TY - JOUR
T1 - Low-depth quantum state preparation
AU - Zhang, Xiao-Ming
AU - Yung, Man-Hong
AU - Yuan, Xiao
PY - 2021
Y1 - 2021
N2 - A crucial subroutine in quantum computing is to load the classical data of N complex numbers into the amplitude of a superposed n = [log2 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(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 Ω(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.
AB - A crucial subroutine in quantum computing is to load the classical data of N complex numbers into the amplitude of a superposed n = [log2 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(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 Ω(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.
KW - ALGORITHMS
KW - SUPREMACY
UR - http://www.scopus.com/inward/record.url?scp=85122534371&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85122534371&origin=recordpage
UR - http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=LinksAMR&SrcApp=PARTNER_APP&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000734834100008
U2 - 10.1103/PhysRevResearch.3.043200
DO - 10.1103/PhysRevResearch.3.043200
M3 - 21_Publication in refereed journal
VL - 3
JO - Physical Review Research
JF - Physical Review Research
SN - 2643-1564
IS - 4
M1 - 043200
ER -