Quantum State Preparation Using an Exact
CNOT Synthesis Formulation

Hanyu Wang

{}^{1}

, Bochen Tan

{}^{2}

, Jason Cong

{}^{2}

, and Giovanni De Micheli

{}^{3}

{}^{1}

ETH, Zurich, Swizterland,

{}^{2}

UCLA, California, United States,

{}^{3}

EPFL, Lausanne, Swizterland

Abstract

Minimizing the use of CNOT gates in quantum state preparation is a crucial step in quantum compilation, as they introduce coupling constraints and more noise than single-qubit gates. Reducing the number of CNOT gates can lead to more efficient and accurate quantum computations. However, the lack of compatibility to model superposition and entanglement challenges the scalability and optimality of CNOT optimization algorithms on classical computers. In this paper, we propose an effective state preparation algorithm using an exact CNOT synthesis formulation. Our method represents a milestone as the first design automation algorithm to surpass manual design, reducing the best CNOT numbers to prepare a Dicke state by 2 $\times$ . For general states with up to 20 qubits, our method reduces the CNOT number by 9% and 32% for dense and sparse states, on average, compared to the latest algorithms.

I Introduction

Quantum states preparation (QSP) is essential for compiling quantum algorithms [childs2000finding], implementing quantum communications [ben2005fast], studying quantum metrology [toth2012multipartite], and experimenting with quantum entanglement [horodecki2009quantum]. For decades, researchers have based QSP circuit designs on mathematical derivation [cruz2019efficient, bartschi2019deterministic, mukherjee2020preparing, aktar2022divide] and created them manually. Although efficient, the derived properties are specialized to a certain class of highly symmetric states, e.g., GHZ states [greenberger1989going], W states [dur2000three], and Dicke states [dicke1954coherence], and cannot be generalized.

Limitations of manual designs point us to the need to develop design automation algorithms. Recent works propose Boolean methods utilizing decision diagrams to prepare general $n$ -qubit states using $\mathcal{O}(2^{n})$ CNOT gates [araujo2021divide, mozafari2019preparation, niemann2016logic]. By leveraging sparsity, the latest studies improve the efficiency and develop algorithms to prepare $n$ -qubit with $m$ nonzero amplitudes using $\mathcal{O}(mn)$ CNOT gates [gleinig2021efficient, mozafari2022efficient, malvetti2021quantum]. However, these methods sacrifice optimality for efficiency, consuming more CNOT gates than manual designs.

The challenges of solving QSP on classical computers are the complexities of modeling superposition and entanglement [nielsen2010quantum]. Indeed, while classical computers store binary information, compute Boolean operators, and retrieve a single binary output, quantum computing processes high-dimensional state vectors with complex amplitudes that evolve with matrix multiplications. With superposition, the dimension of state vectors grows exponentially with the number of qubits. Therefore, only certain families of quantum states can be efficiently encoded using classical bits [aaronson2004multilinear, raz2009multi]. Besides, because of entanglement, the qubits in the states are inseparable. As a result, developing an effective divide-and-conquer approach for QSP problems is difficult.

In this paper, we propose an exact CNOT synthesis formulation for QSP. Our method encodes quantum states and gates on a graph and formulates QSP as a shortest path problem. Given an arbitrary quantum state and a library of available gates, our formulation provides full visibility of the solution space and is guaranteed to find the optimal circuit with minimal CNOT gates. For general states with up to $20$ qubits, our method reduces the CNOT number by $9\%$ and $32\%$ for dense and sparse states, on average, compared to the latest algorithms. Besides, our method represents a milestone as the first design automation algorithm to surpass manual design, reducing the best CNOT numbers to prepare a Dicke state by $2\times$ .

In the rest of the paper, we present the background in Section II and show an example to motivate our work in Section III. Then, we illustrate our shortest path problem formulation for QSP in LABEL:sec:formulation and introduce our specialized shortest path algorithm in LABEL:sec:algorithm. In LABEL:sec:evaluation, we demonstrate experimental results and evaluate our method.

II Background

In this section, we provide background for quantum state preparation. For clarity and space constraints, we refer readers to established sources for formal definitions of notations [nielsen2010quantum] and quantum gates[barenco1995elementary].

II-A Quantum States and Quantum Gates

We express the $n$ -qubit quantum state as a linear combination of $2^{n}$ orthonormal basis vectors.

\ket{\psi}=\sum_{x\in S(\psi)}c_{x}\ket{x},\,\text{and}\,\sum_{x\in S(\psi)}|c_{x}|^{2}=1,

where $\ket{x}\in\{0,1\}^{n}$ is the basis state, $c_{x}\in\mathbb{C}$ are amplitudes whose norm indicates the probability of observing $\ket{x}$ , and $S(\psi)$ is the index set, which represents the set of basis with nonzero amplitudes. The cardinality of a state $\psi$ is the number of elements in its index set, $|S(\psi)|$ .

Quantum gates, or operators, denoted by $U$ , are unitary matrices representing transitions between quantum states. $\mathcal{U}(2^{n})$ represents the set of all $n$ -qubit gates. This paper studies states with real amplitudes and restricts state transitions in the X-Z plane. Therefore, all single-qubit unitary matrices, $U\in\mathcal{U}(2)$ , are Y rotations, $\text{R}_{y}$ , and all multi-qubit operators can be decomposed into gates in $\{\text{CNOT},\text{R}_{y}\}$ .

U=\begin{pmatrix}a&-b\\ b&a\end{pmatrix}=\begin{pmatrix}\cos\frac{\theta}{2}&\sin\frac{\theta}{2}\\ -\sin\frac{\theta}{2}&\cos\frac{\theta}{2}\end{pmatrix}=\text{R}_{y}(\theta),

(1)

where $a$ and $b$ are real numbers satisfying $a^{2}+b^{2}=1$ and $\theta$ is a rotation angle that satisfies $\theta=-2\cdot\arctan\frac{b}{a}$ .

We define CNOT cost of an operator $U$ as the number of CNOT gates to decompose $U$ . Quantum gates involved in this paper and their costs are listed in Section II-A, including Y rotations (R ${}_{y}$ ), CNOT, and multi-controlled Y rotations (MCR ${}_{y}$ ) gates. Note that the CNOT cost depends on the decomposition algorithm and the number of ancillary qubits [maslov2016advantages, mottonen2004quantum, saeedi2013linear]. This paper assumes an MCR ${}_{y}$ gate with $n$ control qubit has a CNOT cost of $2^{n}$ .

TABLE I: Selected quantum gates with their CNOT costs.

Operators

{}_{y}

CNOT

{}_{y}

MCR

{}_{y}

\Qcircuit@C=.3em @R=.5em
	\gateR_y	\qw

& \Qcircuit@C=.3em @R=.5em \ctrl1 \qw \targ \qw \Qcircuit@C=.3em @R=.5em \ctrl1 \qw \qw \Qcircuit@C=.3em @R=.5em \ctrl1 \qw \ctrl1 \qw \gateR_y \qw CNOT cost 0 1 2 $\mathcal{O}(2^{n})$ [mottonen2004quantum]

II-B Quantum Circuits for State Preparations

Given a state $\ket{\psi}$ and a set of quantum gates $\mathcal{L}$ , the quantum state preparation finds a quantum circuit comprising $l$ gates $U_{1},U_{2},...U_{l}\in\mathcal{L}$ such that these gates map the ground state $\ket{0}$ to the desired state $\ket{\psi}$ , i.e., $\ket{\psi}=U_{l}...U_{2}U_{1}\ket{0}$ . For noisy intermediate-scale quantum (NISQ) computers, CNOTs introduce more noise than single-qubit gates. Therefore, the objective of QSP is to minimize the CNOT cost of the circuit, which is the sum of the gates’ CNOT costs.

III Motivating Example

Consider the problem of preparing the state $\psi$ , with $\ket{\psi}=\frac{1}{\sqrt{4}}(\ket{000}+\ket{011}+\ket{101}+\ket{110})$ which comprises three qubits with a cardinality of four. We demonstrate the quantum circuits generated by two categories of existing methods.

The first category of methods use qubit reduction [mozafari2019preparation, araujo2021divide]. These methods focus on one target qubit at each stage and apply MCR ${}_{y}$ gates to separate it from the entanglement. As illustrated in Figure 1, the gates in the solid box separate $q_{3}$ , and the gates in the dashed box separate $q_{2}$ . The dashed and solid boxes have 1 and 2 control qubits, respectively, and require $2^{1}\!+\!2^{2}\!=\!6$ CNOT gates.

\Qcircuit@C=.7em @R=1em \lstickq_1: —0⟩ \gateR_y(π2) \ctrlo1 \ctrl1 \ctrlo1 \ctrl1 \qw\gategroup1324.5em–\gategroup1536.5em- \lstickq_2: —0⟩ \qw \gateR_y(π2) \gateR_y(π2) \ctrl1 \ctrlo1 \qw \lstickq_3: —0⟩ \qw \qw \qw \gateR_y(π) \gateR_y(π) \qw

Figure 1: 6-CNOT circuit using the qubit reduction method.

Other related works perform cardinality reduction [gleinig2021efficient]. This method iteratively selects two different basis vectors from the index set and merges them using CNOT and controlled rotation gates. As depicted in LABEL:fig:cardinality-reduction, the circuit strictly reduces cardinality by one after each “merging” from right to left until $|S|=1$ , which is the ground state, $\ket{000}$ . This circuit contains a single-qubit gate, three CNOTs, and two controlled Y-rotation gates. Therefore, the CNOT cost is $3\!\times\!1\!+\!2\!\times\!2\!=\!7$ .

\Qcircuit@C=.7em @R=1em \lstickq_1: —0⟩ \gateR_y(