Name
Abstract | ||
|---|---|---|
We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2n
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-3</sup>
- 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-n</sup>
/2 must take at least 2
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-o(n)</sup>
time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 2
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2.2451×10-8t</sup>
below which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/TIT.2020.3004427 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
Quantum computing,computational complexity,circuit simulation | Quantum,Discrete mathematics,Upper and lower bounds,Quantum simulator,Amplitude,Mathematics,Monotone polygon,Exponential time hypothesis | Journal |
Volume | Issue | ISSN |
66 | 9 | 0018-9448 |
Citations | PageRank | References |
1 | 0.36 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cupjin Huang | 1 | 4 | 1.13 |
| Michael Newman | 2 | 1 | 0.36 |
| Mario Szegedy | 3 | 3358 | 325.80 |