Phase gradient

Phase gradients are a useful concept in quantum computing. Here we are specifically interested in implementing (phase) rotation gates using phase gradient states as a catalytic resource. This is useful in scenarios typically encountered in fault-tolerant quantum computing, where (phase) rotation gates are expensive compared to CNOT gates, and it is favourable to trade rotation gates for additional qubits.

Inputs

• (Multiplexed) R_Z rotation gate with angles \vec\theta.
• Precision \varepsilon.
• Target and control/multiplexing qubits.
• Auxiliary register in state |0\rangle, to encode \theta with precision \varepsilon.
• Auxiliary register in phase gradient state |\nabla\rangle, at least as large as the angle-encoding register.

Outputs

• (Multiplexed) R_Z rotation implemented within the Clifford + T gate set to precision \varepsilon (in the rotation angles), returning auxiliary registers to their input states |0\rangle and |\nabla\rangle.

Note that below we show the simple example of a non-multiplexed rotation gate, which is helpful to understand the concept of phase gradients as a catalytic resource, but may not pay off in a practical setting. There are multiple important extensions of this simple case, most importantly those that implement multiplexed rotations and/or groups of rotations on different qubits or about different axes. Note that controlled rotations are included in the former scenario as a special case. Finally, any Pauli product rotation can be implemented with the phase gradient method simply by including a Clifford basis change.

Example

Suppose we want to apply the rotation gate R_Z(\theta) with \theta=0.9326(2\pi) within a precision of \varepsilon=0.05 (in the rotation angle). A valid approximation of the angle is 2\pi \phi=0.9296875(2\pi)=(0.1110111)_2 (2\pi), where the subscript 2 indicates that the number is expressed in base 2, i.e., (0.1110111)_2=0\cdot 2^0 +1\cdot 2^{-1}+1\cdot 2^{-2}\dots +1\cdot 2^{-7}. In general we know that b=\lceil\log_2(2\pi/\varepsilon)\rceil bits suffice to approximate any angle \theta\in[0,2\pi) to precision \varepsilon. Here, this corresponds to 7 bits.

The circuit to realize the rotation with a phase gradient then consists of three steps: encoding the binary representation of the approximated, rescaled angle \phi in an auxiliary register, adding this register to a second auxiliary register in the phase gradient state |\nabla_b\rangle of size b, and uncomputing the angle encoding.

The complete circuit for our example is

|ψ>    : ─╭●────────────╭●─exp(-πϕi)─┤  ≈R_Z(θ)|ψ>
|0>    : ─├X─╭SemiAdder─├X───────────┤   |0>
|0>    : ─├X─├SemiAdder─├X───────────┤   |0>
|0>    : ─├X─├SemiAdder─├X───────────┤   |0>
|0>    : ─│──├SemiAdder─│────────────┤   |0>
|0>    : ─├X─├SemiAdder─├X───────────┤   |0>
|0>    : ─├X─├SemiAdder─├X───────────┤   |0>
|0>    : ─╰X─├SemiAdder─╰X───────────┤   |0>
      ╭: ────├SemiAdder──────────────┤ ╮
      │: ────├SemiAdder──────────────┤ │
      │: ────├SemiAdder──────────────┤ │
|∇_7> ┤: ────├SemiAdder──────────────┤ ├ |∇_7>
      │: ────├SemiAdder──────────────┤ │
      │: ────├SemiAdder──────────────┤ │
      ╰: ────╰SemiAdder──────────────┤ ╯

See the phase gradient rotations tab for details.

Non-Clifford cost analysis

While the phase gradient implementation of an R_Z rotation may seem overly complicated, it pays off in the broader context of quantum algorithms. This is for two reasons:

1. The phase gradient state only has to be prepared once and can be reused for as many sequential rotation gates as we like, because it is left untouched, i.e. it is a catalytic state. This makes the overhead for preparing it a constant, and thus the overhead per rotation scales with 1/N for N rotation gates.
2. The construction above can be used synergetically for multiplexed rotations or between rotations on different qubits, reusing the costly element of the circuit, the SemiAdder.

Denoting the cost of the phase gradient state preparation (of a SemiAdder) by C_\nabla (C_+), and the number of rotations we can group together (on average) by n_{\text{group}}, we obtain a non-Clifford cost of

per rotation gate.

This can be compared to synthesis methods like channel-mixing, Gridsynth, or repeat-until-success schemes, which realize each rotation gate independently.

To make things concrete, we will compare the number of T gates required to implement a batch of K m-multiplexed R_Z gates with m=4 and precision \varepsilon=10^{-6} (this corresponds to N=16K and n_{\text{group}}=16 above). We require b=\lceil \log_2(2\pi/10^{-6})\rceil=23 qubits in the phase gradient and angle encoding registers each. Preparing this phase gradient with an overall precision of \varepsilon requires us to implement a Pauli Z operator, a phase gate S, a T gate, and b-3=20 R_Z rotations with precision \varepsilon/(b-3). For simplicity, let's assume we decomposed these rotations with Gridsynth. This requires about 3\log_2((b-3)/\varepsilon)\approx 75 T gates per rotation, leading to about 1500 T gates for the phase gradient state preparation. In addition, the construction for multiplexed rotations requires 4(b+2M-m-6)=180 T gates per multiplexer, where M is the number of angles in one multiplexer, which in turn is equal to n_{\text{group}}=16 here. This leads to an overall cost of 1500 + 180K T gates for the phase gradient approach.

Now, let's assume we instead decomposed the N=16K individual rotations in these multiplexers directly with Gridsynth. This requires about 3\log_2(1/\varepsilon)\approx 60 T gates per rotation, leading to about 960K T gates for the total circuit.

As we can see, the phase gradient state is too expensive to prepare for K=1 to exploit the savings through the arithmetic circuit. However, already for K=2 we find the phase gradient implementation to cost 1860 T gates, whereas the direct discretization via Gridsynth costs 1920 T gates. This advantage then grows linearly with increasing K.

Note that this calculation is to be taken as a rough estimate and there are cheaper synthesis methods than Gridsynth in the presence of auxiliary qubits.

Typical usage

The construction presented here is only useful in scenarios where non-Clifford gates are notably more expensive than Clifford gates and, to some degree, additional qubits. This is typically the case when compiling for fault-tolerant quantum computation. The consequence of the synergetic effects described in the cost analysis above is that phase gradient-based rotations are typically used in larger quantum circuits to realize multiplexed rotations or groups of rotations across multiple target qubits.

References

[1] "Classical and Quantum Computation", A. Kitaev, A. Shen, and M. Vyalyi, Graduate Studies in Mathematics Volume 47, 2002.

[2] "Halving the cost of quantum addition", Craig Gidney, Quantum 2, 74, 2018.

[3] "Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization", Y. Sanders, D. Berry, P.C.S. Costa, L.W. Tessler, N. Wiebe, C. Gidney, H. Neven, and R. Babbush, PRX Quantum 1, 020312, 2020.