Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy

Tomoyuki Morimae; Yuki Takeuchi; Harumichi Nishimura

doi:10.22331/q-2018-11-15-106

Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy

Tomoyuki Morimae^1,2,3, Yuki Takeuchi^4,5, and Harumichi Nishimura⁶

¹Yukawa Institute for Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyo-ku, Kyoto 606-8502, Japan
²Department of Computer Science, Gunma University, 1-5-1 Tenjincho, Kiryu, Gunma, 376-0052, Japan
³JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012, Japan
⁴Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka 560-8531, Japan
⁵NTT Communication Science Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan
⁶Graduate School of Informatics, Nagoya University, Furocho, Chikusaku, Nagoya, Aichi, 464-8601, Japan

Published:	2018-11-15, volume 2, page 106
Eprint:	arXiv:1711.10605v3
Doi:	https://doi.org/10.22331/q-2018-11-15-106
Citation:	Quantum 2, 106 (2018).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We introduce a simple sub-universal quantum computing model, which we call the Hadamard-classical circuit with one-qubit (HC1Q) model. It consists of a classical reversible circuit sandwiched by two layers of Hadamard gates, and therefore it is in the second level of the Fourier hierarchy. We show that output probability distributions of the HC1Q model cannot be classically efficiently sampled within a multiplicative error unless the polynomial-time hierarchy collapses to the second level. The proof technique is different from those used for previous sub-universal models, such as IQP, Boson Sampling, and DQC1, and therefore the technique itself might be useful for finding other sub-universal models that are hard to classically simulate. We also study the classical verification of quantum computing in the second level of the Fourier hierarchy. To this end, we define a promise problem, which we call the probability distribution distinguishability with maximum norm (PDD-Max). It is a promise problem to decide whether output probability distributions of two quantum circuits are far apart or close. We show that PDD-Max is BQP-complete, but if the two circuits are restricted to some types in the second level of the Fourier hierarchy, such as the HC1Q model or the IQP model, PDD-Max has a Merlin-Arthur system with quantum polynomial-time Merlin and classical probabilistic polynomial-time Arthur.

► BibTeX data

@article{Morimae2018merlinarthur,
  doi = {10.22331/q-2018-11-15-106},
  url = {https://doi.org/10.22331/q-2018-11-15-106},
  title = {Merlin-{A}rthur with efficient quantum {M}erlin and quantum supremacy for the second level of the {F}ourier hierarchy},
  author = {Morimae, Tomoyuki and Takeuchi, Yuki and Nishimura, Harumichi},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {2},
  pages = {106},
  month = nov,
  year = {2018}
}

► References

[1] Y. Shi, Quantum and classical tradeoffs. Theoretical Computer Science 344, 335 (2005). DOI:10.1016/j.tcs.2005.03.053.
https://doi.org/10.1016/j.tcs.2005.03.053

[2] D. R. Simon, On the power of quantum computation. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), p.116 (1994). DOI:10.1137/S0097539796298637.
https://doi.org/10.1137/S0097539796298637

[3] P. Shor, Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), p.124 (1994). DOI:10.1109/SFCS.1994.365700.
https://doi.org/10.1109/SFCS.1994.365700

[4] M. J. Bremner, R. Jozsa, and D. J. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A 467, 459 (2011). DOI:10.1098/rspa.2010.0301.
https://doi.org/10.1098/rspa.2010.0301

[5] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016). DOI:10.1103/PhysRevLett.117.080501.
https://doi.org/10.1103/PhysRevLett.117.080501

[6] B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quant. Inf. Comput. 4, 134 (2004). DOI:10.26421/QIC4.2.
https://doi.org/10.26421/QIC4.2

[7] S. Aaronson and A. Arkhipov, The computational complexity of linear optics. Theory of Computing 9, 143 (2013). DOI:10.1145/1993636.1993682.
https://doi.org/10.1145/1993636.1993682

[8] E. Knill, and R. Laflamme, Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672 (1998). DOI:10.1103/PhysRevLett.81.5672.
https://doi.org/10.1103/PhysRevLett.81.5672

[9] T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one clean qubit model. Phys. Rev. Lett. 112, 130502 (2014). DOI:10.1103/PhysRevLett.112.130502.
https://doi.org/10.1103/PhysRevLett.112.130502

[10] T. Morimae, Hardness of classically sampling one clean qubit model with constant total variation distance error. Phys. Rev. A 96, 040302(R) (2017). DOI:10.1103/PhysRevA.96.040302.
https://doi.org/10.1103/PhysRevA.96.040302

[11] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Impossibility of classically simulating one-clean-qubit computation. Phys. Rev. Lett. 120, 200502 (2018). DOI:10.1103/PhysRevLett.120.200502.
https://doi.org/10.1103/PhysRevLett.120.200502

[12] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Power of quantum computation with few clean qubits. Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), p.13:1. DOI:10.4230/LIPIcs.ICALP.2016.13.
https://doi.org/10.4230/LIPIcs.ICALP.2016.13

[13] B. Fefferman and C. Umans, The power of quantum Fourier sampling. arXiv:1507.05592.
arXiv:1507.05592

[14] A. Bouland, J. F. Fitzsimons, and D. E. Koh, Quantum advantage from conjugated Clifford circuits. Proceedings of the 33rd Computational Complexity Conference (CCC2018). DOI: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. Nat. Phys. 2018 DOI:10.1038/s41567-018-0318-2.
https://doi.org/10.1038/s41567-018-0318-2

[16] D. Aharonov and U. Vazirani, Is quantum mechanics falsifiable? A computational perspective on the foundations of quantum mechanics. arXiv:1206.3686.
arXiv:1206.3686

[17] T. Morimae, D. Nagaj, and N. Schuch, Quantum proofs can be verified using only single-qubit measurements. Phys. Rev. A 93, 022326 (2016). DOI:10.1103/PhysRevA.93.022326.
https://doi.org/10.1103/PhysRevA.93.022326

[18] J. F. Fitzsimons, M. Hajdušek, and T. Morimae, Post hoc verification of quantum computation. Phys. Rev. Lett. 120, 040501 (2018). DOI:10.1103/PhysRevLett.120.040501.
https://doi.org/10.1103/PhysRevLett.120.040501

[19] J. F. Fitzsimons and E. Kashefi, Unconditionally verifiable blind computation. Phys. Rev. A 96, 012303 (2017). DOI:10.1103/PhysRevA.96.012303.
https://doi.org/10.1103/PhysRevA.96.012303

[20] D. Aharonov, M. Ben-Or, E. Eban, and U. Mahadev, Interactive proofs for quantum computations. arXiv:1704.04487.
arXiv:1704.04487

[21] M. Hayashi and T. Morimae, Verifiable measurement-only blind quantum computing with stabilizer testing. Phys. Rev. Lett. 115, 220502 (2015). DOI:10.1103/PhysRevLett.115.220502.
https://doi.org/10.1103/PhysRevLett.115.220502

[22] A. Broadbent, How to verify quantum computation. Theory of Computing 14, 1 (2018). DOI:10.4086/toc.2018.v014a011.
https://doi.org/10.4086/toc.2018.v014a011

[23] A. Gheorghiu, T. Kapourniotis, and E. Kashefi, Verification of quantum computation: an overview of existing approaches. DOI:10.1007/s00224-018-9872-3.
https://doi.org/10.1007/s00224-018-9872-3

[24] M. McKague, Interactive proofs for BQP via self-tested graph states. Theory of Computing 12, 1 (2016). DOI:10.4086/toc.2016.v012a003.
https://doi.org/10.4086/toc.2016.v012a003

[25] Z. Ji, Classical verification of quantum proofs. Proceedings of the 48th annual ACM symposium on Theory of Computing (STOC 2016) p.885 (2016). DOI:10.1145/2897518.2897634.
https://doi.org/10.1145/2897518.2897634

[26] B. W. Reichardt, F. Unger, and U. Vazirani, Classical command of quantum systems. Nature 496, 456 (2013). DOI:10.1038/nature12035.
https://doi.org/10.1038/nature12035

[27] D. Aharonov and A. Green, A quantum inspired proof of ${\rm P}^{\# {\rm P}}\subseteq {\rm IP}$. arXiv:1710.09078.
arXiv:1710.09078

[28] U. Mahadev, Classical verification of quantum computations. arXiv:1804.01082.
arXiv:1804.01082

[29] E. Bernstein and U. Vazirani, Quantum complexity theory. SIAM Journal on Computing 26, 1411 (1997). DOI:10.1137/S0097539796300921.
https://doi.org/10.1137/S0097539796300921

[30] M. McKague, Interactive proofs with efficient quantum prover for recursive Fourier sampling. Chicago Journal of Theoretical Computer Science 6, 1 (2012). DOI:10.4086/cjtcs.0006.
https://doi.org/10.4086/cjtcs.0006

[31] T. F. Demarie, Y. Ouyang, and J. F. Fitzsimons, Classical verification of quantum circuits containing few basis changes. Phys. Rev. A 97, 042319 (2018). DOI:10.1103/PhysRevA.97.042319.
https://doi.org/10.1103/PhysRevA.97.042319

[32] F. Le Gall, T. Morimae, H. Nishimura, and Y. Takeuchi, Interactive proofs with polynomial-time quantum prover for computing the order of solvable groups. arXiv:1805.03385.
arXiv:1805.03385

[33] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, H. Weinfurter, Elementary gates for quantum computation. Phys. Rev. A 52 3457 (1995). DOI:10.1103/PhysRevA.52.3457.
https://doi.org/10.1103/PhysRevA.52.3457

[34] L. M. Adleman, J. DeMarrais, and M. A. Huang, Quantum Computability. SIAM J. Comput. 26 1524 (1997). DOI:10.1137/S0097539795293639.
https://doi.org/10.1137/S0097539795293639

[35] M. Schwarz and M. Van den Nest, Simulating quantum circuits with sparse output distributions. arXiv:1310.6749.
arXiv:1310.6749

[36] R. Canetti, G. Even, and O. Goldreich, Lower bounds for sampling algorithms for estimating the average. Information Processing Letters 53, 17 (1995).

Cited by

[1] Alexander M. Dalzell, Aram W. Harrow, Dax Enshan Koh, and Rolando L. La Placa, "How many qubits are needed for quantum computational supremacy?", Quantum 4, 264 (2020).

[2] Yuki Takeuchi, Yasuhiro Takahashi, and Seiichiro Tani, "Hardness of efficiently generating ground states in postselected quantum computation", Physical Review Research 3 1, 013213 (2021).

[3] Seiseki Akibue, Yuki Takeuchi, Yasuhiro Takahashi, Go Kato, and Seiichiro Tani, "Theoretical Approach to Overcome Difficulties in Implementing Quantum Computers", NTT Technical Review 19 5, 34 (2021).

[4] Mariami Gachechiladze, Otfried Gühne, and Akimasa Miyake, "Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states", Physical Review A 99 5, 052304 (2019).

[5] Yuki Takeuchi, Tomoyuki Morimae, and Seiichiro Tani, "Sumcheck-based delegation of quantum computing to rational server", Theoretical Computer Science 924, 46 (2022).

[6] Tomoyuki Morimae and Suguru Tamaki, "Additive-error fine-grained quantum supremacy", Quantum 4, 329 (2020).

[7] Kaifeng Bu and Dax Enshan Koh, "Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States", Physical Review Letters 123 17, 170502 (2019).

[8] Masahito Hayashi and Yuki Takeuchi, "Verifying commuting quantum computations via fidelity estimation of weighted graph states", New Journal of Physics 21 9, 093060 (2019).

[9] Keisuke Fujii, "Quantum speedup in stoquastic adiabatic quantum computation", arXiv:1803.09954, (2018).

[10] François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, and Yuki Takeuchi, "Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups", arXiv:1805.03385, (2018).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-13 10:23:16) and SAO/NASA ADS (last updated successfully 2024-08-13 10:23:16). 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.