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.
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.
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
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.
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.
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.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth.
We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential.
The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy.
Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension d and M≥d2−1 ports, we construct a unitary circuit of depth O(d), independent of M and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2. Thus, at fixed d, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on d can also be removed remains open.
In this work, we investigate the trade-off between the circuit depth and the number of ancillary qubits for preparing sparse quantum states. We prove that any n-qubit d-spare quantum state (i.e., it has only d non-zero amplitudes) can be prepared by a quantum circuit with depth O(mlogm/nndlogm+lognd) using m≥6n ancillary qubits, which achieves the current best trade-off between depth and ancilla number. In particular, when m=Θ(logdnd), our result recovers the optimal circuit depth Θ(lognd) given in \hyperlink{cite.zhang2022quantum}{[Phys. Rev. Lett., 129, 230504(2022)]}, but using significantly fewer gates and ancillary qubits.