Journal
QUANTUM
Volume 5, Issue -, Pages 1-12Publisher
VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF
DOI: 10.22331/q-2021-12-20-606
Keywords
-
Funding
- Army Research Office [W911NF-14-1-0103]
- Transformative Quantum Technologies (TQT)
- Natural Sciences and Engineering Research Council of Canada (NSERC) [RGPIN-2018-05188]
- Government of Canada through the Department of Innovation, Science and Economic Development Canada
- Province of Ontario through the Ministry of Colleges and Universities
- Natural Sciences and Engineering Research Council of Canada [RGPIN-2019-04198]
- Canadian Institute for Advanced Research
- IBM Research
Ask authors/readers for more resources
In this work, we improve the runtime of classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates by establishing new upper bounds on stabilizer ranks. Through known techniques, our algorithm approximates output probabilities of circuits with a given error using a poly(n, m)2(alpha m) runtime. Additionally, we provide improved upper bounds on the stabilizer rank of symmetric product states and suggest a method to further enhance the upper bounds through the construction of linear codes.
In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of m copies of the magic state vertical bar T = root 2(-1)(vertical bar 0 + e(i pi/4)vertical bar 1 ) in the limit of large m. In particular, we show that vertical bar T (circle times m) can be exactly expressed as a superposition of at most O(2(alpha m)) stabilizer states, where alpha <= 0.3963, improving on the best previously known bound alpha <= 0.463. This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an n-qubit 'Clifford + T' circuit U with m uses of the T gate to within a given inverse polynomial relative error using a runtime poly(n, m)2(alpha m). We also provide improved upper bounds on the stabilizer rank of symmetric product states vertical bar psi (circle times m) more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and m instances of any (fixed) single-qubit Z-rotation gate with runtime poly(n, m)2(m/2). We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available