Sounds implausible… Number of computational steps to find the shortest sequence maybe grows with Ackermann function. But length of the shortest sequence?

I think you are right. I just read this article linked in the OP: https://www.quantamagazine.org/an-easy-sounding-problem-yiel...