In quantum circuit design, a common problem is computing too much. You’ll find some clever way to compute a result, only to realize it also computes something else. An unwanted value. A value whose mere existence is splitting your carefully crafted superposition into jagged non-interfering pieces. A value that you can’t discard, and can’t ignore.

The typical way to deal with unwanted values is uncomputation. Find some series of operations that would make the value, and run them backwards. This unmakes the unwanted value. The downside of uncomputation is its cost. You pay to make the value, and then you pay again to get rid of it! There are tricks to reduce these costs, such as measurement based uncomputation, but in this post I want to discuss a different kind of idea for dealing with unwanted values: “superposition masking”.

Anecdotally, basically nobody knows about superposition masking. I rarely see it used in papers. And, when I mention it to other researchers, I don’t get many “oh that old thing” reactions. The typical reaction is more like “huh? why does that work?”, triggering an hour long explanatiathon.

The core idea behind superposition masking is the following: you can craft states that prevent unwanted values from forming in the first place. It’s “An ounce of prevention is worth a pound of cure” but for quantum circuits instead of blood sugar. You can save a lot of effort by preventing the formation of an unwanted value, rather than intervening to get rid of it later.

My goal in this post is to make you appreciate superposition masking. My plan? Just show it working. Over, and over, and over. So… let’s get started with something nice and simple.

Level 0: Parallel Parities

Suppose you’re given a bunch of qubits, and told to measure whether an even or odd number of them are ON. In the lingo: build a circuit that measures $Z^{\otimes n}$. One way to do this is to initialize an ancilla qubit into the $|0\rangle$ state, and then for each input qubit perform a CNOT gate targeting the ancilla:

This circuit is really deep. (Not deep as in insightful, deep as in slow.) Every gate touches the ancilla, which serializes the whole affair. But surely for something this simple there’s some way to introduce a bit of parallelism…?

One way to add parallelism is to use multiple ancilla qubits. For example, if there were two ancillas instead of one, then half of the inputs could CNOT into one ancilla while the other half of the inputs CNOT into the other ancilla. The desired value is then the parity of the two ancilla qubits, which can be pushed into one of the ancillas using a final CNOT:

…unfortunately, this circuit isn’t correct. See the red exclamation points in the top right? That’s an unwanted value. The extra ancilla is storing the parity of one half of the inputs. The circuit isn’t complete until this value is uncomputed.

You’d never remove this particular unwanted value with normal uncomputation. Doing so would double the depth of the circuit, undoing all the progress you made by introducing the extra ancilla in the first place! Measurement-based uncomputation could save you from that fate, but superposition masking is an even better fit.

The superposition masking strategy for this setup is very simple: initialize the ancilla qubits into the state $|00\rangle + |11\rangle$ (instead of $|00\rangle$). Then, at the end of the circuit, you can just measure both ancillas and recover the parity classically:

Why does this work?

The key detail to understand is that the state $|00\rangle + |11\rangle$ doesn’t care which of its qubits you apply a NOT gate to. Bit flip the left qubit, and you transition to the state $|01\rangle + |10\rangle$. Bit flip the right qubit? Same transition. And $|01\rangle + |10\rangle$ has the same property. Regardless of which of its qubits you bit flip, you’ll transition back to the state $|00\rangle + |11\rangle$. Because the ancillary state doesn’t care which qubit you bit flip, it doesn’t matter that some of the CNOT gates are targeting one of its qubits while others are targeting the other.

After all the CNOTs have been performed, the ancillary state will be $|00\rangle + |11\rangle$ if an even number of the qubits were ON and $|01\rangle + |10\rangle$ if an odd number were ON. We can distinguish the two possible cases by measuring the ancilla qubits and seeing if an even or odd number of the measurement bits were ON.

In addition to the bit of information we wanted, we also learned a second bit. In a quantum computation, learning too many bits is a red flag. But here it’s benign; it’s just measuring the distinction between $00$ and $11$ in $|00\rangle + |11\rangle$. The state was used in a way where this detail can’t have become entangled with the input qubits, so it’s just an independent random bit. The 00-vs-11 distinction is where the unwanted value would have gone, but that degree of freedom was masked out by the superposition.

Exercise for the reader: improve the depth of measuring $Z^{\otimes n}$ to $n/3 + O(1)$ by using superposition masking on three ancilla qubits.

Exercise for the reader: construct a circuit that measures $Z^{\otimes n}$ in constant depth, up to Pauli feedback. (“Up to Pauli feedback” means non-constant-depth classical computations may be needed to finish the computation of the parity and to determine later Pauli corrections to apply to the qubits.)

Level 1: Parallel Sums

Let’s do a harder example now, though you’ll see that ultimately it’s extremely similar to the first one.

You’re asked to measure the sum of many superposed integers (many “quints”). One way to do this is to initialize an accumulator into the $|0\rangle$ state and then, one by one, add the integers into the accumulator:

You might already see where this is going. As in the parity example, we don’t like how this forces us to process the quints serially. To introduce some parallelism, we can use multiple accumulators:

…but once again the problem is that there’s an unwanted value. To avoid paying the cost of uncomputing it, we use superposition masking. This time, the special initial state is a superposition of all ways the ancillary registers can add up to 0. For $m$-qubit quints, that state is:

\[\sum_{k=0}^{2^m-1} |k\rangle \otimes |(-k) \bmod 2^m\rangle\]

An easy way to create this state is to initialize one of the registers to $|+\rangle^{\otimes m}$, and then subtract it out of the other register:

If you work through the algebra, you’ll see that adding into one of the accumulators has exactly the same effect as adding into the other. You’ll also see that the two values measured at the end contain the intended result (obtained by adding the measured accumulators), and a uniformly random value uncorrelated with the rest of the system (obtained by subtracting them). The random value is where the unwanted value would have gone, if not for the mask. Once again the superposition mask has prevented an unwanted value from forming, bypassing the need for an uncomputation.

Level 2: Streamed Fibonacci Products

The most recent usage of masking, that I’m aware of, was by my student researcher Katherine van Kirk. Her project was to reduce the space overhead of Regev’s factoring algorithm. In particular, she was working on getting “qubit recycling” to work. Qubit recycling is a very old trick for reducing the space cost of phase estimation, but it has a very strict constraint: you have to iterate through the “phase estimation qubits” only once (you have to stream them).

There were various parts of Regev’s algorithm that were getting in the way of streaming. A key one was that Ragavan and Vaikuntanathan’s variant of Regev’s algorithm, which fixed a bunch of other space costs, uses two accumulators. When it came time to measure the result, the second accumulator contained an unwanted value. Uncomputing this value forced a reverse pass over the phase estimation qubits, breaking streaming and doubling the gate count of the algorithm.

Katherine had asked Seyoon Ragavan if he thought it was possible to fix the unwanted value. He said probably not. Martin Ekerå also suspected it wasn’t possible to stream the algorithm. Perhaps by now you suspect the opposite. Two accumulators? An unwanted value? What if we… initialized the second register to a uniform superposition?

…Yeah that just works. Plug in the superposition, carefully analyze its effect, and at the crucial moment you find that you can simply measure both accumulators instead of turning back and uncomputing. I’d go into detail, but explaining this example actually gets quite involved. In particular, I’d need to explain a huge chunk of Regev’s algorithm to provide context. Plus, Katherine just explained it in our preprint. (The preprint also explains how to resolve the other former streaming showstopper, which was that it was unclear how to do phase estimation using Fibonacci powers of operations rather than power-of-two powers.)

Level 3: The Coset Representation

Often, quantum arithmetic is done modulo some classically known constant $N$ (rather than modulo a power of 2). This is annoying, because adders are more expensive when $N$ isn’t a power of 2. A typical modular addition decomposes into a non-modular addition, a comparison (to check if it passed $N$), a second non-modular addition (to conditionally subtract $N$ to get back into range), and a second comparison (to uncompute the first comparison). Modular arithmetic is really expensive!

In 2006, Zalka found a way to bypass this expense. He found a way to perform a modular addition with a normal adder. His basic insight is that we have a value we want (the remainder $x \bmod N$), a value we don’t want (the quotient $\lfloor x / N \rfloor$), and instead of constantly ensuring the unwanted quotient is 0 we can mask away the problem.

The normal representation of a remainder $r$ modulo $N$ is the state $|r\rangle$. Zalka’s coset representation instead uses:

\[|C(r)\rangle = \sum_{q=0}^{2^m-1} |r + Nq\rangle\]

A crucial difference between this example of masking and the prior ones is that this one is approximate. For example, if you increment the register, you might push the lowest value in the superposition past a multiple of $N$. That is to say, you might increment the quotient. The key thing to realize is that the quotient’s state is affected very little by that unwanted increment. The infidelity between the quotient-incremented state $|C(r + N)\rangle$ and the ideal state $|C(r)\rangle$ can be exponentially suppressed by increasing $m$:

\[1 - \Big|\langle C(r + N) | C(r) \rangle\Big|^2 \leq \frac{2}{2^m}\]

In general, as long as the total amount you offset the register by is substantially less than $2^mN$, Zalka’s coset representation is a good approximation of storing the remainder without storing the quotient. A small amount of approximate masking yields a large cost reduction.

Level 4: Quantum Nails

Another annoying thing about quantum adders is that the low depth ones cost a lot of Toffolis. A linear-depth ripple carry adder? That costs an understandable $n$ Toffolis. A log-depth carry-lookahead adder? Suddenly four times as many Toffolis! Can’t we get a better deal somehow??

Classically, there’s a technique called “nails” for splitting operations into pieces. Basically, instead of storing a number using as few bits as possible, you introduce some extra padding bits here and there across the register (these extra bits are the nails). When you operate on numbers with nails, you can use the nails as pressure relief for effects that would otherwise have to propagate long distances. For example, carries produced during an addition can be dumped into the nails rather than potentially continuing all the way across the register. (An extreme version of this is the carry-save adder, which is an adder that achieves constant depth by having a nail at every bit position.)

It would be great to be able to use nails quantumly. It would let us split adders into independent blocks. We could use a ripple carry adder on each block, which wouldn’t cost too many more Toffolis but would be a lot lower depth (because blocks are shorter than entire registers). Alas, there is the obvious problem: at the end of the computation, the nails are unwanted values. To get rid of them, you’ll have to undo the entire– nope, not doing that, we’re doing masking.

Instead of initializing the nails of the register to $|0\rangle$, initialize the register into a superposition of all possible representations of 0. For example, if there’s a 50 qubit nail at offsets 500, 1000, and 1500 of a 2050 qubit register, then the initial state is:

\[\sum_{a=0}^{2^{50}-1} \sum_{b=0}^{2^{50}-1} \sum_{c=0}^{2^{50}-1} \Big|-2^{500}a-2^{1000}b-2^{1500}c \pmod{2^{2050}}\Big\rangle \otimes |a\rangle \otimes |b\rangle \otimes |c\rangle\]

Concretely, this state is created by initializing the nails into uniform superpositions and then subtracting them out of the main register at the appropriate bit offsets. You can add values into the resulting state by adding separately into each of the 550-qubit blocks. Using a ripple carry adder on each block (rather than the entire register) improves depth by ~73% (2050 to 550) while only increasing the Toffoli count by ~8% (from 2050 to 2200). This is a much more practical tradeoff than the one offered by carry-lookahead adders.

As with Zalka’s coset representation, this masked nail representation is approximate. The mask doesn’t completely stop unwanted information from entering the nails. But the rate of information leakage is suppressed exponentially as you increase the length of the nails, and in practice it’s possible to find good tradeoffs.

Level 5: Un-approximation

In 2024, Chevignard et al revolutionized quantum factoring. They found a way to compute an approximate modular exponentiation which, combined with prior work, made it possible to factor $n$-bit semiprimes using only $n/2 + \epsilon n$ qubits. However, they paid a huge gate count overhead to save this space.

The gate count overhead came from many places, but one of them is particularly relevant to this post. The approximate value that Chevignard et al compute is perturbed away from the value normally computed during Shor’s algorithm. This perturbation is information that was produced by the computation, but that you don’t want to measure and ultimately need to get rid of. Sound familiar? The perturbation is an unwanted value.

Chevignard et al got rid of the unwanted perturbation by uncomputing it the normal way. When I built on Chevignard et al’s work, a key goal was to fix the Toffoli overhead. This unwanted value was doubling the gate count, so I really wanted to get rid of it. And, looking at it, the obvious thought occurred: “I bet I can mask it.”.

The computation of the approximation is done by a series of additions into an accumulator. Chevignard et al initialized the accumulator to $|0\rangle$. I instead initialized the accumulator to a uniform superposition over the integers less than a custom value $M$. The tricky bit was picking an $M$ that wasn’t too large or too small. It needed to be large enough to prevent almost all information about the perturbation from entering the accumulator, but not so large that it prevented useful information from entering the accumulator. I picked an appropriate $M$, and collected my factor of 2 fewer gates.

Interestingly, this case is essentially the opposite of Zalka’s coset representation. He needed to get rid of an unwanted value in the high bits (the quotient). I needed to get rid of an unwanted value in the low bits (the perturbation). They were both solved by carefully targeted masking.

Level 6: Offloading Inversion

The craziest use of masking that I know of is a trick for computing $x^{-1} \pmod{N}$ under superposition. Although there’s been quite a lot of progress improving multiplicative inverse subroutines recently, it’s still a very expensive operation. Amazingly, masking can produce an inversion far more cheaply than in even the most recent papers. …Sort of. You’ll see.

There’s an old classical trick for batching modular inversions called Montgomery’s trick. Instead of computing $x^{-1}$ and $y^{-1}$ separately, compute the inverse $z^{-1}$ of their product $z = xy$. Then, by multiplying $x\cdot z^{-1}$, you recover the multiplicative inverse of $y$ (because $x \cdot z^{-1} = x \cdot (xy)^{-1} = x \cdot x^{-1} \cdot y^{-1} = y^{-1}$). Similarly, multiplying $y \cdot z^{-1}$ yields $x^{-1}$. Thus Montgomery’s trick replaces two inversions with three multiplications and just one inversion. Multiplication is cheaper than inversion, so that’s a savings.

Here’s the concept: can you apply Montgomery’s trick to a quantum $x$, while keeping $z$ classical? If by some miracle this was possible, then we’d be able to offload the incredibly expensive inversion to a classical computer. The quantum computer would only have to do a few multiplications. This sounds impossible… but it’s not. Samuel Jacques figured out how to do it. He told me about it in 2020, I got excited, and we (well… mostly he) wrote the preprint “Offloading Quantum Computation by Superposition Masking” describing it.

Here’s how it works. To get a classical $z$ from a quantum $x$, introduce a uniformly superposed $y$ and then measure $x \cdot y$. This measurement tells you how $x$ relates to $y$, but because $y$ was uniformly superposed it doesn’t actually reveal anything about $x$. $y$ masks $x$. Instead of revealing $x$, what the measurement effectively did was force $y$ to become equal to $x^{-1} \cdot m \pmod{N}$, where $m$ is the measurement result. By classically computing $m^{-1}$, and multiplying it into $y$, you recover $x^{-1}$ without ever performing an inversion on the quantum computer:

(Note: there are some nitpicky details here about accidentally making values of $y$ that aren’t in the multiplicative group of $N$. However, in typical cases that’s so unlikely that it can be ignored.)

Now comes the irony. There’s a teeny weeny major showstopping problem with this technique: it doesn’t turn $|x\rangle$ into $|x^{-1}\rangle$; it turns it into $|x\rangle \otimes |x^{-1}\rangle$. It leaves behind an unwanted value. Masking has created the exact problem it normally solves! It can efficiently compute $x^{-1}$ out of place, but what algorithms need is inplace inversion. The only known way to get rid of the out-of-place inverse is via other slower methods, defeating the entire purpose.

I find this problem so frustrating. It’s the only example I know where measurement makes it easier to compute something, rather than easier to uncompute it. Surely there must be a way to fix it! And it’s important if it can be fixed, because it’d probably yield efficient elliptic curve point addition circuits!

Come to think of it, this problem has nagged at me since 2020. I’m tired of it. How about YOU solve it:

Hard exercise for the reader: offload the expensive part of this transformation to a classical computer:

\[|x^{-1} \pmod{N}\rangle \otimes |x\rangle \rightarrow |x\rangle\]

Conclusion

Superposition masking is a useful tool. I’ve used it over and over throughout my career. It’s not particularly complicated, it has lots of applications, and it’s underutilized. Add it to your toolbelt.

A notable downside of superposition masking is that, to the best of my knowledge, there’s no easy way to test it numerically. The proofs that these circuits work are typically analytic. They appeal to structure, rather than to sampling or to case enumeration. This is in stark contrast to, for example, kickmix circuits. Maybe superposition masking isn’t underappreciated; maybe it’s just waiting for someone to find an easier way to verify the amazing constructions it produces.