As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of | i ⟩ | 0 n ⟩ → | i ⟩ | ψ i ⟩ for all i ∈ { 0 , 1 } k for the given n -qubit states | ψ i ⟩ . In this paper, we construct a quantum circuit for implementing CQSP, with depth O ( n + k + 2 n + k n + k + m ) and size O ( 2 n + k ) for any given number m of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are optimal for any integer parameters m , k ≥ 0 and n ≥ 1 . When k = 0 , the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation | 0 n ⟩ | 0 m ⟩ → | ψ ⟩ | 0 m ⟩ . This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to Θ ( n + 2 n / ( n + m ) ) and its size complexity to Θ ( 2 n ) for any
As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of | i ⟩ | 0 n ⟩ → | i ⟩ | ψ i ⟩ for all i ∈ { 0 , 1 } k for the given n -qubit states | ψ i ⟩ . In this paper, we construct a quantum circuit for implementing CQSP, with depth O ( n + k + 2 n + k n + k + m ) and size O ( 2 n + k ) for any given number m of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are optimal for any integer parameters m , k ≥ 0 and n ≥ 1 . When k = 0 , the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation | 0 n ⟩ | 0 m ⟩ → | ψ ⟩ | 0 m ⟩ . This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to Θ ( n + 2 n / ( n + m ) ) and its size complexity to Θ ( 2 n ) for any
The Quantum State Preparation problem aims to prepare an n-qubit quantum state |ψv=k=02n-1vk|k from the initial state |0n, for a given unit vector v=(v0,v1,v2,v2n-1)TC2n with ||v||2=1. The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth complexity remains open when ancillary qubits are available. In this paper, we study quantum circuits when there are m ancillary qubits available. We construct, for any m, circuits that can prepare |ψvin depth Õ(2nm+n+n) and size O(2n), achieving the optimal value for both measures simultaneously. These results also imply a depth complexity of (4nm+n) for quantum circuits implementing a general n-qubit unitary for any m≤O(2n/n) number of ancillary qubits. This resolves the depth complexity for circuits without ancillary qubits. And for circuits with exponentially many ancillary qubits, our result quadratically improves the currently best upper bound of O(4n) to ˜(2n). Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide parameter regime. The results can be viewed as (optimal) time-space trade-off bounds, which is not only theoretically interesting, but also practically relevant in the current trend that the number of qubits starts to take off, by showing a way to use a large number of qubits to compensate the short qubit lifetime.
Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.
The preparation of n-qubit quantum states is a cross-cutting subroutine for many quantum algorithms, and the effort to reduce its circuit complexity is a significant challenge. In the literature, the quantum state preparation algorithm by Sun et al. is known to be optimally bounded, defining the asymptotically optimal width-depth trade-off bounds with and without ancillary qubits. In this work, a simpler algebraic decomposition is proposed to separate the preparation of the real part of the desired state from the complex one, resulting in a reduction in terms of circuit depth, total gates, and CNOT count when m ancillary qubits are available. The reduction in complexity is due to the use of a single operator Λ for each uniformly controlled gate, instead of the three in the original decomposition. Using the PennyLane library, this new algorithm for state preparation has been implemented and tested in a simulated environment for both dense and sparse quantum states, including those that are random and of physical interest. Furthermore, its performance has been compared with that of Möttönen et al.'s algorithm, which is a de facto standard for preparing quantum states in cases where no ancillary qubits are used, highlighting interesting lines of development.
A crucial subroutine in quantum computing is to load the classical data of N complex numbers into the amplitude of a superposed $n=\ensuremath{\lceil}{log}_{2}N\ensuremath{\rceil}$-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least O(N) constant weight operations. However, the proof assumes that only n qubits are used, whereas the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with O(n2) circuit depth to encode any N complex numbers using only single- and two-qubit gates, and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with O(N2) ancillary qubits, O(n2) circuit depth, and O(n2) average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits, and at most O(n) qubits are entangled. We also prove a fundamental lower bound $\mathrm{\ensuremath{\Omega}}(n)$ for the minimum circuit depth and runtime with an arbitrary number of ancillary qubits, aligning with our scheme with O(n2). The algorithms are expected to have wide applications in both near-term and universal quantum computing.
A crucial subroutine in quantum computing is to load the classical data of N complex numbers into the amplitude of a superposed n=⌈log2N⌉-qubit state. It has been proven that any algorithm universally implementing this subroutine would need at least O(N) constant weight operations. However, the proof assumes that only n qubits are used, whereas the circuit depth could be reduced by extending the space and allowing ancillary qubits. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with O(n2) circuit depth to encode any N complex numbers using only single-, two-qubit gates and local measurements with ancillary qubits. Different variances of the algorithm are proposed with different space and runtime. In particular, we present a scheme with O(N2) ancillary qubits, O(n2) circuit depth, and O(n2) average runtime, which exponentially improves the conventional bound. While the algorithm requires more ancillary qubits, it consists of quantum circuit blocks that only simultaneously act on a constant number of qubits and at most O(n) qubits are entangled. We also prove a fundamental lower bound $\mitΩ(n)$ for the minimum circuit depth and runtime with arbitrary number of ancillary qubits, aligning with our scheme with O(n2). The algorithms are expected to have wide applications in both near-term and universal quantum computing.
Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates. We show that for any budget m≥0 of ancilla, every n-qubit unitary can be exactly implemented using a quantum circuit consisting of O(4n) CNOT and single-qubit gates in O(n+4n/(n+m)) layers attaining the asymptotically optimal depth--ancilla tradeoff while simultaneously achieving optimal circuit size. The key idea is to encode computational basis states as wavefunctions sharing a Gaussian envelope, converting unitary action on amplitudes into coordinate transformations that admit shallow circuit implementations. The continuous encoding is then discretized, with approximation errors removed by exact residual correction. The depth-ancilla tradeoff follows by recursively applying the quantum Shannon decomposition, synthesizing its smaller unitary factors, and reusing ancillary qubits.