PCPhase decomposition

David Wierichs

Compilation/
PCPhase decomposition

PCPhase decomposition

Here we will explain the decomposition of projector-controlled phase gates (qml.PCPhase) in more detail.

PCPhase and PhaseShift gates

Before we find the procedure to decompose PCPhase gates into (multi-controlled) PhaseShift gates, let's look at their properties first. In particular, we will be concerned with the gate generators.

The generator of PCPhase is given by

G = 2 \left(\sum_{j=0}^{d-1} |j\rangle\langle j|\right) - \mathbb{I}_N = \text{diag}( \underset{d\text{ times}}{\underbrace{1, \dots, 1}}, \underset{(N-d)\text{ times}}{\underbrace{-1, \dots, -1}} ),

where we denoted the overall dimension as $N=2^n$ for $n$ qubits and the subspace dimension as $d$ , which is called dim in code. Our first step is to move to a slightly different convention in order to arrive at a projector that has ones and zeros, instead of ones and minus ones (note how $G$ is not a projector because $G^2=\mathbb{I}_N\neq G$ ). To do this, we define

\Pi = \begin{cases} \sum_{j=0}^{d-1} |j\rangle\langle j| & \text{for }\ d\leq \tfrac{N}{2}\\ \sum_{j=d}^{N-1} |j\rangle\langle j| & \text{for }\ d> \tfrac{N}{2} \end{cases},

so that $G=2\Pi -\mathbb{I}_N$ for $d\leq \tfrac{N}{2}$ and $G=\mathbb{I}_N - 2 \Pi$ for $d>\tfrac{N}{2}$ . We may summarize this as $G=\sigma (2\Pi -\mathbb{I}_N)$ with the sign $\sigma=\pm 1$ defined accordingly for the two cases.

Next, let's look at the generator of a multi-controlled PhaseShift gate, where the controls are on the more significant qubits than the target. The generator of a simple PhaseShift gate is

G_{\text{phase}} = \text{diag}(0, 1).

Attaching a control node that is active on the $|0\rangle$ state will append a block of zeros to the generator,

G_{|0\rangle-\text{phase}} = \text{diag}(0, 1, 0, 0),

whereas attaching a control that is active on the $|1\rangle$ state prepends such a block,

G_{|1\rangle-\text{phase}} = \text{diag}(0, 0, 0, 1).

This process can then be repeated, appending or prepending a block of zeros of the same size as the gate, or generator, that we attach the control to. As with any gate, if there are additional (less significant, for our case) qubits that a (multi-controlled) phase shifts does not act on, its generator is tensored with the identity matrix. For example, the generator of a doubly-controlled PhaseShift gate controlled on the state $|01\rangle$ , used in a circuit on $4$ qubits, takes the form

G^{n=4}_{|01\rangle-\text{phase}} = \text{diag}(0, 0, 0, 1, 0, 0, 0, 0) \otimes \mathbb{I}_2

\phantom{G^4_{|01\rangle-\text{phase}}} = \text{diag}(0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0).

Note that the projector $\Pi$ obtained from the generator of PCPhase has $\text{min}(d, N-d)$ consecutive entries that are $1$ , and that the generator of a $i$ -fold controlled PhaseShift on $n$ qubits is a projector, too, and has $2^{n-1-i}$ consecutive entries that are $1$ .

Generator decomposition

Our task is now to decompose the projector $\Pi$ , introduced above, into sums and differences of (multi-controlled) PhaseShift projectors. This means that we will decompose $d$ (or $N-d$ , if that is smaller; we'll assume $d<N-d$ for simplicity from here on) into powers of two, allowing for addition or subtraction.

This subproblem has a neat solution, which is based on this post on stack overflow, and implemented in qml.math.decomposition.decomp_int_to_powers_of_two in PennyLane.

This function provides us with the decomposition

d = \sum_{i=0}^{n-1} c_i 2^{n-1-i}, \quad c_i\in\{-1, 0, 1\}

and it is known that the number of non-zero $c_i$ can be computed as $\|d\oplus (3d)\|$ (OEIS sequence A007302) with $\| \cdot \|$ denoting the Hamming weight and $\oplus$ denoting bitwise XOR. Note that we use zero-based indexing.

Now, we want to use this decomposition to combine projectors onto $2^{n-1-i}$ consecutive computational basis states into the desired $\Pi$ :

\Pi = \sum_{i=0}^{n-1} c_i \sum_{j=s_i}^{e_i} |j\rangle\langle j|,

where $s_i$ and $e_i$ are the start and end positions for the $i$ -th contribution to $\Pi$ . This decomposition works via simple addition and subtraction of the gate generators, because they all are diagonal, and thus commute.

Besides computing the integer decomposition itself, the algorithm in the compute_decomposition method of qml.PCPhase is mostly concerned with figuring out the right control structure to realize the correct positioning according to $s_i$ and $e_i$ .

To begin, we initialize empty lists of control wires and control values, corresponding to $s_0=0$ . Then, starting at $i=0$ , which also marks the current wire, we go through the integer decomposition $\{c_i\}$ from above and perform the following steps:

If $c_i=0$ , go to step 2 immediately. Else, we want to add/subtract computational basis state projectors to the decomposition. The number of projectors $2^{n-1-i}$ is stored in the number of control wires that we already aggregated. In addition, $s_i$ (and thus $e_i$ ) is encoded in the control values, up to whether the projectors should be located in the $|0\rangle$ or $|1\rangle$ subspace of the current target wire $i$ . If we want to add projectors ( $c_i=+1$ ), we append them at the beginning of the current subspace, so in the $|0\rangle$ subspace. If we want to remove projectors ( $c_i=-1$ ), we need to remove them from the end of the subspace, so from $|1\rangle$ . Having figured out the subspace, we add the corresponding projector to the decomposition. In code, we immediately apply the corresponding phase gate (see below).
Add the current wire $i$ to the control wires. The control value to be added depends on the current $c_i$ and on the next non-zero coefficient $d_i$ . For $d_i=+1$ , we are going to add more projectors, so we should control into the $|1\rangle$ subspace (add onto just added projectors for $c_i=+1$ , or re-add just removed projectors for $c_i=-1$ ) unless we have $c_i=0$ , in which case we did not just modify the decomposition and need to control into the $|0\rangle$ subspace instead. In either case, this sets $s_{i+1}$ to $e_i+1$ . For $d_i=-1$ , we will subtract projectors. If we just subtracted projectors (from the $|1\rangle$ subspace, $c_i=-1$ ), we need to remove further from the $|0\rangle$ subspace and control into it. If we just added projectors (to the $|0\rangle$ subspace), we remove some of those again, and need to control into the $|0\rangle$ subspace as well. For $c_i=0$ , we need to remove from the upper end, i.e., the $|1\rangle$ subspace. All of this is easily summarized: If the next non-zero coefficient, $d_i$ , is positive (negative), set the next control value to $1$ ( $0$ ). If the current coefficient is $c_i=0$ , flip the control value.
Increment $i$ by one. If $i=n$ , terminate, else go to step 1.

To conclude, we translate the projector decomposition back to (multi-controlled) PhaseShift gates, using the discussion from above. The sign of all phases is multiplied by $2\sigma$ to realize the first term of $G=\sigma(2\Pi -\mathbb{I}_N)$ , and a global phase with angle $\sigma\phi$ is added to realize the second term.

We close with the explicit calculation of the example from the overview page. Let $d=13$ and $n=4$ . As $2^n-d=3<13=d$ , we will be using $\sigma=-1$ and decompose $2^n-d=3$ into powers of two:

import pennylane as qml
print(qml.math.decomposition.decomp_int_to_powers_of_two(3, n=4))

[0, 1, 0, -1]

This realizes the decomposition

2^n-d=3=4-1 = 0\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 - 1\cdot 2^0,

which translates into the generator decomposition

\Pi = \text{diag}\begin{pmatrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix} =\text{diag}\begin{pmatrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}-\text{diag}\begin{pmatrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}.

We may read off that the first term is $G^{n=4}_{|1\rangle-phase}$ and the second term is $X_3 G^{n=4}_{|110\rangle-phase}X_3$ , where we need to use the Pauli- $X$ gates on the last qubit in order to make the phase shift act on the $|0\rangle$ state instead of the $|1\rangle$ state.

Finally, the angle for these gates is $2\sigma\phi$ and $-2\sigma\phi$ , respectively, and we include the global phase with angle $\sigma\phi$ . Altogether, this yields the decomposition we saw before:

phi = 1.45
op = qml.PCPhase(phi, d=13, wires=[0, 1, 2, 3])
print(qml.draw(op.decomposition)())

0: ──GlobalPhase(-1.45)─╭●────────╭●──────────┤
1: ──GlobalPhase(-1.45)─╰Rϕ(-2.9)─├●──────────┤
2: ──GlobalPhase(-1.45)───────────├○──────────┤
3: ──GlobalPhase(-1.45)──X────────╰Rϕ(2.9)──X─┤

About

Software & Documentation

Resources

Topics

Community & Support

PCPhase decomposition

PCPhase and PhaseShift gates

Generator decomposition