Ancilla intuition, when to use them, how to recognize when I'd want to use them?

Question

Sorry if this is too open ended.

I've spent some time studying some various quantum algorithms that involve ancillary qubits. Some examples that come to mind are phase estimation, linear combination of unitaries (LCU), and this paper on quantum state preparation.

In phase estimation, an ancillary register of l-qubits is storing an l-bit representation of the eigenvalue associate with eigenstate prepared in the system register. In this setting it seems quite obvious why one would want to use ancillas (although I'm not sure I would've been able to come up with it myself!); you need a place to store a value that's related to the system register. Otherwise in order to obtain an energy estimate you'd need to perform measurements for each term of the Hamiltonian $H$ (or at least groups of mutually commuting terms spanning $H$) and gather enough statistics to infer the energy.

In LCU, the ancilla system is used to prepare a superposition to probabilistically apply the terms in the LC based on the relative weights of the coefficients in the LC. Then uncomputing the ancillary register and measuring a signal state (typically the all zero state) tells us that the state on the register corresponded to a normalized application of the LCU onto the input state.

These two approaches use the ancillary system in seemingly totally different ways. In the QPE approach it's used to store a value that's related to information found on the system, in LCU it's used to store a probability distribution related to the coefficients in the LCU. It's essentially a dilation to a larger Hilbert space where a subspace acts non-unitarily. Although I feel like I understand these algorithms and why they need ancillas, when designing a quantum algorithm myself, I don't find it so obvious when to use ancillas or how I would want to use them! They've always felt so mysterious to me and I've struggled to come up with algorithms that effectively use an ancillary system.

In the above linked paper, the authors were able to greatly reduce the circuit depth required for implementing an arbitrary quantum state by introducing an ancilla register with the same size as the system register and performing controlled swaps between them. This seems to be similar to a lot of width vs depth tradeoff people observe in algorithms. This raises a question, why is there such a width/depth tradeoff in algorithms?

I guess I'm interested in what patterns to look for when I'm developing an algorithm that could benefit from ancillas. When are they useful? When do I need them? How do I use them when I find I need them?

Much thanks from an algorithms baby.

Answer 1

I would say you have already given a good answer in the formulation of the question itself. To keep things organized, I shall try to enumerate the most relevant and general use cases of ancillary qubits in quantum computing that I can think of, many of which were already mentioned in the question.

• Computing expectation values: The canonical method to compute expectation values of unitary operators on a quantum computer is the Hadamard test, which involves adding an ancilla that controls the unitary applied in the main register to produce an interference effect in a similar spirit to the Mach-Zehnder interferometer. The quantum phase estimation algorithm is a more sophisticated version of the Hadamard test that allows to achieve a $\mathcal{O}(1/\epsilon)$ scaling of the query of the unitary with respect to the desired precision $\epsilon$. Interestingly, the ancilla and corresponding controlled-unitaries of the Hadamard test can be replaced by projective measurements in the main register, as discussed in this paper by Mitarai and Fujii, following a similar spirit to the derivation of the destructive SWAP test.
• Projecting given state onto eigenbasis of unitary operator: The full potential of quantum phase estimation is unleashed when the input state is a linear combination of eigenstates of the reference unitary, in which case the measurement of a given eigenvalue in the ancillary register projects the main register onto the corresponding eigenstate. This is why we expect to use quantum phase estimation in fault-tolerant quantum computers to prepare the ground state of quantum many-body systems given an input state with a nonvanishing (i.e., polynomially decaying in the system size) overlap with the ground state. This paper by D. Lacroix also considers this property of the quantum phase estimation algorithm to restore symmetries.
• Preparing linear combinations: Adding states is an operation that we take for granted in conventional hardware but that happens to be far less trivial on quantum computers. The usual strategy is to add ancillas that allow to associate each term in the sum with one particular computational basis state of the ancillary register through controlled-operations and then add them all through an operation that acts on the ancillary register alone to move it to the fiducial state. This process is precisely Childs and Wiebe's Linear Combination of Unitaries method that was mentioned in the question, but a less general version of this concept was already present in earlier literature (cf., e.g., this 2001 paper by Ortiz, Gubernatis, Knill and Laflamme).
• Implementing non-unitary operations on quantum hardware: Quantum gates are inherently unitary, as they amount to the time-evolution operator of some closed quantum system. It is, however, possible to embed a non-unitary operation in a larger unitary one through the addition of ancillas. For concreteness, if we have a three-qubit gate, its $8 \times 8$ matrix representation is unitary, but any of its $4 \times 4$ quadrants need not be unitary. By initializing the ancilla in a given computational basis state and then measuring it after the application of such embedding unitary in the Z basis, we can select the desired quadrant probabilistically through post-selection of measurements. A general way of accomplishing this was discussed in this paper by Lin et al. and applied to perform imaginary-time evolution. Similar methods have been used to prepare physically relevant quantum many-body states such as the Gutzwiller wave function or AKLT states. The latter reference also makes use of the LCU method to implement a non-unitary operation by expressing it as a linear combination of unitaries. Note also that the second point in this list can be regarded as a special case of this one, as a projector is a non-unitary operation, although in general we do not know the form of the eigenstate, so we cannot actually find its projector explicitly.
• Reducing circuit depth: Adding ancillas often allows to simplify the basis gate decomposition of many-qubit operations. A celebrated example is the decomposition of multi-controlled-NOT (MCX) gates in the landmark paper by Barenco et al.. Another important example is a decomposition of the Toffoli gate with T-depth 1 found by P. Selinger by adding four ancillas. More generally, the exponential scaling $\Omega(2^n/n)$ of the depth resulting from the ancilla-free quantum state preparation of an arbitrary $n$-qubit state can be reduced to $\Omega(n)$ depth by adding $\mathcal{O}(2^n)$ ancillas. This reflects the general width-depth tradeoff that was alluded to in the question.
• Applying phase kickback effect in a simple way: Most discussions of the Grover algorithm, for example, include an ancillary qubit that only serves to apply a phase shift of $e^{i \pi} = -1$ to the target states in the oracle and to the input state in the diffusion operator per the phase kickback effect. Strictly speaking, one could perform such phase shifts without the ancilla, but the corresponding quantum circuit would be far more complex. In that regard, this point is just a special case of the previous one, but, given the significance of the phase kickback effect in quantum computing, I thought it deserved this highlight.