Recently, I’ve been working on a fast simulator for reversible classical circuits assisted by measurement based uncomputation. Basically it’s just doing the strategy I pointed out back in 2019. The simulator supports the CCX gate for classical computation, the HMR (Hadamard+Measure+Reset) gate for measurement based computation, and phase gates like Z for correcting phase kickback from HMR gates.
It’s surprising that CCX+HMR circuits can be efficiently classically simulated, because CCX+H is known to be universal for quantum computations. Something about forcing the H to only occur just before a demolition measurement prevents the universality. A natural question then is whether this constraint can be weakened. For example, suppose H was also allowed immediately after a reset (i.e. you were allowed to prepare $|+\rangle$). Can the resulting circuits still be simulated efficiently on a classical computer? That would be really useful if true, because it would give a cheap method for verifying constructions based on superposition masking.
Unfortunately, as I will explain here, introducing $|+\rangle$ has a huge effect. CCX+HMR is cheap to simulate, but CCX+HMR+RX is computationally universal. In this post, I’m going to show that universality by constructing the gateset Clifford+T from the gateset CCX+HMR+RX. As a bonus, it turns out this construction achieves the goals of the construction in “Actually, you can’t test if quantum uses complex numbers” but with a single-qubit catalyst rather than a three-qubit catalyst.
Axiomatic gates
Here are the gates we are given:
-
CCX. The Toffoli gate. The controlled-controlled-not. Flips the target when the two controls are ON.
-
HMR. X basis demolition measurement. The “hammer” gate. Equivalent to a Hadamard followed by a computational basis measurement followed by a reset of the qubit into the $|0\rangle$ state.
-
RX. X basis preparation. Resets the qubit into the state $|+\rangle = |0\rangle + |1\rangle$.
These are the only quantum gates we have access to. Everything else must be built from these, including simple things like “prepare $|1\rangle$”.
Note that we are allowed to perform arbitrary classical computation and feedback. We can do different gates depending on prior measurement results, including things like repeating a probabilistic state preparation until it succeeds.
Constructed Gates
There are several gates you might just take for granted as being present, but which we must construct.
INIT_ZERO
We can initialize a qubit into the $|0\rangle$ state by performing an HMR gate and ignoring the measurement result:
INIT_ZERO from {HMR}:
BOOTSTRAP_MINUS
We can arduously initialize a qubit into the $|-\rangle = |0\rangle - |1\rangle$ state using a repeat until success construction (RUS):
BOOTSTRAP_MINUS from {INIT_ZERO, RX, CCX, HMR} using RUS
It takes on average 9 attempts per success.
BOOTSTRAP_ONE
We can arduously initialize a qubit into the $|1\rangle$ state using a repeat until success construction:
BOOTSTRAP_ONE from {RX, CCX, HMR} catalyzed by $|-\rangle$ using RUS
It takes on average 2 attempts per success.
INIT_ONE
Once we’ve bootstrapped multiple $|1\rangle$ states, we can catalyze the production of more $|1\rangle$ states:
INIT_ONE from {RX, CCX} catalyzed by $|1\rangle, |1\rangle$:
INIT_MINUS
Once we’ve bootstrapped $|1\rangle$ and $|-\rangle$, we can catalyze the production of more $|-\rangle$ states:
INIT_MINUS from {RX, CCX} catalyzed by $|-\rangle, |1\rangle$:
CX
A CX is a CCX with a control in the $|1\rangle$ state:
CX from {CCX} catalyzed by $|1\rangle$:
X
An X gate is a CCX with both controls in the $|1\rangle$ state:
X from {CCX} catalyzed by $|1\rangle$, $|1\rangle$:
CZ
A CZ gate is a CCX with the target in the $|-\rangle$ state:
CZ from {CCX} catalyzed by $|-\rangle$:
Z
A Z gate is a CCX with a control in the $|1\rangle$ state and the target in the $|-\rangle$ state:
Z from {CCX} catalyzed by $|1\rangle$, $|-\rangle$:
H
The basic gates are sufficient for performing a Hadamard gate:
H from {RX, CX, CZ, X, Z, HMR} using feedback
BOOTSTRAP_i
All the gates we’ve used so far are defined using only real numbers. To provide access to the complex plane, we can introduce a single $|i\rangle = |0\rangle + i|1\rangle$ catalyst.
Later I will show this catalyst can be replaced with literally any state whatsoever. But for now we will pretend it is a true $|i\rangle$ state, of which exactly one is provided.
DUPE_i
A nice property of $|i\rangle$ states is they catalyze their own production:
DUPE_i from {RX, CX, CZ} catalyzed by $|i\rangle$
S
The S gate can also be catalyzed by $|i\rangle$ states:
S from {CX, CZ} catalyzed by $|i\rangle$
All Cliffords
We can now construct CX, H, and S. This is well known to be a universal gateset for Clifford operations.
All Pauli Product Measurements
Combining Cliffords with the HMR operation, we can now perform demolition and non-demolition measurements of any Pauli product operator. For example, we can now perform MZ (non-demolition Z basis measurement).
BOOTSTRAP_APPROX_T
There is a repeat until success construction, using the operations we’ve defined so far, that produces an approximation of the state $|\sqrt{i}\rangle = |0\rangle + \sqrt{i}|1\rangle$ with a fidelity of 99.5%:
BOOTSTRAP_APPROX_T from {DUPE_i, RX, INIT_ZERO, X, CCX, H, MZ} using RUS:
BOOTSTRAP_DISTILLED_T
Because we have access to the Toffoli gate, rather than only Clifford gates, we can do substantially more efficient T state distillation than is normally possible. There is a 2-to-1 factory with quadratic suppression:
BOOTSTRAP_DISTILLED_T from {BOOTSTRAP_APPROX_T, CCX, S, X, H, MZ} catalyzed by $|0\rangle$ using RUS:
This distillation procedure can be concatenated with itself in order to produce arbitrarily reliable $|\sqrt{i}\rangle$ states.
T
Once a sufficiently good approximation of $|\sqrt{i}\rangle$ has been distilled, T gates can be catalyzed by it:
T from {H, CCX, CX} catalyzed by $|\sqrt{i}\rangle, |i\rangle$:
Note that the chance of algorithm failure is at most as large as the infidelity of the $|\sqrt{i}\rangle$ catalyst (assuming there is only one), regardless of how many T gates it catalyzes.
Removing the $|i\rangle$
At this point I have explained how to implement Clifford+T, but I have cheated in one place: the BOOTSTRAP_i construction uses an $|i\rangle$ state that clearly can’t be produced by RX+CCX+HMR because those gates are defined using only real numbers whereas $|i\rangle$ has imaginary parts. However, in a circuit constructed using the method specified so far in this post, the only operation that needed a non-real complex number was preparing the seed $|i\rangle$ state. Therefore, replacing that single $|i\rangle$ with its conjugate $|j\rangle = |0\rangle - i|1\rangle$ is equivalent to conjugating all complex numbers that appear in the entire circuit. By the conjugation symmetry of the complex numbers, this preserves the distribution of measurement results produced by the circuit.
The fact we can replace the seed $|i\rangle$ with $|j\rangle$ implies we can replace it with anything. Consider that $X|i\rangle = |j\rangle$, $Z|i\rangle = |j\rangle$, and $XZ|i\rangle = |i\rangle$. All Pauli errors turn the $|i\rangle$ state into itself or $|j\rangle$. Applying Pauli errors to the $|i\rangle$ seed does not affect the function of the circuit! That means maximally depolarizing the seed, by hitting it with an X gate with 50% chance and a Z gate with 50% chance, won’t affect the circuit. But hitting a state with maximum depolarization turns it into the maximally mixed state and, if a maximally mixed state works with 100% chance, all states must work. Therefore the seed $|i\rangle$ state can be replaced with anything, such as $|0\rangle$ or $|-\rangle$ or a Bell pair entangled with some unknown qubit somewhere else in the world. I choose to replace it with $|0\rangle$, completing the proof that RX+CCX+HMR is computationally universal.
As mentioned in the introduction, this construction is a strict improvement on the construction I described in this previous post. It uses real-only gates, but only needs to store one entangled catalyst qubit per computer (rather than three) (the catalyst being what would have been $|i\rangle$ if the seed $|i\rangle$ wasn’t replaced with $|0\rangle$).
