1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
2Department of Physics, Massachusetts Institute of Technology, Cambrdige, Massachusetts 02139, USA
3Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
4Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
5Zapata Computing, Inc., 100 Federal Street, 20th Floor, Boston, Massachusetts 02110, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ($mathsf{PH}$) does not collapse, a stronger version of the statement that $mathsf{P} neq mathsf{NP}$, which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH($a$) and per-int-NSETH($b$) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in $n$ variables over $mathbb{F}_2$ or the permanent of an $n times n$ integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires $2^{cn}$ time steps, where $c in {a,b}$. A third conjecture poly3-ave-SBSETH($a’$) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class $mathsf{SBP}$. We analyze evidence for these conjectures and argue that they are plausible when $a=1/2$, $b = 0.999$ and $a’ = 1/2$.
Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring $10^4$ to $10^7$ gates.
► BibTeX data
► References
[1] S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 461 (2063): 3473–3482, 2005. 10.1098/rspa.2005.1546.
https://doi.org/10.1098/rspa.2005.1546
[2] S. Aaronson. A linear-optical proof that the permanent is $#P$-hard. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2136): 3393–3405, 2011. 10.1098/rspa.2011.0232.
https://doi.org/10.1098/rspa.2011.0232
[3] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pages 333–342, 2011. 10.1145/1993636.1993682.
https://doi.org/10.1145/1993636.1993682
[4] S. Aaronson and L. Chen. Complexity-theoretic foundations of quantum supremacy experiments. In 32nd Computational Complexity Conference (CCC 2017), volume 79, pages 22:1–22:67, 2017. 10.4230/LIPIcs.CCC.2017.22.
https://doi.org/10.4230/LIPIcs.CCC.2017.22
[5] S. Aaronson, A. Bouland, G. Kuperberg, and S. Mehraban. The computational complexity of ball permutations. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 317–327, 2017. 10.1145/3055399.3055453.
https://doi.org/10.1145/3055399.3055453
[6] S. Arora and B. Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
[7] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5
[8] M. Ball, A. Rosen, M. Sabin, and P. N. Vasudevan. Average-case fine-grained hardness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, page 483–496, 2017. 10.1145/3055399.3055466.
https://doi.org/10.1145/3055399.3055466
[9] C. Beck and R. Impagliazzo. Strong ETH holds for regular resolution. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, page 487–494, 2013. 10.1145/2488608.2488669.
https://doi.org/10.1145/2488608.2488669
[10] R. Beigel and J. Tarui. On ACC. Computational Complexity, 4 (4): 350–366, 1994. 10.1007/BF01263423.
https://doi.org/10.1007/BF01263423
[11] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for quantum simulation showing a quantum speedup. Phys. Rev. X, 8: 021010, Apr 2018. 10.1103/PhysRevX.8.021010.
https://doi.org/10.1103/PhysRevX.8.021010
[12] A. Björklund, P. Kaski, and R. Williams. Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. Algorithmica, 81 (10): 4010–4028, 2019. 10.1007/s00453-018-0513-7.
https://doi.org/10.1007/s00453-018-0513-7
[13] A. Bouland, L. Mančinska, and X. Zhang. Complexity classification of two-qubit commuting Hamiltonians. In 31st Conference on Computational Complexity (CCC 2016), volume 50, pages 28:1–28:33, 2016. 10.4230/LIPIcs.CCC.2016.28.
https://doi.org/10.4230/LIPIcs.CCC.2016.28
[14] A. Bouland, J. F. Fitzsimons, and D. E. Koh. Complexity classification of conjugated Clifford circuits. In 33rd Computational Complexity Conference (CCC 2018), volume 102, pages 21:1–21:25, 2018. 10.4230/LIPIcs.CCC.2018.21.
https://doi.org/10.4230/LIPIcs.CCC.2018.21
[15] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15 (2): 159, 2019. 10.1038/s41567-018-0318-2.
https://doi.org/10.1038/s41567-018-0318-2
[16] M. J. Bremner, R. Jozsa, and D. J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2126): 459–472, 2011. 10.1098/rspa.2010.0301.
https://doi.org/10.1098/rspa.2010.0301
[17] M. J. Bremner, A. Montanaro, and D. J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, Aug 2016. 10.1103/PhysRevLett.117.080501.
https://doi.org/10.1103/PhysRevLett.117.080501
[18] E. Böhler, C. Glaßer, and D. Meister. Error-bounded probabilistic computations between $mathsf{MA}$ and $mathsf{AM}$. Journal of Computer and System Sciences, 72 (6): 1043–1076, 2006. 10.1016/j.jcss.2006.05.001.
https://doi.org/10.1016/j.jcss.2006.05.001
[19] C. Calabro, R. Impagliazzo, and R. Paturi. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, pages 75–85, 2009. 10.1007/978-3-642-11269-0_6.
https://doi.org/10.1007/978-3-642-11269-0_6
[20] M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, page 261–270, 2016. 10.1145/2840728.2840746.
https://doi.org/10.1145/2840728.2840746
[21] P. Clifford and R. Clifford. The classical complexity of boson sampling. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 146–155, 2018. 10.1137/1.9781611975031.10.
https://doi.org/10.1137/1.9781611975031.10
[22] A. M. Dalzell. Lower bounds on the classical simulation of quantum circuits for quantum supremacy. Bachelor’s thesis, Massachusetts Institute of Technology, 2017. URL http://hdl.handle.net/1721.1/111859.
http://hdl.handle.net/1721.1/111859
[23] H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and M. Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms, 10 (4), Aug 2014. 10.1145/2635812.
https://doi.org/10.1145/2635812
[24] E. Farhi and A. W. Harrow. Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674, 2016.
arXiv:1602.07674
[25] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.
arXiv:1411.4028
[26] S. Fenner, F. Green, S. Homer, and R. Pruim. Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 455 (1991): 3953–3966, 1999. 10.1098/rspa.1999.0485.
https://doi.org/10.1098/rspa.1999.0485
[27] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani. Power of quantum computation with few clean qubits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55, pages 13:1–13:14, 2016. 10.4230/LIPIcs.ICALP.2016.13.
https://doi.org/10.4230/LIPIcs.ICALP.2016.13
[28] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani. Impossibility of classically simulating one-clean-qubit model with multiplicative error. Phys. Rev. Lett., 120: 200502, May 2018. 10.1103/PhysRevLett.120.200502.
https://doi.org/10.1103/PhysRevLett.120.200502
[29] O. Goldreich and G. N. Rothblum. Worst-case to average-case reductions for subclasses of $P$. In Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation, pages 249–295. 2020. 10.1007/978-3-030-43662-9_15.
https://doi.org/10.1007/978-3-030-43662-9_15
[30] Y. Han, L. A. Hemaspaandra, and T. Thierauf. Threshold computation and cryptographic security. SIAM Journal on Computing, 26 (1): 59–78, 1997. 10.1137/S0097539792240467.
https://doi.org/10.1137/S0097539792240467
[31] D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert. Anticoncentration theorems for schemes showing a quantum speedup. Quantum, 2: 65, May 2018. 10.22331/q-2018-05-22-65.
https://doi.org/10.22331/q-2018-05-22-65
[32] A. W. Harrow and A. Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203–209, 2017. 10.1038/nature23458.
https://doi.org/10.1038/nature23458
[33] R. Hayakawa, T. Morimae, and S. Tamaki. Fine-grained quantum supremacy based on orthogonal vectors, 3-sum and all-pairs shortest paths. arXiv preprint arXiv:1902.08382, 2019.
arXiv:1902.08382
[34] C. Huang, M. Newman, and M. Szegedy. Explicit lower bounds on strong quantum simulation. arXiv preprint arXiv:1804.10368, 2018.
arXiv:1804.10368
[35] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63 (4): 512–530, 2001. 10.1006/jcss.2001.1774.
https://doi.org/10.1006/jcss.2001.1774
[36] H. Jahanjou, E. Miles, and E. Viola. Local reductions. In Automata, Languages, and Programming, pages 749–760, 2015. 10.1007/978-3-662-47672-7_61.
https://doi.org/10.1007/978-3-662-47672-7_61
[37] M. Jerrum and M. Snir. Some exact complexity results for straight-line computations over semirings. J. ACM, 29 (3): 874–897, Jul 1982. 10.1145/322326.322341.
https://doi.org/10.1145/322326.322341
[38] R. Jozsa and M. Van Den Nest. Classical simulation complexity of extended Clifford circuits. Quantum Information & Computation, 14 (7&8): 633–648, 2014. 10.26421/QIC14.7-8.
https://doi.org/10.26421/QIC14.7-8
[39] D. E. Koh. Further extensions of Clifford circuits and their classical simulation complexities. Quantum Information & Computation, 17 (3&4): 0262–0282, 2017. 10.26421/QIC17.3-4.
https://doi.org/10.26421/QIC17.3-4
[40] G. Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11 (1): 183–219, 2015. 10.4086/toc.2015.v011a006.
https://doi.org/10.4086/toc.2015.v011a006
[41] R. J. Lipton. New directions in testing. In Distributed Computing and Cryptography, volume 2, pages 191–202, 1989. 10.1090/dimacs/002/13.
https://doi.org/10.1090/dimacs/002/13
[42] D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, and H. Yu. Beating brute force for systems of polynomial equations over finite fields. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2190–2202. 2017. 10.1137/1.9781611974782.143.
https://doi.org/10.1137/1.9781611974782.143
[43] A. Montanaro. Quantum circuits and low-degree polynomials over $mathbb{F}_2$. Journal of Physics A: Mathematical and Theoretical, 50 (8): 084002, Jan 2017. 10.1088/1751-8121/aa565f.
https://doi.org/10.1088/1751-8121/aa565f
[44] T. Morimae and S. Tamaki. Additive-error fine-grained quantum supremacy. arXiv preprint arXiv:1912.06336, 2019a.
arXiv:1912.06336
[45] T. Morimae and S. Tamaki. Fine-grained quantum computational supremacy. Quantum Information & Computation, 19 (13&14): 1089–1115, 2019b. 10.26421/QIC19.13-14.
https://doi.org/10.26421/QIC19.13-14
[46] T. Morimae, K. Fujii, and J. F. Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett., 112: 130502, Apr 2014. 10.1103/PhysRevLett.112.130502.
https://doi.org/10.1103/PhysRevLett.112.130502
[47] T. Morimae, Y. Takeuchi, and H. Nishimura. Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy. Quantum, 2: 106, Nov 2018. 10.22331/q-2018-11-15-106.
https://doi.org/10.22331/q-2018-11-15-106
[48] R. Movassagh. Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of random circuit sampling. arXiv preprint arXiv:1810.04681, 2018.
arXiv:1810.04681
[49] R. Movassagh. Cayley path and quantum computational supremacy: A proof of average-case $# P$-hardness of random circuit sampling with quantified robustness. arXiv preprint arXiv:1909.06210, 2019.
arXiv:1909.06210
[50] A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing. Classical boson sampling algorithms with superior performance to near-term experiments. Nature Physics, 13 (12): 1153, 2017. 10.1038/nphys4270.
https://doi.org/10.1038/nphys4270
[51] J. Preskill. Quantum computing and the entanglement frontier. arXiv preprint arXiv:1203.5813, 2012.
arXiv:1203.5813
[52] P. Pudlák and R. Impagliazzo. A lower bound for DLL algorithms for $k$-SAT (preliminary version). In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, page 128–136, 2000. URL https://dl.acm.org/doi/abs/10.5555/338219.338244.
https://dl.acm.org/doi/abs/10.5555/338219.338244
[53] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani. Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73: 58–61, Jul 1994. 10.1103/PhysRevLett.73.58.
https://doi.org/10.1103/PhysRevLett.73.58
[54] M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter. Quantum resource estimates for computing elliptic curve discrete logarithms. In Advances in Cryptology – ASIACRYPT 2017, pages 241–270, 2017. 10.1007/978-3-319-70697-9_9.
https://doi.org/10.1007/978-3-319-70697-9_9
[55] H. J. Ryser. Combinatorial mathematics, volume 14. 1963. 10.5948/UPO9781614440147.
https://doi.org/10.5948/UPO9781614440147
[56] D. Shepherd and M. J. Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465 (2105): 1413–1439, 2009. 10.1098/rspa.2008.0443.
https://doi.org/10.1098/rspa.2008.0443
[57] L. Stockmeyer. The complexity of approximate counting. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, page 118–126, 1983. 10.1145/800061.808740.
https://doi.org/10.1145/800061.808740
[58] B. M. Terhal and D. P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quantum Information & Computation, 4 (2): 134–145, 2004. 10.26421/QIC4.2.
https://doi.org/10.26421/QIC4.2
[59] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20 (5): 865–877, 1991. 10.1137/0220053.
https://doi.org/10.1137/0220053
[60] S. Toda and M. Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 21 (2): 316–328, 1992. 10.1137/0221023.
https://doi.org/10.1137/0221023
[61] L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8 (2): 189 – 201, 1979. 10.1016/0304-3975(79)90044-6.
https://doi.org/10.1016/0304-3975(79)90044-6
[62] M. Vyalyi. $QMA$$=$$PP$ implies that $PP$ contains $PH$. In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports, 2003. URL https://eccc.weizmann.ac.il/report/2003/021/.
https://eccc.weizmann.ac.il/report/2003/021/
[63] R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348 (2): 357–365, 2005. 10.1016/j.tcs.2005.09.023.
https://doi.org/10.1016/j.tcs.2005.09.023
[64] R. Williams and H. Yu. Finding orthogonal vectors in discrete structures. In Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1867–1877. 2014. 10.1137/1.9781611973402.135.
https://doi.org/10.1137/1.9781611973402.135
[65] R. R. Williams. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In 31st Conference on Computational Complexity (CCC 2016), volume 50, pages 2:1–2:17, 2016. 10.4230/LIPIcs.CCC.2016.2.
https://doi.org/10.4230/LIPIcs.CCC.2016.2
[66] V. V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), volume 43, pages 17–29, 2015. 10.4230/LIPIcs.IPEC.2015.17.
https://doi.org/10.4230/LIPIcs.IPEC.2015.17
[67] A. R. Woods. Unsatisfiable systems of equations, over a finite field. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 202–211, 1998. 10.1109/SFCS.1998.743444.
https://doi.org/10.1109/SFCS.1998.743444
Cited by
[1] Daniel Jost Brod and Michał Oszmaniec, “Classical simulation of linear optics subject to nonuniform losses”, Quantum 4, 267 (2020).
[2] Gavin E. Crooks, “Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem”, arXiv:1811.08419.
[3] P. Krantz, M. Kjaergaard, F. Yan, T. P. Orlando, S. Gustavsson, and W. D. Oliver, “A quantum engineer’s guide to superconducting qubits”, Applied Physics Reviews 6 2, 021318 (2019).
[4] Thomas Hummel, Claudéric Ouellet-Plamondon, Ela Ugur, Irina Kulkova, Toke Lund-Hansen, Matthew A. Broome, Ravitej Uppu, and Peter Lodahl, “Efficient demultiplexed single-photon source with a quantum dot coupled to a nanophotonic waveguide”, Applied Physics Letters 115 2, 021102 (2019).
[5] Matthew Coudron, Jalex Stark, and Thomas Vidick, “Trading locality for time: certifiable randomness from low-depth circuits”, arXiv:1810.04233.
[6] Tomoyuki Morimae and Suguru Tamaki, “Fine-grained quantum computational supremacy”, arXiv:1901.01637.
[7] Michał Oszmaniec and Daniel J. Brod, “Classical simulation of photonic linear optics with lost particles”, New Journal of Physics 20 9, 092002 (2018).
[8] Ming-Cheng Chen, Riling Li, Lin Gan, Xiaobo Zhu, Guangwen Yang, Chao-Yang Lu, and Jian-Wei Pan, “Quantum-Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits”, Physical Review Letters 124 8, 080502 (2020).
[9] Samuele Ferracin, Theodoros Kapourniotis, and Animesh Datta, “Accrediting outputs of noisy intermediate-scale quantum computing devices”, arXiv:1811.09709.
[10] Ryu Hayakawa, Tomoyuki Morimae, and Suguru Tamaki, “Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths”, arXiv:1902.08382.
[11] Ramis Movassagh, “Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling”, arXiv:1810.04681.
[12] Jacob D. Biamonte, Mauro E. S. Morales, and Dax Enshan Koh, “Entanglement Scaling in Quantum Advantage Benchmarks”, arXiv:1808.00460.
[13] Mikkel V. Larsen, Xueshi Guo, Casper R. Breum, Jonas S. Neergaard-Nielsen, and Ulrik L. Andersen, “Fiber-coupled EPR-state generation using a single temporally multiplexed squeezed light source”, npj Quantum Information 5, 46 (2019).
[14] Will Finigan, Michael Cubeddu, Thomas Lively, Johannes Flick, and Prineha Narang, “Qubit Allocation for Noisy Intermediate-Scale Quantum Computers”, arXiv:1810.08291.
[15] Abhinav Deshpande, Bill Fefferman, Minh C. Tran, Michael Foss-Feig, and Alexey V. Gorshkov, “Dynamical Phase Transitions in Sampling Complexity”, Physical Review Letters 121 3, 030501 (2018).
[16] Daniel Jost Brod and Michał Oszmaniec, “Classical simulation of linear optics subject to nonuniform losses”, arXiv:1906.06696.
[17] Pak Hong Leung and Kenneth R. Brown, “Entangling an arbitrary pair of qubits in a long ion crystal”, Physical Review A 98 3, 032318 (2018).
[18] Ramis Movassagh, “Cayley path and quantum computational supremacy: A proof of average-case $#P-$hardness of Random Circuit Sampling with quantified robustness”, arXiv:1909.06210.
[19] Kaifeng Bu and Dax Enshan Koh, “Classical simulation of quantum circuits by half Gauss sums”, arXiv:1812.00224.
[20] Deanna M. Abrams, Nicolas Didier, Blake R. Johnson, Marcus P. da Silva, and Colm A. Ryan, “Implementation of the XY interaction family with calibration of a single pulse”, arXiv:1912.04424.
[21] Iskren Vankov, Daniel Mills, Petros Wallden, and Elham Kashefi, “Methods for classically simulating noisy networked quantum architectures”, Quantum Science and Technology 5 1, 014001 (2020).
[22] Michael Cubeddu, Will Finigan, Thomas Lively, Johannes Flick, and Prineha Narang, “Introducing Control Flow in Qubit Allocation for Quantum Turing Machines”, arXiv:1907.07113.
[23] Alexander Zlokapa, Sergio Boixo, and Daniel Lidar, “Boundaries of quantum supremacy via random circuit sampling”, arXiv:2005.02464.
[24] Jacob D. Biamonte, Mauro E. S. Morales, and Dax Enshan Koh, “Entanglement scaling in quantum advantage benchmarks”, Physical Review A 101 1, 012349 (2020).
[25] Tomoyuki Morimae, Yuki Takeuchi, and Seiichiro Tani, “Sampling of globally depolarized random quantum circuit”, arXiv:1911.02220.
[26] Tomoyuki Morimae and Suguru Tamaki, “Additive-error fine-grained quantum supremacy”, arXiv:1912.06336.
The above citations are from Crossref’s cited-by service (last updated successfully 2020-06-03 16:29:27) and SAO/NASA ADS (last updated successfully 2020-06-03 16:29:28). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Source: https://quantum-journal.org/papers/q-2020-05-11-264/
