Can a quantum computer easily determine the mixing time of the Rubik's cube group?

Question

Officials in Rubik's cube tournaments have used two different ways of scrambling a cube. Presently, they break a cube apart and reassemble the cubies in a random order $\pi\in G$ of the Rubik's cube group $G$. Previously, they would apply a random sequence $g$ of Singmaster moves $\langle U,D, F, B, L, R\rangle$.

However, the length $t$ of the word $g$ - the number of random moves needed in order to fully scramble the cube such that each of the $\Vert G\Vert=43,252,003,274,489,856,000$ permutations is roughly equally likely to occur - is presently unknown, but must be at least $20$. This length $t$ can be called the mixing time of a random walk on the Cayley graph of the Rubik's cube group generated by the Singmaster moves $\langle U,D, F, B, L, R\rangle$.

Would a quantum computer have any advantages to determining the mixing time $t$ of the Rubik's cube group?

I think we can have some clever sequence of Hadamard moves to create a register $\vert A \rangle$ as a uniform superposition over all $\Vert G\Vert$ such configurations; thus applying any sequence of Singmaster moves to $\vert A \rangle$ doesn't change $\vert A \rangle$.

If we have a guess $t'$ as to what the mixing time $t$ is, we can also create another register $\vert B \rangle$ as a uniform superposition of all Singmaster words of length $t'$, and conditionally apply each such word to a solved state $\vert A'\rangle$, to hopefully get a state $\vert B\rangle \vert A\rangle$ such that, if we measure $\vert A \rangle$, each of the $\Vert G \Vert$ configurations are equally likely to be measured. If $t'\lt t$, then we won't have walked along the Cayley graph of $G$ for long enough, and if we were to measure $\vert A \rangle$, configurations that are "closer" to the solved state would be more likely. Some clever Fourier-like transform on $\vert B \rangle$ might be able to measure how uniformly distributed $\vert A \rangle$ is.

To me this feels like something a quantum computer may be good at. For example, if $\vert A \rangle$ hasn't been uniformly mixed by all of the words in $\vert B\rangle$, then some configurations are more likely than others, e.g. $\vert A \rangle$ is more "constant"; whereas if $\vert A \rangle$ has been fully mixed by all of the walks, then $\vert A \rangle$ is more "balanced". But my inuition about both quantum algorithms and Markov chains is not strong enough to get very far.

---

EDIT

Contrast this question with the quantum knot verification problem.

In the quantum knot verification, a merchant is given a quantum coin as a state $\vert K \rangle$ of all knots that have a particular invariant. In order to verify the quantum coin, she applies a Markov chain $M$ to transition $\vert K \rangle$ to itself (if it's a valid coin.) She must apply this Markov chain and measure the result at least $t$ times, but otherwise she has no way to construct $\vert K \rangle$ on her own (lest she could forge the coin.) So if she's given a valid coin, she's given a state that she can't produce on her own, along with a Markov chain as a matrix $M$, and she presumably knows the mixing time $t$; she's required to test that $\vert K \rangle$ is valid.

In the present question, it's probably pretty easy to generate $\vert RC \rangle$ of all Rubik's cube permutations. The quantum circuit corresponding to the Markov chain, call it $S$, of Singmaster moves, is also probably pretty easy to build. However, the mixing time $t$ is unknown, and is the one thing to be determined.

Answer 1

It's an interesting question which is better than most "is there a quantum algorithm for x?" questions. I don't know of an existing quantum algorithm. Let me describe what I think would be a typical first attempt, and why that fails. At the end I'll describe a couple of things that might lead to some improvements.

First Attempt at an Algorithm

Let's say I want to test a particular mixing time $t$. I'm going to create one register, $RC$ to contains sufficient workspace to hold any of the possible configurations of the Rubik's cube. The initial state of this is a product state that corresponds to the starting state of the cube.

Then I'm going to make $t$ ancilla registers, $A_1$ to $A_t$. Each of these is the same size as the number of possible Singmaster moves, and is prepared as a uniform superposition across all possible basis elements. Then for each $i=1,\ldots t$, we apply a controlled-unitary from $A_i$ to $RC$ where the register $A_i$ specifies which Singmaster move is applied on $RC$.

After all this, if we just look at $RC$, it should be in the maximally mixed state if the mixing has happened as desired. The problem is how to test whether or not this output is the maximally mixed state. There are useful techniques such as this one, but what accuracy do we require (i.e. how many repetitions?). We'll need about $|A|^t$ to be sure, I think.

In fact, this way of doing things is just as bad as doing it classically: you could replace the initial state of each of the $A_i$ with $\mathbb{I}/2^{|A_i|}$ and it wouldn't change the outcome. But this really is just like making a random choice each time and running many times, checking for the correct output distribution.

Possible Improvements

• Running as I described, the output density matrix $\rho$ (on $RC$) must be diagonal. That means that the uniform superposition $|u\rangle$ over all basis states is an eigenstate if and only if the system is maximally mixed. I would if one could combine this observation with some sort of amplitude amplification to get a mild speed-up. Note that $\rho^k|u\rangle$ builds up a difference very rapidly from $|u\rangle$ if the state is not an eigenvector.

• Aside from that, you probably need to do something smarter with the ancilla registers. There is some hope that this might be possible because there's quite a lot of group structure built in to the Rubik's cube. One thing that you might try is to see whether you can replace all $t$ ancilla registers with a single register, apply Hadmard gates on every qubit of the register in between each round of controlled-unitaries. It might be that all this does is give you an efficiency saving in terms of the number of qubits compared to my original suggestion. It might not even do that.

Whether either of those work directly, I don't know. Still, I think the key principles are to find some useful group structure, and find a way that amplitude amplification can be applied.

You might find it useful to read up about unitary designs. This is certainly a distinct problem from what we're talking about here, but some of the technical tools might be useful. Roughly speaking, the idea is that a set of unitaries $\{U\}$ is a $t$-design if random application of these unitaries lets one simulate a truly random unitary (drawn from the Haar measure) on output functions $f$ which, when expanded using a Taylor series, are accurate up to degree $t$. The approximate connection here is that if you take the unitaries representing a sequence of $t$ Singmaster moves as $\{U\}$, it would be sufficient if this set were a 2-design (if you get $\text{Tr}(\rho^2)$ correct, you're done).

Answer 2

(CW to avoid reps from self-answer)

There might be an interactive way for two parties to narrow in on the value of $t$, following up on @DaftWullie's answer and @Steven Sagona's comments. My formalism is poor, but I hope the idea gets through...

For example, call the two parties Alice and Bob. The parties have to cooperate, and behave honestly according to the protocol.

Alice knows how to prepare two states, $\vert A_0 \rangle$ and $\vert A_1 \rangle$. Here, $\vert A_0\rangle$ is the uniform superposition over all Rubik's cube combinations, and $\vert A_1\rangle$ is some other monkey state with the same number of qubits (such as the state corresponding to a solved Rubik's cube, or a uniform superposition over some large subgroup of $G$). Bob knows how to apply a matrix $M$ to a quantum state, where $M$ corresponds to single step of all of the Singmaster moves (with ancillas where appropriate.)

Alice and Bob want to show that the mixing time $t$ of the Rubik's cube group under Singmaster moves is at most $r$. Alice and Bob repeat the following $s$ times.

1. Alice flips a coin $i\in\{0,1\}$, and provides $\vert A_i \rangle$ to Bob
2. Bob repeats $r$ times to apply $M$ to $\vert A_i \rangle$, and measures the projector each time.
3. If the projector is $1$ for each of the $r$ iterations, then Bob says that $i=0$. If the projector is not $1$ for at least one of the $r$ iterations, then Bob says that Alice's $i=1$.

If $i=0$, then each of Bob's $r$ iterations in step 2 does not change $\vert A_0\rangle$ - because by definition $\vert A_0 \rangle$ is an eigenstate of Bob's matrix, and Bob's matrix just permutes the states among themselves. If $i=1$, then the monkey state $\vert A_1 \rangle$ is not an eigenstate of Bob's projector, and the chance that a $1$ will not be measured grows quickly with $r$.

Thus, if Bob has accurately predicted $i$ for $s$ iterations, the probability of success grows exponentially with $s$, and Bob's $r$ is large enough to distinguish a valid Rubik's cube state from a monkey state.

I don't know how far apart $\vert A_1\rangle$ has to be from $\vert A_0\rangle$. I also don't know if interaction can be removed.

Answer 3

Initially let's consider some registers and operators.

1. The register $\vert A\rangle$, which encodes superpositions of states of the cube (e.g. a permutation of the cube $G$);
2. The operator $U$, which acts on $\vert A\rangle$ to map the all-0's ket $\vert 00\cdots 0\rangle$ to the uniform superposition over all $\Vert G\Vert$ states;
3. The register $\vert B\rangle=\vert b_1\rangle\vert b_2\rangle\cdots\vert b_k\rangle$, which encodes superpositions of a set of Singmaster moves to be applied to a given position (e.g., superpositions of words of Singmaster moves of length $k$);
4. The operators $V$ and $V^{-1}$, which act on $\vert B\rangle$ to map the all-0's ket $\vert 00\cdots 0\rangle$ to the uniform superposition of all $18^k$ words of Singmaster moves of length $k$ (and vice-versa); and
5. The (controlled) operator $W$, which applies Singmaster move $b$ to to a given cube position.

If $\vert A\rangle$ is in the uniform superposition over all elements of $G$, then $\vert A\rangle$ is in an eigenstate of $W$, and repeated applications of $W$ will not be kicked back to affect $\vert B\rangle$.

That is, $V^{-1}$ should return $\vert B\rangle$ in the above circuit to the all-zeroes ket $\vert 00\cdots 0\rangle$.

However, as noted by @DaftWullie, if $\vert u\rangle$ is not in an eigenstate, then a difference between $\vert u \rangle$ and $\rho^k \vert u\rangle$ builds up very rapidly - I believe a speed at which this difference builds up depends precisely on the mixing properties of the operator of interest.

Thus, if we are able to prepare a state $\vert A\rangle$ that is perturbed from the uniform distribution, such that $\vert A\rangle$ is not an eigenstate, then repeated applications of $W$ will rapidly build a difference, and $V^{-1}\vert B\rangle$ may not be the all-zeroes ket.

If we had a function $F$ acting on $\vert A\rangle$ and an answer qubit $\vert C\rangle$ that determines, say, whether some hash $\{0,1\}^{\log_2 \Vert G\Vert}\mapsto (0,1)$ of the Rubik's cube position is less than some threshold $\delta$, and we use this $F$ to control a rotation of $\vert A\rangle$, then I believe that $V^{-1}\vert B\rangle$ in the circuit above will not read the all-zeros ket, and instead will likely deviate from the all-zeroes ket in a manner depending only on $\delta$ and the mixing time of the Rubik's cube group with the Singmaster generating set.

That is, I expect measurement of $\vert B\rangle$ in the above circuit will read $\vert 00000\cdots000101101\rangle$ or something similar, where the index of the first $1$ depends solely on the mixing time and the threshold $\delta$.