Phase gradient

Extending on the implementations of rotations and controlled rotations with phase gradients, we are going to look at multiplexed rotations, implemented in PennyLane as qp.SelectPauliRot. As we saw in the resource comparison in the overview tab, it is such "groups" of rotations where the phase gradient stands out and improves over standard decompositions–if enough work wires are available. The construction is very similar to the one for controlled rotations when attaching the control node to the fanout, i.e., the subcircuit that loads the angle.

We start with the implementation of an R_Z rotation:

|ψ>    : ───────╭○────────────╭○────────┤  ≈R_Z(θ)|ψ>
|0>    : ─╭load─│──╭SemiAdder─│──╭load†─┤   |0>
|0>    : ─├load─│──├SemiAdder─│──├load†─┤   |0>
|0>    : ─╰load─├──├SemiAdder─├──╰load†─┤   |0>
      ╭: ───────├X─├SemiAdder─├X────────┤ ╮
|∇_b> ┤: ───────├X─├SemiAdder─├X────────┤ ├ |∇_b>
      ╰: ───────╰X─╰SemiAdder─╰X────────┤ ╯

Now, we would like to implement the multiplexed version of this circuit, with M rotation angles \{\theta_j\}_{j=0}^{M-1} about the Z-axis. For m=3 multiplexing qubits, this looks as follows,

      ╭: ─╭◻───────┤ ╮
|ψ>   ┤: ─├◻───────┤ ├ =MUX-R_Z(θ_j)|ψ>
      │: ─├◻───────┤ │
      ╰: ─╰RZ(θ_j)─┤ ╯.

We can implement this simply by attaching the multiplexing nodes to each constituent in the circuit above, due to the multiplexer extension property (MEP). The SemiAdder and its controlled modification into a subtractor are static gates, so multiplexing does not modify them. This leaves us with multiplexing nodes attached to the angle loading routines:

      ╭: ─╭◻──────────────────────────╭◻──────────┤ ╮
|ψ>   ┤: ─├◻──────────────────────────├◻──────────┤ ├≈MUX-R_Z(θ_j)|ψ>
      │: ─├◻──────────────────────────├◻──────────┤ │
      ╰: ─│──────────╭○────────────╭○─│───────────┤ ╯
|0>    : ─├load(θ_j)─│──╭SemiAdder─│──├load†(θ_j)─┤   |0>
|0>    : ─├load(θ_j)─│──├SemiAdder─│──├load†(θ_j)─┤   |0>
|0>    : ─╰load(θ_j)─├──├SemiAdder─├──╰load†(θ_j)─┤   |0>
      ╭: ────────────├X─├SemiAdder─├X─────────────┤ ╮
|∇_b> ┤: ────────────├X─├SemiAdder─├X─────────────┤ ├ |∇_b>
      ╰: ────────────╰X─╰SemiAdder─╰X─────────────┤ ╯

We thus obtained a multiplexed loading circuit, or QROM, quite similar to the controlled rotation implementation that attached control nodes to the loading stage. The further decomposition of this circuit thus is also very similar, but with a T gate overhead that is linear in the number M of angles that are implemented with the multiplexer, not in the number of multiplexing nodes. The auxiliary qubit count does grow with the number of multiplexing nodes, and thus logarithmically with the number of angles. This is achieved via unary iteration, a technique for multiplexers, also known as Select operators. Complementary and alternative optimizations such as partial Select and lazy Select, respectively, are available as well.

The precise T cost of one QROM is given by 4(m+M-\ell(M,m)-2), where

is a non-negative integer that takes the precise structure of unary iteration into account.

Like for the controlled rotations, we can cancel the last right elbows of the first loader with the first left elbows of the second loader when compiling the full circuit, removing 4(m-1) T gates. Overall, this leads to an overhead of multiplexing over a single rotation of 4(m+2M-2\ell(M,m)-3).

The total T cost for an m-multiplexed R_Z rotations of M angles represented with a precision of b bits is thus

If the number of angles is at the maximum of M=2^m for m multiplexing qubits, we have \ell(M,m)=m+1 and this T count becomes 4(b+2M-m-6).