You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This document will describe the trick for arbitrary state prepration from
Section IV of Shende et al. (This is necessary to implement in the Qwerty
compiler to support superposition literals.)
Surprisingly, the overall idea of the algorithm is based on un-computing the
desired state, qubit-by-qubit. It starts with uncomputing the rightmost qubit
back to $\ket{0}$, then uncomputes the next-to-rightmost qubit back to
$\ket{0}$, and so on until you have $\ket{0}^{\otimes n}$. Then you can run the
circuit that accomplishes this uncomputation backwards to compute the desired
state! I describe the algorithm in more detail below.
I. Algorithm
Input: A vector $\ket{\psi}$ of dimension $2^n$, where $n \ge 1$
Output: A circuit (list of gates) which performs a $2^n{\times}2^n$ unitary
$U$ such that $U\ket{0}^{\otimes n} = \ket{\psi}$.
Steps:
Run the Undo subroutine on $\ket{\psi}$
Reverse the order of gates output by Undo, take the adjoint of each one, and
return them
A. Undo Subroutine
Input: A vector $\ket{\psi}$ of dimension $2^n$, where $n \ge 1$
Output: A circuit (list of gates) which un-computes $\ket{\psi}$
back to zero. Specifically, the product of the gates it returns is a
$2^n{\times}2^n$ unitary $U'$ such that $U'\ket{\psi} = \ket{0}^{\otimes n}$.
Steps:
If $n=1$, then use the procedure described above in Section 2B to calculate
$\phi$ and $\theta$. Emit the gate $W^\dagger(\theta,\phi)$ (defined in
Section 2C).
If $n>1$:
For each $j \in {0,1,\ldots,2^{n-1}-1}$,
Compute $\theta_j$, $\phi_j$, $r_j$, and $\gamma_j$ as described in Section 2D
Emit $(n-1,j)$-controlled $W^{\dagger}(\theta_j,\phi_j)$. (See Section 2A
for what I mean by $(n,j)$-controlled.)
Create a new $2^{n-1}$-dimensional vector
$\ket{\psi'} = \sum_{j=0}^{2^{n-1}-1} r_j e^{i \gamma_j}\ket{j}$.
Recurse on $\ket{\psi'}$.
II. Notation and Lemmas
Otherwise, gates are defined as in Section 4.2 of Nielsen and Chuang ("Mike and
Ike"), which also matches the QCirc dialect definitions.
A. Controlling on a Bitstring
You are probably familiar with the notation $CU$, which denotes a version of
$U$ that is controlled on the left. For example, $CX$ performs the following
operation:
You could also have an operation like $cCcX$, which flips the rightmost bit
only when the first three bits are $010$. I will refer to a generalized case of
this as $(n,j)$-controlled $U$. This represents performing $U$ on the
rightmost qubits if and only if the leftmost $n$ qubits match the $n$-bit
binary form of $j$. For example, $(3,2)$-controlled $X$ is exactly $cCcX$
because $2$ is written $010$ in three-bit binary.
In this document, I may write $(n,j)$-controlled $U$ as ${C^{(n,j)}}U$ to save
some space.
As an additional note, to accomplish $cCcX$ in an IR that supports only $CCCX$
(such as the QCirc MLIR dialect), you can perform
$(X\otimes I\otimes X \otimes I)CCCX(X\otimes I\otimes X \otimes I)$.
B. Parameterization of an Arbitrary Single-Qubit State
Recall a qubit state $\ket{\psi}$ is defined as $\alpha\ket{0} + \beta\ket{1}$
where the complex amplitudes $\vert\alpha\vert^2 + \vert\beta\vert^2 = 1$.
One parameterization of this state can be written as
$\ket{\psi} = e^{i\gamma}(e^{-i\phi/2} \cos(\theta/2)\ket{0} + e^{i\phi/2} \sin(\theta/2)\ket{1})$, where
the parameters $\gamma$, $\theta$, and $\phi$ are real. $\gamma$ is the global
phase and $\phi$ is the relative phase.
Computing these three parameters given $\alpha$ and $\beta$ isn't too bad. You
can find $\gamma$ with $(\text{arg}(\alpha) + \text{arg}(\beta))/2$. Then if
$\alpha \ne 0$, one can compute $\phi = 2(\gamma - \text{arg}(\alpha))$. Or if
$\beta \ne 0$, then $\phi = 2(\text{arg}(\alpha) - \gamma)$ will work instead.
Finally, you can calculate $\theta = 2\arccos(\vert \alpha \vert)$.
C. Preparation of an Arbitrary Single-Qubit State
If you know the $\phi$ and $\theta$ in the parameterization in Section 2B, you
can prepare $\ket{\psi}$ with the following tiny circuit:
$e^{i\gamma}R_z(\phi)R_y(\theta)\ket{0} = \ket{\psi}$. This is easy to verify.
Henceforth, I will define $W(\theta,\phi) = R_z(\phi)R_y(\theta)$. Note that
$W^\dagger(\theta,\phi)\ket{\psi} = e^{i\gamma}\ket{0}$, i.e., it can be used
to uncompute too.
D. Crazy Factoring of a Multi-Qubit State
Imagine $\ket{\psi}$ is an $n$-qubit state where $n > 1$. Then you can do the
following insane linear algebra:
Hopefully you can see that each term in the sum) has its own qubit-like space.
Given two adjacent amplitudes $\alpha_{2j}$ and $\alpha_{2j+1}$ in the
statevector, you can compute $r_j$ with
$r_j = \sqrt{\vert \alpha_{2j} \vert^2 + \vert \alpha_{2j+1} \vert^2}$. If
you set $\alpha_{2j}' = \alpha_{2j}/r_j$ and $\alpha_{2j+1}' = \alpha_{2j+1}/r_j$,
then you can calculate the other parameters ($\gamma_j$, $\theta_j$, and
$\phi_j$) as described in Section 2B if you treat $\alpha_{2j}'$ as $\alpha$
and $\alpha_{2j+1}'$ as $\beta$.
E. Multiplexed Ry and Rz Decomposition
This subsection describes how to decompose an $R_y$ that is multiplexed on a
single qubit. The definition of a multiplexed $R_y$ is equivalent to any of the
following (take your pick!):
Now, we can observe that each of these pairs of z-rotation and phase gates are
happening in orthogonal subspaces, so these pairs commute with each other. In
fact, as long as we make sure the relative phase gates happen after the
z-rotation gates, we can rearrange this as the following:
Why is this interesting? Well, it turns out that each of the parenthesized
products are block diagonal, so I can rewrite the last expression as follows:
Shende et al. call each of these matrices quantum multiplexers. I found this
name counterintuitive at first, but regardless, they describe an amazing
optimization for lowering these so-called multiplexers to CNOTs and $R_y$
gates.
B. Efficient Multiplexed Ry Decomposition
Let's focus on the multiplexed $R_y$ for a moment, first rewriting it with
Dirac notation (below, $k0$ means the bits of $k$ with a $0$ appended on the end):
We can make a crucial observation here: both CNOTs seen in the sum above are
running in all $2^{n-2}$ subspaces. So why bother controlling them? If a more
matrix-based argument helps your intuition, hopefully this equality is clear:
Those two remaining sum terms are themselves $R_y$ multiplexors, except with
one fewer control qubit! Thus, this math forms the basis for a recursive
algorithm. The base case is simply an $R_y$ gate.
Algorithm
Input: A positive number of qubits $n$, a list of $n$ qubit indices to
operate on, and a list of rotation angles for a multiplexed $R_y$:
$\theta_0,\theta_1,\ldots,\theta_{2^{n-1}-1}$
Output: A circuit (list of gates) which performs a multiplexed $R_y$
Steps:
If $n=1$, emit $R_y(\theta_0)$.
Else:
Calculate a new list of $2^{n-2}$ rotation angles. For
$k=0,1,\ldots,2^{n-2}-1$, set $\theta_k' = (\theta_{2k} + \theta_{2k+1})/2$.
Recurse with number of qubits $n-1$, the list of qubits excluding the
second-to-last qubit, and
$\theta_0',\theta_1',\ldots,\theta_{2^{n-2}-1}'$ as the rotation angles.
Emit a CNOT with control $n-2$ and target $n-1$
Calculate a new list of $2^{n-2}$ rotation angles. For
$k=0,1,\ldots,2^{n-2}-1$, set $\theta_k'' = (\theta_{2k} - \theta_{2k+1})/2$.
Recurse with number of qubits $n-1$, the list of qubits excluding the
second-to-last qubit, and
$\theta_0'',\theta_1'',\ldots,\theta_{2^{n-2}-1}''$ as the rotation angles.
Emit another CNOT with control $n-2$ and target $n-1$
This works equivalently if you replace every $\theta_j$ with $\phi_j$ and every
$R_y$ with $R_z$.
D. Overall Changes to Original Algorithm
That was a lot. So it's time to summarize.
The main change this optimization makes to the state preparation algorithm is
how the Undo subroutine (Section 1A) behaves. Instead of emitting
${C^{(n-1,j)}} {W^\dagger} ({\theta_j},{\phi_j})$ gates directly, the undo subroutine
should return two lists of angles:
$\theta_0,\theta_1,\ldots,\theta_{2^{n-1}-1}$ and
$\phi_0,\phi_1,\ldots,\phi_{2^{n-1}-1}$. Call these $\vec{\theta_n}$ and
$\vec{\phi_n}$ respectively. We can then rewrite Section 1 as follows:
Revised Overall Algorithm
Input: A vector $\ket{\psi}$ of dimension $2^n$, where $n \ge 1$
Output: A circuit (list of gates) which performs a $2^n{\times}2^n$ unitary
$U$ such that $U\ket{0}^{\otimes n} = \ket{\psi}$.
Steps:
Run the Undo subroutine on $\ket{\psi}$
For each $i \in {1,2,\ldots,n}$:
Run the multiplexed $R_y$ synthesis algorithm in Section 3B with number
of qubits $i$, list of qubits $0,1,\ldots,i-1$, and angles $\vec{\theta_i}$
Run the multiplexed $R_z$ synthesis algorithm in Section 3B with number
of qubits $i$, list of qubits $0,1,\ldots,i-1$, and angles $\vec{\phi_i}$
Revised Undo Subroutine
Input: A vector $\ket{\psi}$ of dimension $2^n$, where $n \ge 1$
Output: Stores lists of angles for multiplexed rotations in
$\vec{\theta_n}$ and $\vec{\phi_n}$
Steps:
If $n=1$, then use the procedure described above in Section 2B to calculate
$\phi$ and $\theta$. Set $\vec{\theta_1} = \theta$ and $\vec{\phi_1} = \phi$.
If $n>1$:
For each $j \in {0,1,\ldots,2^{n-1}-1}$,
Compute $\theta_j$, $\phi_j$, $r_j$, and $\gamma_j$ as described in Section 2D
Set $\vec{\theta_n} = \theta_0,\theta_1,\ldots,\theta_{2^{n-1}-1}$
and $\vec{\phi_n} = \phi_0,\phi_1,\ldots,\phi_{2^{n-1}-1}$
Create a new $2^{n-1}$-dimensional vector
$\ket{\psi'} = \sum_{j=0}^{2^{n-1}-1} r_j e^{i \gamma_j}\ket{j}$.
Recurse on $\ket{\psi'}$.