AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Characterization of Exact One-Query Quantum Algorithms for Partial Boolean Functions

Institute of Quantum Computing and Computer Theory, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China
Ministry of Education Key Laboratory of Machine Intelligence and Advanced Computing, Sun Yat-sen University Guangzhou 510006, China
Show Author Information

Abstract

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. In the history of quantum algorithms, the Deutsch algorithm and the Deutsch-Jozsa algorithm play a fundamental role and both are exact one-query quantum algorithms. This leads us to consider the problem: what functions can be computed by exact one-query quantum algorithms? This problem has been addressed in the literature for total Boolean functions and symmetric partial Boolean functions, but is still open for general partial Boolean functions. Thus, in this paper, we continue to characterize the computational power of exact one-query quantum algorithms for general partial Boolean functions. First, we present several necessary and sufficient conditions for a partial Boolean function to be computed by exact one-query quantum algorithms. Second, inspired by these conditions, we discover some new representative functions that can be computed by exact one-query quantum algorithms but have an essential difference from the already known ones. Specially, it is worth pointing out that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions and the quantum algorithm used is essentially the Deutsch-Jozsa algorithm, whereas the functions discovered in this paper are generally asymmetric and new algorithms to compute these functions are required. Thus, this expands the class of functions that can be computed by exact one-query quantum algorithms.

Keywords

quantum computingquantum query complexityquantum algorithm

Electronic Supplementary Material

Download File(s)
JCST-2102-11361-Highlights.pdf (128.7 KB)

References

[1]

Buhrman H, De Wolf R. Complexity measures and decision tree complexity: A survey. Theoretical Computer Science , 2002, 288(1): 21–43. DOI: 10.1016/S0304-3975(01)00144-X.
Crossref Google Scholar
[2]

Chen W, Ye Z, Li L. Characterization of exact one-query quantum algorithms. Physical Review A , 2020, 101(2): 02232. DOI: 10.1103/PhysRevA.101.022325.
Crossref Google Scholar
[3]

Ambainis A. Superlinear advantage for exact quantum algorithms. SIAM Journal on Computing , 2016, 45(2): 617–631. DOI: 10.1137/130939043.
Crossref Google Scholar
[4]

Ambainis A, Gruska J, Zheng S. Exact quantum algorithms have advantage for almost all Boolean functions. Quantum Information and Computation , 2015, 15(5/6): 435–452. DOI: 0.26421/QIC15.5-6-5.
Crossref Google Scholar
[5]

Deutsch D, Jozsa R. Rapid solution of problems by quantum computation. Proceedings of the Royal Society A: Mathematical and Physical Sciences , 1992, 439(1907): 553–558. DOI: 10.1098/rspa.1992.0167.
Crossref Google Scholar
[6]

Mihara T, Sung S. Deterministic polynomial-time quantum algorithms for Simon’s problem. Computational Complexity , 2003, 12(3/4): 162–175. DOI: 10.1007/s00037-003-0181-z.
Crossref Google Scholar
[7]
He X, Sun X, Yang G, Yuan P. Exact quantum query complexity of weight decision problems via Chebyshev polynomials. arXiv: 1801.05717, 2018. https://arxiv.org/abs/1801.05717, Feb. 2021.
[8]

Montanaro A, Jozsa R, Mitchison G. On exact quantum query complexity. Algorithmica , 2013, 71(4): 775–796. DOI: 10.1007/s00453-013-9826-8.
Crossref Google Scholar
[9]
Ambainis A, Iraids J, Smotrovs J. Exact quantum query complexity of EXACT and THRESHOLD. In Proc. the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, May 2013, pp.263–269. DOI: 10.4230/LIPIcs.TQC.2013.263.
[10]
Ambainis A, Iraids J, Nagaj D. Exact quantum query complexity of EXACTk,ln. In Proc. the 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Jan. 2017, pp.243–255. DOI: 10.1007/978-3-319-51963-0_19.
Crossref
[11]

Cai G, Qiu D. Optimal separation in exact query complexities for Simon’s problem. Journal of Computer and System Sciences , 2018, 97: 83–93. DOI: 10.1016/j.jcss.2018.05.001.
Crossref Google Scholar
[12]
Aaronson S, Ben-David S, Kothari R. Separations in query complexity using cheat sheets. In Proc. the 48th Annual ACM Symposium on Theory of Computing, Jun. 2016, pp.863–876. DOI: 10.1145/2897518.2897644.
Crossref
[13]

Ambainis A, Balodis K, Belovs A, Lee T, Santha M, Smotrovs J. Separations in query complexity based on pointer functions. Journal of the ACM , 2017, 64(5): Article No. 32. DOI: 10.1145/3106234.
Crossref Google Scholar
[14]

Farhi E, Goldstone J, Gutmann S, Sipser M. Limit on the speed of quantum computation in determining parity. Physical Review Letters , 1998, 81(24): 5442–5444. DOI: 10.1103/PhysRevLett.81.5442.
Crossref Google Scholar
[15]

Hayes T, Kutin S, Van Melkebeek D. The Quantum black-box complexity of majority. Algorithmica , 2002, 34(4): 480–501. DOI: 10.1007/s00453-002-0981-6.
Crossref Google Scholar
[16]
Brassard G, Høyer P. An exact quantum polynomial-time algorithm for Simon’s problem. In Proc. the 5th Israel Symposium on Theory of Computing and Systems, Jun. 1997, pp.12–23. DOI: 10.1109/ISTCS.1997.595153.
Crossref
[17]

Qiu D, Zheng S. Generalized Deutsch-Jozsa problem and the optimal quantum algorithm. Physical Review A , 2018, 97(6): 062331. DOI: 10.1103/PhysRevA.97.062331.
Crossref Google Scholar
[18]

Qiu D, Zheng S. Revisiting Deutsch-Jozsa algorithm. Information and Computation , 2020, 275: 104605. DOI: 10.1016/j.ic.2020.104605.
Crossref Google Scholar
[19]
Aaronson S, Ambainis A, Iraids J, Kokainis M, Smotrovs J. Polynomials, quantum query complexity, and Grothendieck’s Inequality. In Proc. the 31st Conference on Computational Complexity, May 29–June 1, 2016, Article No. 25. DOI: 10.4230/LIPIcs.CCC.2016.25.
Crossref
[20]

Arunachalam S, Briët J, Palazuelos C. Quantum query algorithms are completely bounded forms. SIAM Journal on Computing , 2019, 48(3): 903–925. DOI: 10.1137/18M11 7563X.
Crossref Google Scholar
[21]

Beals R, Buhrman H, Cleve R, Mosca M, De Wolf R. Quantum lower bounds by polynomials. Journal of the ACM , 2001, 48(4): 778–797. DOI: 10.1145/502090.502097.
Crossref Google Scholar
[22]

Simon D R. On the power of quantum computation. SIAM Journal on Computing , 1997, 26(5): 1474–1483. DOI: 10.1137/S0097539796298637.
Crossref Google Scholar
[23]
Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proc. the 35th Annual Symposium on Foundations of Computer Science, Nov. 1994, pp.124–134. DOI: 10.1109/SFCS.1994.365700.
Crossref
[24]
Ben-David S, Childs A M, Gilyén A, Kretschmer W, Podder S, Wang D. Symmetries, graph properties, and quantum speedups. In Proc. the 61st IEEE Annual Symposium on Foundations of Computer Science, Nov. 2020, pp.649–660. DOI: 10.1109/FOCS46700.2020.00066.
Crossref
[25]

Aaronson S, Ambainis A. Forrelation: A problem that optimally separates quantum from classical computing. SIAM Journal on Computing , 2018, 47(3): 982–1038. DOI: 10.1137/15M1050902.
Crossref Google Scholar
[26]
Tal A. Towards optimal separations between quantum and randomized query complexities. In Proc. the 61st IEEE Annual Symposium on Foundations of Computer Science, Nov. 2020, pp.228–239. DOI: 10.1109/FOCS46700.2020.00030.
Crossref
[27]
Bansal N, Sinha M. k-Forrelation optimally separates quantum and classical query complexity. In Proc. the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Jun. 2021, pp.1303–1316. DOI: 10.1145/3406325.3451040.
Crossref
[28]
Sherstov A A, Storozhenko A A, Wu P. An optimal separation of randomized and quantum query complexity. In Proc. the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Jun. 2021, pp.1289–1302. DOI: 10.1145/3406325.3451019.
Crossref
[29]

Xu G, Qiu D. Partial Boolean functions with exact quantum 1-query complexity. Entropy , 2021, 23(2): 189. DOI: 10.3390/e23020189.
Crossref Google Scholar
[30]
Nielsen M A, Chuang I. Quantum Computation and Quantum Information. Cambridge University Press, 2002.
Crossref
Journal of Computer Science and Technology
Volume 38 Issue 6,
November 2023
Pages 1423-1430
DOI: 10.1007/s11390-022-1361-0
Cite this article:
Ye Z-K, Li L-Z. Characterization of Exact One-Query Quantum Algorithms for Partial Boolean Functions. Journal of Computer Science and Technology, 2023, 38(6): 1423-1430. https://doi.org/10.1007/s11390-022-1361-0

169

Views

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 07 February 2021
Accepted: 23 March 2022
Published: 15 November 2023
© Institute of Computing Technology, Chinese Academy of Sciences 2023
Return