Document Open Access Logo

An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes

Authors Atsuya Hasegawa, François Le Gall

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.6.pdf
  • Filesize: 1.14 MB
  • 14 pages

Document Identifiers

Author Details

Atsuya Hasegawa
  • Graduate School of Information Science and Technology, The University of Tokyo, Japan
François Le Gall
  • Graduate School of Mathematics, Nagoya University, Japan

Funding

JSPS KAKENHI grants Nos. JP16H01705, JP19H04066, JP20H00579, JP20H04139, JP22J22563 and the MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grant No. JPMXS0120319794.

Acknowledgements

The authors are grateful to Nai-Hui Chia for helpful discussions. They are also grateful to Atul Singh Arora, Alexandru Gheorghiu and Uttam Singh for sharing the information about their result [Arora et al., 2022].

Cite AsGet BibTex

Atsuya Hasegawa and François Le Gall. An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.6

Abstract

Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle 𝒪 such that BQP^𝒪 ≠ (BPP^BQNC)^𝒪 ∪ (BQNC^BPP)^𝒪. In fact, Chia et al. proved a stronger statement: for any depth parameter d, there exists an oracle that separates quantum depth d and 2d+1, when polynomial-time classical computation is allowed. This implies that relative to an oracle, doubling quantum depth gives classical and quantum hybrid schemes more computational power. In this paper, we show that for any depth parameter d, there exists an oracle that separates quantum depth d and d+1, when polynomial-time classical computation is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes. To prove our result, we consider d-Bijective Shuffling Simon’s Problem (which is a variant of d-Shuffling Simon’s Problem considered by Chia et al.) and an oracle inspired by an "in-place" permutation oracle.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • small-depth quantum circuit
  • hybrid quantum computer
  • oracle separation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. URL: https://en.wikipedia.org/wiki/List_of_quantum_processors.
  2. Scott Aaronson. Quantum lower bound for the collision problem. In Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002), pages 635-642, 2002. URL: https://doi.org/10.1145/509907.509999.
  3. Scott Aaronson. Ten semi-grand challenges for quantum computing theory, 2005. URL: https://www.scottaaronson.com/writings/qchallenge.html.
  4. Scott Aaronson. BQP and the polynomial hierarchy. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pages 141-150, 2010. URL: https://doi.org/10.1145/1806689.1806711.
  5. Scott Aaronson. Projects aplenty, 2011. URL: https://scottaaronson.blog/?p=663.
  6. Andris Ambainis, Mike Hamburg, and Dominique Unruh. Quantum security proofs using semi-classical oracles. In Advances in Cryptology – CRYPTO 2019, volume 11693 of Lecture Notes in Computer Science, pages 269-295. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26951-7_10.
  7. Atul Singh Arora, Alexandru Gheorghiu, and Uttam Singh. Oracle separations of hybrid quantum-classical circuits. arXiv, 2022. URL: https://doi.org/10.48550/arXiv.2201.01904.
  8. Frank Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505-510, 2019. URL: https://doi.org/10.1038/s41586-019-1666-5.
  9. Marco Cerezo et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625-644, 2021. URL: https://doi.org/10.1038/s42254-021-00348-9.
  10. Nai-Hui Chia. Personal communication, 2022. Google Scholar
  11. Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai. On the need for large quantum depth. In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020), pages 902-915, 2020. URL: https://doi.org/10.1145/3357713.3384291.
  12. Nai-Hui Chia and Shih-Han Hung. Classical verification of quantum depth. arXiv, 2022. URL: https://doi.org/10.48550/arXiv.2205.04656.
  13. Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC 2003), pages 59-68, 2003. URL: https://doi.org/10.1145/780542.780552.
  14. Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings of 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2000), pages 526-536, 2000. URL: https://doi.org/10.1109/SFCS.2000.892140.
  15. Matthew Coudron and Sanketh Menda. Computations with greater quantum depth are strictly more powerful (relative to an oracle). In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020), pages 889-901, 2020. URL: https://doi.org/10.1145/3357713.3384269.
  16. Bill Fefferman and Shelby Kimmel. Quantum vs. classical proofs and subset verification. In Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), pages 22:1-22:23, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.22.
  17. Stephen A Fenner and Yong Zhang. A note on the classical lower bound for a quantum walk algorithm. arXiv, 2003. URL: https://doi.org/10.48550/arXiv.quant-ph/0312230.
  18. Richard Jozsa. An introduction to measurement based quantum computation. arXiv, 2005. URL: https://doi.org/10.48550/arXiv.quant-ph/0508124.
  19. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511976667.
  20. Daniel R. Simon. On the power of quantum computation. In Proceedings of 35th IEEE Annual Symposium on Foundations of Computer Science (FOCS 1994), pages 116-123, 1994. URL: https://doi.org/10.1109/SFCS.1994.365701.
  21. Dominique Unruh. Revocable quantum timed-release encryption. Journal of the ACM, 62(6):1-76, 2015. URL: https://doi.org/10.1145/2817206.
  22. Han-Sen Zhong et al. Quantum computational advantage using photons. Science, 370:1460-1463, 2020. URL: https://doi.org/10.1126/science.abe8770.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact