Efficient Rotations With Phase Gradient States

Efficient Rotations?

As it stands, quantum algorithmic efficiency tends to be quantified by the number of T gates required to execute the non-Clifford operations included in a system. Since each T gate represents a fixed \(\frac{\pi}{4}\) rotation, generating arbitrary angles that deviate from this fixed point becomes increasingly resource intensive the more we vary from \(\frac{\pi}{4}\). Arbitrary rotations are very expensive and, at the same time, foundational to some of the most important tools we have in quantum algorithms and computing, such as the quantum Fourier transform (QFT), quantum phase estimation, and the Trotterization algorithm. As a result, optimizing these operations in the fault-tolerant picture is very important [1].

To emphasize the benefit of T gate optimization, let us take the example of time evolution simulation on a computational grid. Here, a wavefunction discretized to \(N=2^n\) grid points, where \(n\) is the number of qubits required to represent the dimensions of the grid, can be effectively evolved in time via the application of a multiplexed rotation, which can be interpreted as a mesh of controlled rotations that apply position-dependent phases to all members of a given state. In the naïve approach, where each point on the grid is treated independently and receives an isolated, individual rotation, the system’s gate count will scale as \(\mathcal{O}(2^n\log_2(1/\epsilon))\), where \(\epsilon\) is the desired precision. Yikes.

A quick resource estimation for a single pass of this procedure can be carried out using PennyLane and the estimator tool. Note that, for an \(n\)-qubit system, SelectPauliRot() (a PennyLane operator that represents the aforementioned multiplexed operation) will apply a total of \(R=2^n\) rotations to address each possible state. Thus, for a 3-qubit system, 8 rotations will be applied in a single pass. The T count estimate here is made using the method outlined in [8] for gate synthesis, which is the default approach taken by PennyLane’s estimation function.

import pennylane as qp
import numpy as np
import pennylane.estimator as qre

n = 3 #Control Qubits
np.random.seed(35)
angles = np.random.rand(2**n)*2*np.pi

#Define Circuit Wires
data_wires = range(n)
target_wire = n

dev = qp.device("default.qubit")

@qp.qnode(dev)
def circuit_baseline():
  for wire in data_wires:
    qp.Hadamard(wire)
  qp.SelectPauliRot(angles, data_wires, target_wire, rot_axis="Y")
  return qp.probs(target_wire)

print(qre.estimate(circuit_baseline)())

--- Resources: ---
 Total wires: 4
   algorithmic wires: 4
   allocated wires: 0
     zero state: 0
     any state: 0
 Total gates : 363
   'T': 352,
   'CNOT': 8,
   'Hadamard': 3

From this estimate, we can see that even a single, simple pass of a rotation multiplexer requires over 300 T gates for a small set of randomly-chosen angles. Considering the cost of T gates and the fact that useful applications of this procedure will need to handle many more qubits and many more rotations, it is easy to see the cost will grow very quickly. We need a hero!

The Phase Gradient State

What if, instead of having to apply an individual, expensive rotation for each bit value to achieve the desired outcome, we could simply add a pre-defined phase state to the qubits as needed?

Phase gradient states are a type of catalytic resource state that can be used to facilitate rotations additively. For clarity, a state is “catalytic” if it is unchanged by a process that it plays a role in facilitating. To borrow (aptly) from the language of chemistry, it exists to catalyze (assist) a specific process (operation). The phase gradient state can be interpreted as a catalyst for phase shifts, invoking phase accumulation on other qubits without sacrificing its own properties. The state can be represented as

where \(x\) represents a target computational basis state, which one can interpret as an address marker that dictates what rotation angle is applied. In product state form,

Here, \(b=\log_2(1/\epsilon)\) is the total number of qubits stored in the phase gradient register, \(B=2^b\) is the total number of possible states in the superposition between all qubits in the gradient register, and \(j\) is the index of a specific qubit within the register.

The phase gradient state can be interpreted as acting as a pre-defined plane of stored angles that can be accessed and invoked on a target state as desired. This state can be prepared once, stored in an auxiliary register, and reused. To induce a rotation, an integer value \(k\), proportional to the rotation angle needs to be added to the gradient register, which is done most commonly using a controlled addition gate step, to invoke a phase shift on the target state corresponding to the “address marker” mentioned above. This procedure is summarized as

The controlled addition step can basically be interpreted as a “push” invoked by the added state on the phase gradient register. Via quantum addition, the gradient register is shifted by an amount equivalent to the binary weight of each data qubit that is added to it. Since the data state remains “stationary”, the two states will be out of phase by an amount equivalent to the shift experienced by the register following the addition operation.

Since phase is relative, it can be said without issue that the data register has accumulated a phase equivalent to this shift. This process is referred to as phase kickback. Again thanks to the relative nature of this shift, the properties of the gradient register are globally unchanged, solidifying it as a catalytic resource.

Thus, the phase gradient state essentially stores spatially dependent phases that can be applied to invoke rotations as a function of qubit position.

This structure can be easily extended to the more commonly used multiplexed case that we discussed at the beginning of this demonstration. In this case, we can use a quantum read only memory (QROM) to store each \(k\) value in parallel in a data register. To carry out the rotation, it is best practice to carry out a semi-out-of-place addition using a SemiAdder() to add this data register to the phase gradient register. This reduces the complexity bound to \(\mathcal{O}(2^n+\log_2(1/\epsilon))\). This reduction in complexity combined with the catalytic nature of the phase gradient state makes this approach to gate synthesis highly resource efficient.

from pennylane.labs.transforms import select_pauli_rot_phase_gradient

prec = 1e-9 #Desired Accuracy
b = int(np.ceil(np.log2(1/prec))) #Gradient Register Size

#Define Auxiliary Wires for Phase Gradient Transformation
reg = qp.registers({
    "_reserved": n + 1,   #Don't overwrite the previously defined wires!
    "angle":     b,
    "gradient":  b,
    "work":      3 * b,
})
angle_wires    = reg["angle"]
gradient_wires = reg["gradient"]
work_wires     = reg["work"]

@qp.qnode(dev)
@select_pauli_rot_phase_gradient(angle_wires,gradient_wires,work_wires)
def circuit_phase_grad():
  for wire in data_wires:
    qp.Hadamard(wire)
  qp.SelectPauliRot(angles, data_wires, target_wire, rot_axis="Y")
  return qp.probs(target_wire)

print(qre.estimate(circuit_phase_grad)())

--- Resources: ---
 Total wires: 183
   algorithmic wires: 154
   allocated wires: 29
     zero state: 29
     any state: 0
 Total gates : 855
   'Toffoli': 37,
   'CNOT': 525,
   'X': 136,
   'Z': 1,
   'S': 2,
   'Hadamard': 154

Note that there are different ways to translate Toffoli gates (which are continuous) into T gate counts, but here we will take Gidney’s approximation of 1 Toffoli gate = 4 T gates [1], meaning this implementation requires an estimated 148 T gates. So, for the same task with the same goal, this operation has now reduced in T gate cost by more than half. Not too shabby!

The scale of these savings becomes increasingly clear as the size of the data register that stores the input state (and, therefore, the size of the system as a whole) increases. The plot below shows how drastically the resource requirements scale in the first case with even a small increase in system size.

Though the phase gradient approach requires an investment of resources to prepare the gradient register, the additive, multiplexed nature of the rotation procedure results in a very slow accumulation of resources, as elaborated below. It is, of course, important to acknowledge that the implementation of the phase gradient state requires additional qubits to be added to the system. Though this contributes to resource cost, the comparative cost of generating a usable T gate still outweighs this investment in the long run. Thus, even though this approach requires an upfront investment of resources, it pays off in the long-run as additional per-rotation costs accumulate much more slowly than in alternative methods.

Sizing Up Other Optimizations

The importance of cheaply decomposing arbitrary rotations has been known to the industry for some time. As a result, the phase gradient approach is not the only gate-synthesis strategy available in the quantum algorithmic toolkit. There are many nuances involved in asserting the ideal applications of each algorithm, but a full exploration will not be included here. Instead, comparing the per-rotation gate cost reveals the relative cost of each strategy, which must be weighed against the nuance of the specific application. Note that, for a QFT, \(R=N^2/2\).

Though this comparison shows the comparatively low cost of the multiplexed phase gradient approach, it leaves a hanging question: why not just multiplex every method? QROM can, of course, be used to load states into a register in any computationally compatible scenario, but the fact that the phase gradient state is catalytic and accessible in a pre-configured register is what makes this efficient multiplexing approach possible. If the phase gradient state were destroyed each time it was applied to a state, it would be impossible to effectively carry out a simultaneous rotation on a register. Trying to multiplex a GridSynth process, for example, would require the simultaneous execution of gate sequences that vary with the control qubit states. This would cause the depth of the multiplexed operation to explode, eliminating any potential advantage. So, while phase gradients are expensive to prepare, they give us the luxury of a simple look-up table style approach.

Conclusion

Phase gradient states are becoming more and more present in state-of-the-art algorithms, such as dynamic simulations. When it comes to developing useful applications for the future’s quantum computers, it is crucial to keep in mind what resources will be required so that compatibility with hardware and physical systems remains reasonable. As emphasized, the additive nature of using phase gradient states for this application greatly reduces the T count of applying arbitrary rotations. Understanding of the theory behind phase gradient states and the role they can play in carrying out efficient rotations opens the door to several compilation tools in PennyLane. The phase gradient page in PennyLane’s compilation hub is the best place to go to learn more. The tools available can be applied to a plethora of applications. Give them a try the next time you are experimenting with quantum phase estimation, for example!

References