Back to Search
Start Over
Low-depth quantum state preparation
- Source :
- Physical Review Research, Vol 3, Iss 4, p 043200 (2021)
- Publication Year :
- 2021
- Publisher :
- American Physical Society, 2021.
-
Abstract
- A crucial subroutine in quantum computing is to load the classical data of N complex numbers into the amplitude of a superposed n=⌈log_{2}N⌉-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(n^{2}) 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(N^{2}) ancillary qubits, O(n^{2}) circuit depth, and O(n^{2}) 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 Ω(n) for the minimum circuit depth and runtime with an arbitrary number of ancillary qubits, aligning with our scheme with O(n^{2}). The algorithms are expected to have wide applications in both near-term and universal quantum computing.
Details
- Language :
- English
- ISSN :
- 26431564
- Volume :
- 3
- Issue :
- 4
- Database :
- Directory of Open Access Journals
- Journal :
- Physical Review Research
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.bc6d7b7c46194d1c9d391731143d9eb5
- Document Type :
- article
- Full Text :
- https://doi.org/10.1103/PhysRevResearch.3.043200