Abstract 1 Introduction 2 Preliminaries 3 SQSP without Ancillary Qubits 4 SQSP with 𝒎 Ancillary Qubits 5 Conclusion References

Nearly Optimal Circuit Size for Sparse Quantum State Preparation

Lvzhou Li ORCID Institute of Quantum Computing and Software, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, China Jingquan Luo ORCID Institute of Quantum Computing and Software, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, China
Abstract

Quantum state preparation is a fundamental and significant subroutine in quantum computing. In this paper, we conduct a systematic investigation of the circuit size (the total count of elementary gates in the circuit) for sparse quantum state preparation. A quantum state is said to be d-sparse if it has only d non-zero amplitudes. For the task of preparing an n-qubit d-sparse quantum state, we obtain the following results:

  • Without ancillary qubits: Any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(ndlogn+n) without using ancillary qubits, which improves the previous best results. It is asymptotically optimal when d=poly(n), and this optimality holds for a broader scope under some reasonable assumptions.

  • With limited ancillary qubits: (i) Based on the first result, we prove for the first time a trade-off between the number of ancillary qubits and the circuit size: any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(ndlog(n+m)+n) using m ancillary qubits for any mO(ndlognd+n). (ii) We establish a matching lower bound Ω(ndlog(n+m)+n) under some reasonable assumptions, and obtain a slightly weaker lower bound Ω(ndlog(n+m)+logd+n) without any assumptions.

  • With unlimited ancillary qubits: Given an arbitrary amount of ancillary qubits available, the circuit size for preparing n-qubit d-sparse quantum states is Θ(ndlognd+n).

Keywords and phrases:
Quantum computing, quantum state preparation, circuit complexity
Category:
Track A: Algorithms, Complexity and Games
Copyright and License:
[Uncaptioned image] © Lvzhou Li and Jingquan Luo; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Circuit complexity
; Theory of computation Quantum computation theory
Related Version:
Full Version: https://arxiv.org/abs/2406.16142 [30]
Funding:
Lvzhou Li and Jingquan Luo were supported by the National Key Research and Development Program of China (Grant No.2024YFB4504004), the National Natural Science Foundation of China (Grants No.92465202 and No.62272492), the Guangdong Provincial Quantum Science Strategic Initiative (Grant No.GDZX2303007), and the Guangzhou Science and Technology Program (Grant No.2024A04J4892).
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

Since the inception of quantum computing [14], an increasing number of quantum algorithms have emerged, exhibiting acceleration advantages over classical algorithms. Notable examples include Shor’s algorithm [55], Grover’s algorithm [20], HHL algorithm [22], and Hamiltonian simulation algorithms [10, 32, 33, 6], as well as quantum machine learning algorithms [31, 29, 28, 27, 47]. Within these algorithms, the preparation of quantum states plays a pivotal role. Usually, the first and inevitable step to process classical data by quantum algorithms is to encode the data into quantum states. If this step consumes substantial resources, it may offset the acceleration advantages of quantum algorithms. Several works have indicated that the substantial accelerations achieved by quantum machine learning stem from the underlying input assumptions [57, 9, 58, 8, 16]. Therefore, how to efficiently prepare quantum states is a fundamental and significant issue in the field of quantum computing.

Before delving into the discussion of quantum state preparation, it is essential to specify the elementary gate set and complexity metrics. In this paper, we adopt the most common gate set, which consists of single-qubit gates and CNOT gates, enabling the accurate implementation of any unitary transformation [3]. Additionally, for convenience, the Toffoli gate is permitted, which can be constructed using 10 single-qubit gates and 6 CNOT gates [42]. Various standards can be employed to gauge the efficiency of a quantum circuit, including size (the total count of elementary gates), depth (the number of layers such that gates in the same layer can be run in parallel), space (the number of ancillary qubits), and more. Given the considerably higher implementation cost of CNOT gates compared to single-qubit gates, the count of CNOT gates is also utilized as a measure of algorithmic efficiency.

When the quantum state to be prepared does not possess any structural features, we refer to it as the general quantum state preparation problem. This problem has already been extensively researched, and current preparation algorithms have achieved the optimal circuit size Θ(2n) [19, 52, 5, 44, 24]. Given the high cost of preparing general quantum states and the fact that, in practical applications, data often exhibits special structures, there has been considerable literature focusing on the preparation of special quantum states. These include states whose amplitudes are given by a continuous function [23, 18, 46, 36, 38, 40], states whose amplitudes are accessed through a black-box oracle [51, 4, 60], and states under the low-rank assumption [2]. Another class of quantum states that holds both practical and theoretical significance is sparse quantum states [17, 34, 45, 41, 13, 12, 64, 56, 35].

An n-qubit d-sparse quantum state refers to an n-qubit quantum state with d non-zero amplitudes. Given two positive integers n and 0<d2n, along with a set

𝒫={(αi,qi)}0id1 (1)

such that αi, qi{0,1}n for all 0id1, i|αi|2=1 and qiqj for all ij, the aim of sparse quantum state preparation (SQSP) is to generate a quantum circuit which acts on n+m qubits and implements a unitary operator U satisfying

U|0n|0m=i=0d1αi|qi|0m, (2)

where m0 is an integer and the last m qubits serve as ancillary qubits.

The importance of SQSP is self-evident, and the motivation is twofold:

  • First, many practically relevant states in quantum computing and processing have the property that only a small proportion of the basis states have nonzero coefficients. Some prominent examples of sparse states are W states, GHZ states, generalized Bell states, and thermofield double states [11].

  • Second, SQSP offers a finer-grained perspective on quantum state preparation. For the general quantum state preparation problem, the circuit size is proven to be Θ(2n), which does not consider the dependence on the parameter d. In other words, it simply assumes d=2n. A more fine-grained complexity should consider this dependence, and recover the general case when d=2n.

1.1 Contributions

In this paper, we conduct a systematic investigation of the circuit size of sparse quantum state preparation, exploring the three scenarios: without, with limited, and with unlimited ancillary qubits. The complexity notations O, Ω, o and ω will be explained in detail in Section 2.

1.1.1 SQSP without Ancillary Qubits

First, we consider the scenario of not using ancillary qubits.

Theorem 1.

Any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(ndlogn+n) without using ancillary qubits.

Previously, the best result without using ancillary qubits [17, 34] can only achieve the circuit size O(nd). We demonstrate for the first time that any n-qubit d-sparse quantum state can be prepared by a circuit of size o(nd) without using ancillary qubits. Moreover, in Theorem 7 we will see that the upper bound O(ndlogn+n) is asymptotically optimal when d=poly(n), and in Theorem 4 we get the lower bound Ω(ndlogn+n) when m=0, which indicates that the upper bound is asymptotically optimal when d2δn for a sufficiently small constant δ(0,1) under reasonable assumptions.

1.1.2 SQSP with 𝒎 Ancillary Qubits

Next, we consider the scenario of using m ancillary qubits. To the best of our knowledge, we are the first to consider and demonstrate the trade-off between the number of ancillary qubits and the circuit size of SQSP. Based on Theorem 1, we obtain the following theorem:

Theorem 2.

For any mO(ndlognd+n), any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(ndlog(m+n)+n) using m ancillary qubits.

 Remark 3.

In Theorem 2, when m=Θ(ndlognd+n), we get O(ndlognd+n) on the circuit size. Actually, more ancillary qubits than Θ(ndlognd+n) are useless for reducing the upper bound O(ndlognd+n). Otherwise, it would contradict the fact that the number of ancillary qubits must be asymptotically less than or equal to the circuit size. Since only one-qubit gates and CNOT gates are considered as elementary quantum gates here, if the number of ancillary qubits is more than twice as much as the circuit size, there must exist unused ancillary qubits. Therefore, without loss of generality, we can assume that mO(ndlognd+n).

We demonstrate that the upper bound established in Theorem 2 is tight under reasonable assumptions. Notice that all sparse quantum state preparation methods proposed so far use at most O(d) arbitrary-angle single-qubit rotation gates (i.e., Rx(θ), Ry(θ), Rz(θ)). For example, in permutation-based algorithms [34, 45], arbitrary-angle single-qubit rotation gates are only used in the first step to prepare a logd-qubit quantum state, while in the second step, implementing a permutation only involves CNOT gates and O(n) specific types of single-qubit gates. We believe that using ω(d) arbitrary-angle single-qubit rotation gates is pointless.

Theorem 4.

Suppose d2ϵn for a sufficiently small constant ϵ(0,1), and given m ancillary qubits available, if an algorithm 𝒜 for preparing n-qubit d-sparse quantum states satisfies the following conditions:

  1. 1.

    𝒜 uses at most O(d) single-qubit rotation gates with arbitrary angles,

  2. 2.

    all other single-qubit gates amount to a total of O(n) types,

then 𝒜 requires Ω(ndlog(m+n)+n) elementary quantum gates in the worst case.

More specifically, excluding rotation gates with arbitrary angles, the single-qubit gates considered in Theorem 4 include NOT gates and Phase(±π/2j) gates for 1jn, where the latter are useful for implementing an n-Toffoli gate without ancillae [15].

 Remark 5.

When only m=poly(n) ancillary qubits are available, the lower bound in Theorem 4 is Ω(ndlogn+n), which can be achieved without ancillary qubits as shown in Theorem 1. Therefore, poly(n) ancillary qubits do not help in reducing the circuit size of SQSP under some reasonable assumptions.

Without any assumptions, we prove a slightly weaker lower bound on the circuit size as follows.

Theorem 6.

Given m ancillary qubits available, there exist n-qubit d-sparse quantum states such that any algorithm to prepare them requires Ω(ndlog(m+n)+logd+n) elementary quantum gates.

1.1.3 SQSP with Unlimited Ancillary Qubits

We provide a complete characterization of the circuit size for SQSP in the case where an unlimited number of ancillary qubits is available.

Theorem 7.

With unlimited number of ancillary qubits available, the circuit size for preparing n-qubit d-sparse quantum states is Θ(ndlognd+n). Furthermore, if d=poly(n), then the circuit size is Θ(ndlogn+n), which can be achieved without using ancillary qubits.

Proof.

According to Remark 3, it is sufficient to assume m=Θ(ndlognd+n) ancillary qubits available. Therefore, by setting m=Θ(ndlognd+n) in Theorem 6, we get the lower bound Ω(ndlognd+n), which can be achieved by Theorem 2.

Furthermore, if d=poly(n), then Θ(ndlognd+n) becomes Θ(ndlogn+n), which can be achieved without using ancillary qubits as shown in Theorem 1.

1.2 Proof Techniques

1.2.1 SQSP without Ancillary Qubits

The idea of SQSP without ancillary qubits proposed in this paper aligns with prior research [34, 45]. Given the state description 𝒫={(αi,qi)}0id1, initially a dense logd-qubit quantum state iαi|σ1(qi) is prepared, where σ is some permutation such that 0σ1(qi)d1. Subsequently, this state is transformed into the target quantum state iαi|qi by applying σ. The dense quantum state iαi|σ1(qi) can be prepared with a circuit of size O(d). Therefore, the primary contribution to circuit size arises from the second step, i.e., the implementation of the permutation σ. Prior works [34, 45] have adopted circuits of size O(nd) for implementing σ, which results in an overall circuit size of O(nd). In comparison, we develop a method for implementing σ with a size of O(ndlogn+n), as detailed in Lemma 8.

Lemma 8.

For any permutation σ𝔖2n, there exists a quantum circuit implementing σ of size O(nsize(σ)logn+nlogmin{size(σ),logn}) without using ancillary qubits.

In the above, 𝔖2n denotes the set of all permutations on {0,1}n, and size(σ) denotes the number of non-fixed points of a permutation σ (see the formal definition in Equation 5). Reversible circuits, which implement permutations, have been extensively studied in the literature [54, 7, 61, 50, 49, 48, 1, 63, 62, 37, 25]. Shende et al. [54] proposed a synthesis method for realizing a permutation σ𝔖n using a circuit of size O(n2n); a similar result was obtained in [7]. Saeedi et al. [50, 49] introduced cycle-based methods that reduced the circuit size in practice, although the asymptotic complexity remained unchanged. Significant improvements were later made independently by Zakablukov [63] and Wu and Li [62], who achieved an asymptotically optimal circuit size of O(n2nlogn). However, Refs.  [63, 62] did not consider the sparsity of permutations111The sparsity of a permutation σ𝔖2n is measured by the quantity size(σ), which equals 2n in the worst case, but can be significantly smaller in many practical applications.. Lemma 8 improves upon the results in [63, 62], and plays a key role in reducing the circuit size from O(nd) to O(ndlogn+n) in Theorem 1. We believe this result is of independent interest and may find applications in other contexts.

1.2.2 SQSP with 𝒎 Ancillary Qubits

To further reduce the circuit size with ancillary qubits, we introduce a new framework for SQSP that is totally different from the approach without ancillary qubits. Specifically, we employ a novel integer encoding method, denoted as the (n,r)-unary encoding (for the formal definition, see Definition 15). The new framework is roughly divided into two steps: firstly, prepare an intermediate state using the (n,r)-unary encoding, and secondly transform the intermediate state to a state in the binary encoding. Intuitively, the (n,r)-unary encoding divides an n-bit integer to nr continuous parts, each of length r, and represents each part using the corresponding unary encoding. When r=n, the (n,r)-unary encoding recovers to the standard unary encoding. This integer representation method was previously introduced in [26], where the authors showed that a general quantum state using the (n,r)-unary encoding can be prepared by a quantum circuit of size O(2n) and depth O(r2nr) with n2rr qubits. However, they focused on reducing the circuit depth and did not account for the sparsity of the quantum state. Also, their technique does not apply to SQSP. We demonstrate that a sparse quantum state using the (n,r)-unary encoding can be efficiently prepared.

Lemma 9.

Given two positive integers n and r such that r divides n, and a set of size d {(qi,αi)}0id1 such that i|αi|2=1, qi{0,1}n for all 0id1 and qiqj for any ij, there exists a quantum circuit preparing the following n2rr-qubit state

i=0d1αi|eqi(nr,n)|eqi(n2r,nr)|eqi(0,r)=i=0d1αi(j=0nr1|eqi(jr,(j+1)r)). (3)

The circuit is of size O(ndr), using one ancillary qubit.

This state using the (n,r)-unary encoding serves as an intermediate form, ultimately transformed into the binary encoding. We believe that this intermediate state will also have applications in other tasks.

1.2.3 Lower Bound for Circuit Size

Prior proofs of lower bounds for quantum circuit size relied on dimensionality arguments [53, 44], resulting in a trivial lower bound of Ω(d) when applied to the sparse quantum state preparation problem. Here we employ the counting argument. The challenge in applying this method to establish lower bounds for quantum circuit size lies in the existence of an infinite number of single-qubit quantum gates, i.e., the parameters of {Rx(θ),Ry(θ),Rz(θ)} are continuous. The fundamental idea in the proof is to discretize the parameters of the single-qubit quantum gates. Specifically, we consider approximately preparing sparse states in the following set to sufficient precision, ensuring that the resulting states are distinct from one another:

𝒟d{|ψ𝒮1di𝒮|i𝒮{0,,2n1},|𝒮|=d}. (4)

To achieve this, we only need to discretize the single-qubit gates to a certain precision, and we demonstrate that this discretization does not increase the circuit size. Consequently, we can derive a lower bound on the circuit size for SQSP based on the lower bound for the task of approximately preparing the states in 𝒟d using the discretized single-qubit gates and CNOT gates. We hope the discretization technique will find more applications in proving lower bounds on the circuit size for other subclasses of quantum states.

1.3 Related Work

The problem of SQSP has garnered significant attention [17, 34, 45, 41, 13, 12, 64, 56, 35]. Gleinig and Hoefler [17] were the first to address this problem and presented an algorithm generating a quantum circuit of size O(nd) without using ancillary qubits for any n-qubit d-sparse quantum state. Subsequently, Malvetti et al. [34] and Ramacciotti et al. [45] presented permutation-based preparation algorithms, achieving the same circuit size using 0 and 1 ancillary qubits, respectively. de Veras et al. [13] improved upon the ideas in [43, 59] and introduced a preparation algorithm based on quantum state splitting, achieving the same circuit size by employing 2 ancillary qubits. They further optimized this algorithm [12], presenting a circuit size depending on the Hamming weights of the basis states with non-zero amplitudes: O(i|qi|). In the worst case, the circuit size remains O(nd). Mozafari et al. [41] employed decision diagrams to represent quantum states and introduced an algorithm with circuit size O(kn), using 1 ancillary qubit, where k denotes the number of paths in the decision diagram. For a d-sparse quantum state, as the number of paths in its associated decision diagram satisfies kd, the circuit size of this method in the worst-case remains O(nd). In summary, the circuit sizes of all the aforementioned algorithms are O(nd). Recently, Mao et al. [35] propose a sparse state preparation algorithm which generates circuits of size O(ndlogn+n) with two ancillary qubits, improving the previous bound O(nd).

In addition to optimizing circuit size, Zhang et al. [64] focused on reducing circuit depth. They showed that with O(ndlogd) ancillary qubits and O(ndlogd) gates222The circuit size was not explicitly stated in [64], but can be inferred from the algorithm presented therein., any n-qubit d-sparse quantum state can be prepared by a circuit of depth O(lognd). They also proved a matching lower bound of Ω(lognd) on the depth. Sun et al. [56] focused on circuit depth for general quantum state preparation, and noted that their method can also be extended to sparse states, yielding a depth complexity of O(nlognd+nd2logdn+m) with m ancillary qubits. This was later improved to O(ndlogdlogmm+lognd) in [65].

1.4 Discussion

We achieve a relatively complete understanding of the circuit size for SQSP in this paper; however, several interesting problems remain open and are worthy of further discussion:

  • In the scenario of using m ancillary qubits, can we prove a matching lower bound O(ndlog(m+n)+n) on the circuit size without assumptions?

  • In this paper, all of our results focus on exact preparation, meaning the precise preparation of the states. What about the approximate preparation of d-sparse quantum states?

  • What is the optimal trade-off between the number of ancillary qubits and the circuit depth for SQSP? To the best of our knowledge, the only known results are a rough upper bound of O(nlognd+nd2logdn+m) mentioned in [56], and a refined bound of O(ndlogdlogmm+lognd) given in [65].

1.5 Organization

In Section 2, we recall some notations. Section 3 is devoted to the proof of Theorem 1. In Section 4, we prove Theorems 2, 4 and 6. Some conclusions are made in Section 5.

2 Preliminaries

In this paper, all logarithms are base 2. A permutation σ on a finite set A is a bijective function σ:AA. Given a positive integer n, we denote by 𝔖2n the set of all permutations on {0,1}n, and the permutations considered in this paper all belong to 𝔖2n. A cycle (a1,a2,,ak) is a permutation σ such that σ(a1)=a2, σ(a2)=a3, , and σ(ak)=a1. The length of a cycle is the number of elements it contains. A cycle of length two is called a transposition. A cycle of length k is called a k-cycle. The composition of two permutations σ1 and σ2 is denoted by σ2σ1 where the right one is applied first. The composition operation is typically not commutative, but when two permutations are disjoint, we can interchange them.

Any permutation can be decomposed as a composition of a finite number of transpositions. A permutation is even (odd) if it can be written as a composition of an even (odd) number of transpositions.

Lemma 10 ([21]).

Any permutation can be written as the composition of a finite number of pairwise disjoint cycles.

A fixed point of a permutation σ is an element x{0,1}n satisfying σ(x)=x. For any permutation σ, let size(σ) denote the number of non-fixed points of σ:

size(σ)|{x{0,1}nσ(x)x}|. (5)

Here we give a simple example to show the notions given above. Consider the permutation σ𝔖8 given as follows:

σ(0)=1,σ(1)=5,σ(2)=4,σ(3)=3,
σ(4)=2,σ(5)=7,σ(6)=6,σ(7)=0.

σ could be written as

σ =(0,1,5,7)(2,4)(3)(6) (6)
=(0,1,5,7)(2,4) (7)
=(0,5)(0,1)(5,7)(2,4). (8)

In Equation 6, σ is written as the composition of pairwise disjoint cycles, where (0,1,5,7) is a 4-circle and (2,4) is a transposition. In Equation 7, we omit 1-circles. In Equation 8, σ is decomposed as the composition of 4 transpositions, thus σ is an even permutation. The number of non-fixed points of σ is size(σ)=6.

An n-qubit Toffoli gate is a quantum gate acting on n qubits and applying an X gate on the last qubit when the preceding n1 qubits are all in the state |1. Gidney [15] demonstrated the following lemma in his well-known blog:

Lemma 11 ([15]).

Any n-qubit Toffoli gate can be implemented by a quantum circuit of size O(n) without ancillary qubits.

We briefly introduce several complexity notations. Given two functions f(n) and g(n) defined on :

  • f(n)=O(g(n)) if there exist positive constants c and n0 such that f(n)cg(n) for all nn0.

  • f(n)=Ω(g(n)) if there exist positive constants c and n0 such that f(n)cg(n) for all nn0.

  • f(n)=Θ(g(n)) if both f(n)=O(g(n)) and f(n)=Ω(g(n)).

  • f(n)=o(g(n)) if, for any positive constant c>0, there exists a constant n0 such that f(n)cg(n) for all nn0.

  • f(n)=ω(g(n)) if, for any positive constant c>0, there exists a constant n0 such that f(n)cg(n) for all nn0.

3 SQSP without Ancillary Qubits

In this section, we present a sparse quantum state preparation algorithm without using ancillary qubits. The algorithm presented here relies on the efficient implementation of a permutation σ𝔖n. As mentioned earlier, the circuit size for implementing σ in prior works [34, 45] is O(nsize(σ)). Improving upon the results of [63, 62], we show in the following lemma that this bound can be further reduced.

Lemma 12 (Restatement of Lemma 8).

For any permutation σ𝔖2n, there exists a quantum circuit implementing σ of size O(nsize(σ)logn+nlogmin{size(σ),logn}) without using ancillary qubits.

Proof.

The basic steps to implement σ are as follows:

  • Step 1: Decompose σ into the composition of as few permutations σi as possible, where each permutation σi consists of at most m pairwise disjoint transpositions and satisfies that size(σi) is a power of 2. m is a parameter to be determined, and will be a power of 2.

  • Step 2: Assume σi=(x0,x1)(x2,x3)(x2m2,x2m1) and implement each σi successively by the following steps:

    • Step 2a: Execute the permutation σi,1 satisfying the condition: for any 0j2m1, σi,1(xj)=j;

    • Step 2b: Execute the permutation σi,2=(0,1)(2,3)(2m2,2m1);

    • Step 2c: Execute the inverse of permutation σi,1.

Below, we illustrate how to implement this process, set the parameter m, and analyze the circuit size.

In Step 1, we aim to decompose σ into a composition of at most

M=size(σ)m+O(log(min{m,size(σ)})) (9)

permutations {σi0iM1}, i.e., σ=σM1σ0, where each σi consists of at most m pairwise disjoint transpositions, and size(σi) is a power of 2. Firstly, by Lemma 10, we decompose σ into the composition of K disjoint cycles for some integer K0, i.e., σ=ρK1ρ0, where each ρk is an rk-cycle for some integer rk>0. It is clear that krk=size(σ). Each rk-cycle can be decomposed into two sets of disjoint transpositions, each of size either rk2 or rk21 [39]. For example, suppose ρ=(x0,x1,,x2k1) is a cycle of even length. Then we have ρ=ρ′′ρ, where

ρ =(x0,x2k1)(x1,x2k2)(xk1,xk), (10)
ρ′′ =(x1,x2k1)(x2,x2k2)(xk1,xk+1). (11)

A similar construction applies when ρ is an odd-length cycle. Thus, σ can be decomposed into two sets of disjoint transpositions, each of size at most size(σ)2. Each such set can be further partitioned into at most size(σ)2m+log(min{m,size(σ)}) sets of disjoint transpositions, where each set contains at most m transpositions and the number of transpositions is a power of 2.

In Step 2, we show each σi can be efficiently implemented. To avoid introducing more parameters, in the following we assume that σi=(x0,x1)(x2,x3)(x2m2,x2m1) is composed of m pairwise disjoint transpositions. Step 2 is divided into three substeps. First, we illustrate how to implement a permutation σi,1 that satisfies σi,1(xj)=j for any 0j2m1. Note that xj is an integer represented by n bits. We treat xj as an n-dimensional row vector xj=(xj,0,xj,1,,xj,n1) satisfying xj=k=0n1xj,k2k, where xj,k represents the k-th bit and the bits are arranged from the least significant bit to the most significant bit, contrary to the usual convention. We construct a matrix composed of xj to track the changes in xj:

A=(x0x1x2m2x2m1)=(x0,0x0,1x0,n2x0,n1x1,0x1,1x1,n2x1,n1x2m2,0x2m2,1x2m2,n2x2m2,n1x2m1,0x2m1,1x2m1,n2x2m1,n1) (12)

Now we introduce additional conditions to m: suppose m is a power of 2 and satisfies 2mlogn. With these conditions, realizing the permutation σi,1 is equivalent to transforming the matrix A into another matrix A~ using elementary gates:

A~=(000100011111log2m00000000nlog2m) (13)

Suppose that the matrix A has distinct non-zero columns. Since the matrix A has 2m distinct rows, we have log2m22m1. When the j-th column is identical to the k-th column, i.e., xi,j=xi,k for all 0i2m1, and they are not all-zero columns, we apply, without loss of generality, a CNOT gate with the j-th qubit as the control qubit and the k-th qubit as the target qubit, transforming the k-th column into an all-zero column. This process is repeated until the matrix no longer contains identical non-zero columns. This step requires at most n CNOT gates. Next, by using at most swap gates (each of which can be implemented with 3 CNOT gates), we swap the non-zero columns to the first columns, obtaining matrix A1:

A1=(a0,0a0,1a0,a1,0a1,1a1,a2m2,0a2m2,1a2m2,a2m1,0a2m1,1a2m1,00000000n) (14)

Next, we proceed to transform each row of matrix A1 step by step, gradually converting it to matrix A~. We start with the first row (indexed as row 0). If a0,k=1 for any 0kn1, we apply an X gate to the k-th qubit. This step requires at most X gates. Upon completing this step, matrix A1 becomes matrix A2:

A2=(000b1,0b1,1b1,b2m2,0b2m2,1b2m2,b2m1,0b2m1,1b2m1,00000000n) (15)

Suppose the rows indexed as 0 to j1 have been successfully transformed, we turn our attention to row indexed as j, which can be divided into two scenarios:

  • In the case where there exists an element bj,k0 in row j with k>log2m, for each 0k< satisfying kk and bj,kA~j,k, we apply a CNOT gate with the k-th qubit as the control qubit and the k-th qubit as the target qubit. This step requires at most CNOT gates. Subsequently, to eliminate the value bj,k, we employ a multi-control Toffoli gate. The control qubits for this gate correspond to the non-zero elements in row j of matrix A~, while the target qubit is the k-th qubit. This Toffoli gate can be implemented by a circuit of size O(log2m) according to Lemma 11.

  • In the case where there is no element bj,k0 in row j satisfying k>log2m, we first apply a multi-control Toffoli gate, where the control qubits are those corresponding to the non-zero elements in the current row, while the target qubit is the (log2m+1)-th qubit. It is asserted that this Toffoli gate will not alter the elements in the rows indexed by 0 to j1 of the current matrix, as otherwise, there would exist some 0jj1 such that the j-th row is identical to the j-th row, contradicting the assumption that each row is distinct. This Toffoli gate contains at most log2m control qubits. Hence, it can be implemented by a circuit of size O(log2m) according to Lemma 11. Upon completion of this Toffoli gate, we revert to the first case.

Combining the above two cases, the transformation of row j can be implemented using a circuit of size O(+log2m). Therefore, the permutation σi,1 can be implemented using a circuit of size O(n+m+mlogm).

The final component for implementing σ is σi,2=(0,1)(2,3)(2m2,2m1). Given that m is a power of 2, the permutation σi,2 essentially flips the first qubit when the last nlog2m qubits are all in the state |0. Thus, this permutation can be realized using 2(nlog2m) X gates and a multi-controlled Toffoli gate with the last nlog2m qubits as the control qubits and the first qubit as the target qubit. According to Lemma 11, the circuit size for this Toffoli gate is O(nlog2m).

In summary, the circuit size for implementing any permutation σi composed of m pairwise disjoint transpositions is O(n+m+mlogm). As long as mlogn4, the circuit size for implementing σi simplifies to O(n) by noting that log2m22m1. Let m2log(logn4). In Step 1, we decompose σ as σ=σM1σ0, where each σi consists of at most m pairwise disjoint transpositions and M=size(σ)m+O(log(min{m,size(σ)})). Thus, the circuit size for implementing σ is O(nsize(σ)logn+nlogmin{size(σ),logn}).

Step 1 decomposes σ into a composition of {σi} in time O(d). Step 2 then generates the corresponding quantum circuit for each σi, with each requiring O(nsize(σi)) classical preprocessing time. Hence, the total classical time complexity of Lemma 12 is O(nsize(σ)).

 Remark 13.

In particular, it is shown in the proof of Lemma 12 that, if the permutation σ is composed of pairwise disjoint transpositions and size(σ)logn2 is a power of 2, then σ can be implemented by a quantum circuit of size O(n).

Now, we are ready to derive the main theorem in this section.

Theorem 14 (Restatement of Theorem 1).

Any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(ndlogn+n) without using ancillary qubits.

Proof.

The algorithm is illustrated in Algorithm 1. The basic idea is to first prepare a logd-qubit dense quantum state iαi|σ1(qi) where σ is a specific permutation satisfying that 0σ1(qi)d1, and then transform it to the target state iαi|qi by applying σ. The circuit C1 prepares the logd-qubit quantum state, and therefore can be implemented with circuit size O(d). In the following, we turn to the implementation of σ.

After the first two for loops of Algorithm 1, we construct a permutation σ composed of at most d disjoint transpositions. When d=Ω(lognloglogn), according to Lemma 12, the permutation σ can be implemented by a circuit of size O(ndlogn+n). When d=o(lognloglogn), we need to consider it a bit more carefully. Note that we can decompose σ as σ=σσM1σ1σ0, where M=O(dlogn), each σi is composed of pairwise disjoint transpositions such that size(σi)logn2 is a power of 2, and σ is a residual permutation composed of less than logn2 pairwise disjoint transpositions. However, we can always replace σ with σ′′ which is made up by complementing σ with some irrelevant transpositions such that size(σ′′) is a power of 2. For example, (i,j) can be an irrelevant transposition if i,j{qi}0id1{0,,d1}. We can always find enough irrelevant transpositions when d=o(lognloglogn). Denote σ′′σM1σ1σ0 as σ~, it is easily to verify that iαi|σ~(σ1(qi))=iαi|σ(σ1(qi))=iαi|qi. According to Remark 13, σ~ can be implemented by a quantum circuit of size O(ndlogn+n).

In conclusion, for any d-sparse quantum state, Algorithm 1 constructs a preparation circuit without ancillary qubits, of size O(ndlogn+n).

Algorithm 1 SQSP without Ancillary Qubits.

4 SQSP with 𝒎 Ancillary Qubits

4.1 Algorithm for SQSP

In this section, we focus on investigating the trade-off between the number of ancillary qubits and the circuit size of SQSP. To achieve this, we introduce the following new representation of integers, whose encoding efficiency lies between binary encoding and unary encoding. Recall that the unary encoding ex of an integer x sets the x-th bit to 1, while all other bits are set to 0.

Definition 15.

Given an n-bit integer x=i=0n12ixi and another integer r>0 such that r divides n, define x(j,k) for any integers 0j<k<n as x(j,k)i=jk12ijxi. The (n,r)-unary encoding of the integer x is expressed as ex(nr,n)ex(n2r,nr)ex(0,r). In particular, when r=n, the (n,n)-unary encoding corresponds to the standard unary encoding.

For example, when n=8, r=2, and x=11011000, the (8,2)-unary encoding of x is given by e11e01e10e00=0001 0100 0010 1000.

 Remark 16.

For convenience in presentation, we assume that r divides n. However, even if r does not divide n, this will not affect the correctness of any subsequent conclusions.

In the following lemma, we show that any sparse quantum state can be efficiently prepared using the (n,r)-unary encoding.

Lemma 17 (Restatement of Lemma 9).

Given two positive integers n and r such that r divides n, and a set of size d {(qi,αi)}0id1 such that i|αi|2=1, qi{0,1}n for all 0id1 and qiqj for any ij, there exists a quantum circuit preparing the following n2rr-qubit state

i=0d1αi|eqi(nr,n)|eqi(n2r,nr)|eqi(0,r)=i=0d1αi(j=0nr1|eqi(jr,(j+1)r)). (16)

The circuit is of size O(ndr), using one ancillary qubit.

Proof.

See Appendix A in the full version [30].

The following lemma transforms the unary encoding to the binary encoding.

Lemma 18.

There exists a quantum circuit that converts the unary encoding of n-bit integers to the binary encoding, that is, achieving the following transformation for any 0i2n1:

|ei|0n|02n|i (17)

The circuit has a size of O(n2n).

Proof.

See Appendix B in the full version [30].

With the above two key lemmas established, we obtain the following theorem for a wide parameter regime.

Theorem 19.

For any d=Ω(nlogn) and any m[Ω(n2),O(ndlognd+n)], any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(ndlog(m+n)+n) using m ancillary qubits.

Proof.

The algorithm is presented in Algorithm 2. Let rlogmn such that n2rrm. In Algorithm 2, we use an ancillary register M consisting of n2rr qubits, which is further divided into nr sub-registers {Mj}0jnr1 as in Lemma 9. The target state is prepared in another register R, which is also divided into nr sub-registers {Rj}0jnr1, each consisting of r qubits.

Let us first show the correctness of Algorithm 2. The initial state is

(j=0nr1|0Mj2r)(j=0nr1|0Rjr). (18)

After Step 2, we have

i=0d1αi(j=0nr1|eqi(jr,(j+1)r)Mj)(j=0nr1|0Rjr). (19)

Note that each |eqi(jr,(j+1)r)Mj is the unary encoding of the r-bit integer qi(jr,(j+1)r). Therefore, Step 3 is to convert |eqi(jr,(j+1)r)Mj|0Rjr to |0Mj2r|qi(jr,(j+1)r)Rj for all 0jnr1 according to Lemma 18. After Step 3, omitting the ancillary qubits, the state stored in the register R now is

i=0d1αi(j=0nr1|qi(jr,(j+1)r)Rj)=i=0d1αi|qiR, (20)

as desired.

Finally, we analyze the size of the circuit. According to Lemma 9 and Lemma 18, the size of Step 2 and Step 3 is O(ndr) and nrO(r2r), respectively. Therefore, the circuit size is O(ndlogmlogn+m), which is O(ndlog(m+n)+n) when m[Ω(n2),O(ndlognd+n)].

Algorithm 2 SQSP with m Ancillary Qubits.

The classical time to generate the quantum circuit in Steps 2 and 3 is O(ndr) and O(n2r), respectively. Therefore, the total classical time complexity of Algorithm 2 is O(ndlog(m+n)+n), matching the circuit size.

Combining Theorem 1 with Theorem 19, we achieve the trade-off between the number of the ancillary qubits and the circuit size for any d1 and mO(ndlognd+n).

Theorem 20 (Restatement of Theorem 2).

For any mO(ndlognd+n), any n-qubit d-sparse quantum state can be prepared by a quantum circuit of size O(ndlog(m+n)+n) using m ancillary qubits.

Proof.

When d=Ω(nlogd) and mΩ(n2), we resort to Theorem 19, and the size is O(ndlog(m+n)+n), satisfying the requirement of the theorem. Otherwise, we have d=o(nlogn) (implying mo(n2)) or mo(n2), and we turn to the algorithm without ancillary qubits, i.e., Theorem 1, and the circuit size is O(ndlogn+n), also satisfying the requirement of the theorem. The proof is completed.

4.2 Lower Bound on the Circuit Size

In this section, we prove lower bounds on the circuit size for preparing sparse quantum states. The following proof is based on the counting argument. To overcome the challenge posed by the existence of an infinite number of single-qubit quantum gates, we discretize the parameters of these gates. For the sake of clarity, we first establish the lower bound on the circuit size without any assumption, and then proceed to the case with reasonable assumptions.

Theorem 21 (Restatement of Theorem 6).

Given m ancillary qubits available, there exist n-qubit d-sparse quantum states such that any algorithm to prepare them requires Ω(ndlog(m+n)+logd+n) elementary quantum gates.

Proof.

Consider the universal quantum gate set G{Rx(θ),Ry(θ),Rz(θ),CNOT}, where θ[0,2π) is a parameter, and the set of quantum states

𝒟d{|ψ𝒮1di𝒮|i𝒮{0,,2n1},|𝒮|=d}. (21)

For any |ψ,|ϕ𝒟d such that |ψ|ϕ, we have |ψ|ϕ2d. Suppose the number of elementary quantum gates required to prepare a quantum state |ψ𝒟d in the worst case is T. Note that Tcnd for some constant c>0 [17, 34].

Now we consider a new set of quantum gates G~ and a new quantum state preparation task. The new set G~ is constructed from G by restricting the precision of the rotation angles of the single-qubit gates to δ14c2d3n2. For instance, given a single-qubit gate Rx(θ) from G with a parameter θ, we set θ~=δθδ, acquire Rx(θ~) in G~, and approximate Rx(θ) with Rx(θ~). The new quantum state preparation task is to construct a circuit with G~ to prepare a quantum state |ψ~ for any given |ψ𝒟d such that |ψ|ψ~14d. Note that |ϕ|ψ~>14d for any |ϕ𝒟d such that |ψ|ϕ.

The circuit to prepare |ψ~ with G~ can be constructed as follows: first, we construct a circuit U=UT1U0 with G to prepare the quantum state |ψ exactly, where UiG or Ui=I; then, we replace each single-qubit gate Rl(θ) (l{x,y,z}) in U with Rl(θ~) from G~. It can be verified that this new circuit U~ prepare an approximate quantum state |ψ~ for |ψ, satisfying |ψ|ψ~14d. This demonstrates the feasibility of achieving the new quantum state preparation task with G~. Note that the discussion also reduces the task of preparing |ψ~ with G~ to preparing |ψ with G. Therefore, the lower bound on the circuit size of the former immediately implies the lower bound on the circuit size of the latter.

Note that |G~|=6πδ+1. For each Ui, there are a total of (6πδ+2) choices of quantum gates (including the identity gate I) to select from. The position where the quantum gates act has at most (m+n)2 choices. Therefore, by the counting argument, we have

((m+n)2(6πδ+2))T|𝒟d|(2nd)d (22)

Thus, we have T=Ω(nddlogdlog(m+n)+logd).

In addition, we have T=Ω(d) from the dimensionality argument. Also, we consider the preparation of the state |1n from the initial state |0n with arbitrary single-qubit gates and CNOT. Undoubtedly, we have to access all the qubits to prepare |1n. Therefore, we get a lower bound Ω(n) on the circuit size.

Combining the argument above, we conclude that

T=Ω(nddlogdlog(m+n)+logd+d+n)=Ω(ndlog(m+n)+logd+n). (23)

Theorem 22 (Restatement of Theorem 4).

Suppose d2ϵn for a sufficiently small constant ϵ(0,1), and given m ancillary qubits, if an algorithm 𝒜 for preparing n-qubit d-sparse quantum states satisfies the following conditions:

  1. 1.

    𝒜 uses at most O(d) single-qubit rotation gates with arbitrary angles,

  2. 2.

    all other single-qubit gates amount to a total of O(n) types,

then 𝒜 requires Ω(ndlog(m+n)+n) elementary quantum gates in the worst case.

Proof.

Following the same discussion as in the proof of Theorem 21, it remains to estimate the number of quantum circuits with T gates and containing only O(d) single-qubit rotation gates with arbitrary angles. We distinguish {Rx(θ),Ry(θ),Rx(θ)} from other single-qubit gates in the circuit, so there are O(n) types of single-qubit gates in total. First, we estimate the number of circuit templates without specifying the parameters of {Rx(θ),Ry(θ),Rx(θ)} in the circuit, and then we specify the angles of single-qubit rotation gates. Therefore, we have

((m+n)2O(n))T(6πδ)O(d)|𝒟d|(2nd)d. (24)

Hence, we have O(log(m+n))T+O(dlognd)nddlogd, implying T=Ω(ndlog(m+n)) when d2ϵn for a sufficiently small constant ϵ(0,1). Similarly, combining T=Ω(d+n), we obtain the lower bound on the circuit size as Ω(ndlog(m+n)+n).

5 Conclusion

In this paper, we focus on optimizing the circuit size of preparing sparse quantum states in two scenarios: without and with ancillary qubits. First, we have demonstrated that, without ancillary qubits, any n-qubit d-sparse quantum state can be prepared by a circuit of size O(ndlogn+n). Second, we have proved that with mO(ndlognd+n) ancillary qubits available, the circuit size is O(ndlog(m+n)+n). Finally, we have established a matching lower bound Ω(ndlog(m+n)+n) on the circuit size for the case of m ancillary qubits available when d2δn for a sufficiently small constant δ(0,1) under reasonable assumptions. Additionally, we have provided a slightly weaker lower bound of Ω(ndlog(m+n)+logd+n) without any assumptions. Putting the above results together, we have obtained the optimal bound Θ(ndlognd+n) on the circuit size in the case of an unlimited number of ancillary qubits available.

References

  • [1] Nabila Abdessaied, Mathias Soeken, Michael Kirkedal Thomsen, and Rolf Drechsler. Upper bounds for reversible circuits based on young subgroups. Information Processing Letters, 114(6):282–286, 2014. doi:10.1016/j.ipl.2014.01.003.
  • [2] Israel F Araujo, Carsten Blank, Ismael CS Araújo, and Adenilton J da Silva. Low-rank quantum state preparation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023. doi:10.1109/TCAD.2023.3297972.
  • [3] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical Review A, 52(5):3457, 1995. doi:10.1103/PhysRevA.52.3457.
  • [4] Johannes Bausch. Fast black-box quantum state preparation. Quantum, 6:773, 2022. doi:10.22331/q-2022-08-04-773.
  • [5] Ville Bergholm, Juha J Vartiainen, Mikko Möttönen, and Martti M Salomaa. Quantum circuits with uniformly controlled one-qubit gates. Physical Review A, 71(5):052330, 2005. doi:10.1103/PhysRevA.71.052330.
  • [6] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. Simulating hamiltonian dynamics with a truncated taylor series. Physical Review Letters, 114(9):090502, 2015. doi:10.1103/physrevlett.114.090502.
  • [7] Alex Brodsky. Reversible circuit realizations of Boolean functions. In Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science, volume 155 of IFIP, pages 67–80. Kluwer/Springer, 2004. doi:10.1007/1-4020-8141-3_8.
  • [8] Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. Journal of the ACM, 69(5):1–72, 2022. doi:10.1145/3549524.
  • [9] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:15, 2020. doi:10.4230/LIPIcs.MFCS.2020.23.
  • [10] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018. doi:10.1073/pnas.1801723115.
  • [11] William Cottrell, Ben Freivogel, Diego M Hofman, and Sagar F Lokhande. How to build the thermofield double state. Journal of High Energy Physics, 2019(2):1–43, 2019. doi:10.1007/jhep02(2019)058.
  • [12] Tiago ML de Veras, Leon D da Silva, and Adenilton J da Silva. Double sparse quantum state preparation. Quantum Information Processing, 21(6):204, 2022. doi:10.1007/s11128-022-03549-y.
  • [13] Tiago ML de Veras, Ismael CS De Araujo, Daniel K Park, and Adenilton J da Silva. Circuit-based quantum random access memory for classical data with continuous amplitudes. IEEE Transactions on Computers, 70(12):2125–2135, 2020. doi:10.1109/TC.2020.3037932.
  • [14] Richard P Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6/7), 1982.
  • [15] Craig Gidney. Constructing large controlled nots. https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots.html, 2015.
  • [16] András Gilyén, Zhao Song, and Ewin Tang. An improved quantum-inspired algorithm for linear regression. Quantum, 6:754, 2022. doi:10.22331/q-2022-06-30-754.
  • [17] Niels Gleinig and Torsten Hoefler. An efficient algorithm for sparse quantum state preparation. In Proceedings of the 58th ACM/IEEE Design Automation Conference, pages 433–438. IEEE, 2021. doi:10.1109/DAC18074.2021.9586240.
  • [18] Javier Gonzalez-Conde, Thomas W Watts, Pablo Rodriguez-Grasa, and Mikel Sanz. Efficient quantum amplitude encoding of polynomial functions. Quantum, 8:1297, 2024. doi:10.22331/q-2024-03-21-1297.
  • [19] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions, 2002. arXiv:quant-ph/0208112.
  • [20] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 212–219, 1996. doi:10.1145/237814.237866.
  • [21] Marshall Hall. The theory of groups. Courier Dover Publications, 2018.
  • [22] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15):150502, 2009. doi:10.1103/physrevlett.103.150502.
  • [23] Adam Holmes and Anne Y Matsuura. Efficient quantum circuits for accurate state preparation of smooth, differentiable functions. In Proceedings of IEEE International Conference on Quantum Computing and Engineering, pages 169–179. IEEE, 2020. doi:10.1109/QCE49297.2020.00030.
  • [24] Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl. Quantum circuits for isometries. Physical Review A, 93(3):032318, 2016. doi:10.1103/PhysRevA.93.032318.
  • [25] Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang. Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 213–229. SIAM, 2020. doi:10.1137/1.9781611975994.13.
  • [26] Sonika Johri, Shantanu Debnath, Avinash Mocherla, Alexandros Singk, Anupam Prakash, Jungsang Kim, and Iordanis Kerenidis. Nearest centroid classification on a trapped ion quantum computer. npj Quantum Information, 7(1):122, 2021. doi:10.1038/s41534-021-00456-5.
  • [27] Iordanis Kerenidis and Jonas Landman. Quantum spectral clustering. Physical Review A, 103(4):042415, 2021. doi:10.1103/PhysRevA.103.042415.
  • [28] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: A quantum algorithm for unsupervised machine learning. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL: https://proceedings.neurips.cc/paper_files/paper/2019/file/16026d60ff9b54410b3435b403afd226-Paper.pdf.
  • [29] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference, volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21, 2017. doi:10.4230/LIPIcs.ITCS.2017.49.
  • [30] Lvzhou Li and Jingquan Luo. Nearly optimal circuit size for sparse quantum state preparation, 2024. arXiv:2406.16142.
  • [31] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631–633, 2014. doi:10.1038/nphys3029.
  • [32] Guang Hao Low and Isaac L Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical Review Letters, 118(1):010501, 2017. doi:10.1103/physrevlett.118.010501.
  • [33] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. doi:10.22331/q-2019-07-12-163.
  • [34] Emanuel Malvetti, Raban Iten, and Roger Colbeck. Quantum circuits for sparse isometries. Quantum, 5:412, 2021. doi:10.22331/q-2021-03-15-412.
  • [35] Rui Mao, Guojing Tian, and Xiaoming Sun. Toward optimal circuit size for sparse quantum state preparation. Physical Review A, 110:032439, September 2024. doi:10.1103/PhysRevA.110.032439.
  • [36] Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz. Quantum algorithms for approximate function loading. Physical Review Research, 5(3):033114, 2023. doi:10.1103/PhysRevResearch.5.033114.
  • [37] Ketan Markov, Igor Patel, and John Hayes. Optimal synthesis of linear reversible circuits. Quantum Information and Computation, 8(3&4):0282–0294, 2008. doi:10.26421/QIC8.3-4-4.
  • [38] Sam McArdle, András Gilyén, and Mario Berta. Quantum state preparation without coherent arithmetic, 2022. arXiv:2210.14892.
  • [39] Cristopher Moore and Martin Nilsson. Parallel quantum computation and quantum codes. SIAM Journal on Computing, 31(3):799–815, 2001. doi:10.1137/S0097539799355053.
  • [40] Mudassir Moosa, Thomas W Watts, Yiyou Chen, Abhijat Sarma, and Peter L McMahon. Linear-depth quantum circuits for loading fourier approximations of arbitrary functions. Quantum Science and Technology, 9(1):015002, 2023. doi:10.1088/2058-9565/acfc62.
  • [41] Fereshte Mozafari, Giovanni De Micheli, and Yuxiang Yang. Efficient deterministic preparation of quantum states using decision diagrams. Physical Review A, 106(2):022617, 2022. doi:10.48550/arXiv.2206.08588.
  • [42] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information, volume 2. Cambridge university press Cambridge, 2001. doi:10.1145/505482.505499.
  • [43] Daniel K Park, Francesco Petruccione, and June-Koo Kevin Rhee. Circuit-based quantum random access memory for classical data. Scientific Reports, 9(1):3949, 2019. doi:10.1038/s41598-019-40439-3.
  • [44] Martin Plesch and Časlav Brukner. Quantum-state preparation with universal gate decompositions. Physical Review A, 83(3):032302, 2011. doi:10.1103/PhysRevA.83.032302.
  • [45] Debora Ramacciotti, Andreea I Lefterovici, and Antonio F Rotundo. Simple quantum algorithm to efficiently prepare sparse states. Physical Review A, 110(3):032609, 2024. doi:10.1103/physreva.110.032609.
  • [46] Arthur G. Rattew and Bálint Koczor. Preparing arbitrary continuous functions in quantum registers with logarithmic complexity, 2022. arXiv:2205.00519.
  • [47] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113(13):130503, 2014. doi:10.1103/PhysRevLett.113.130503.
  • [48] Mehdi Saeedi and Igor L Markov. Synthesis and optimization of reversible circuits—a survey. ACM Computing Surveys, 45(2):1–34, 2013. doi:10.1145/2431211.2431220.
  • [49] Mehdi Saeedi, Mehdi Sedighi, and Morteza Saheb Zamani. A library-based synthesis methodology for reversible logic. Microelectronics Journal, 41(4):185–194, 2010. doi:10.1016/J.MEJO.2010.02.002.
  • [50] Mehdi Saeedi, Morteza Saheb Zamani, Mehdi Sedighi, and Zahra Sasanian. Reversible circuit synthesis using a cycle-based approach. ACM Journal on Emerging Technologies in Computing Systems, 6(4):1–26, 2010. doi:10.1145/1877745.1877747.
  • [51] Yuval R Sanders, Guang Hao Low, Artur Scherer, and Dominic W Berry. Black-box quantum state preparation without arithmetic. Physical Review Letters, 122(2):020502, 2019. doi:10.1103/PhysRevLett.122.020502.
  • [52] Vivek V Shende, Stephen S Bullock, and Igor L Markov. Synthesis of quantum logic circuits. In Proceedings of the 2005 Asia and South Pacific Design Automation Conference, pages 272–275, 2005. doi:10.1145/1120725.1120847.
  • [53] Vivek V Shende, Igor L Markov, and Stephen S Bullock. Smaller two-qubit circuits for quantum communication and computation. In Proceedings Design, Automation and Test in Europe Conference and Exhibition, volume 2, pages 980–985. IEEE, 2004. doi:10.1109/DATE.2004.1269020.
  • [54] Vivek V Shende, Aditya K Prasad, Igor L Markov, and John P Hayes. Synthesis of reversible logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22(6):710–722, 2003. doi:10.1109/TCAD.2003.811448.
  • [55] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 124–134. IEEE, 1994. doi:10.1109/SFCS.1994.365700.
  • [56] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(10):3301–3314, 2023. doi:10.1109/TCAD.2023.3244885.
  • [57] Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217–228, 2019. doi:10.1145/3313276.3316310.
  • [58] Ewin Tang. Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions. Physical Review Letters, 127(6):060503, 2021. doi:10.1103/PhysRevLett.127.060503.
  • [59] Carlo A Trugenberger. Probabilistic quantum memories. Physical Review Letters, 87(6):067901, 2001. doi:10.1103/PhysRevLett.87.067901.
  • [60] Shengbin Wang, Zhimin Wang, Guolong Cui, Shangshang Shi, Ruimin Shang, Lixin Fan, Wendong Li, Zhiqiang Wei, and Yongjian Gu. Fast black-box quantum state preparation based on linear combination of unitaries. Quantum Information Processing, 20(8):270, 2021. doi:10.1007/s11128-021-03203-z.
  • [61] Robert Wille and Rolf Drechsler. Bdd-based synthesis of reversible logic for large functions. In Proceedings of the 46th Annual Design Automation Conference, pages 270–275, 2009. doi:10.1145/1629911.1629984.
  • [62] Xian Wu and Lvzhou Li. Asymptotically optimal synthesis of reversible circuits. Information and Computation, 301:105235, 2024. doi:10.1016/j.ic.2024.105235.
  • [63] Dmitry V Zakablukov. On asymptotic gate complexity and depth of reversible circuits without additional memory. Journal of Computer and System Sciences, 84:132–143, 2017. doi:10.1016/j.jcss.2016.09.010.
  • [64] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quantum state preparation with optimal circuit depth: Implementations and applications. Physical Review Letters, 129(23):230504, 2022. doi:10.1103/PhysRevLett.129.230504.
  • [65] Xiao-Ming Zhang and Xiao Yuan. Circuit complexity of quantum access models for encoding classical data. npj Quantum Information, 10(1):42, 2024. doi:10.1038/s41534-024-00835-8.