Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1111.0475 · Algorithmica

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

Published Aug 29, 2013• 48 citations
arXivHTMLPDF
DOI
10.1007/s00453-013-9826-8

Related papers

On the exact quantum query complexity of MOD and EXACT functions

Penghui Yao, Zekun Ye

arXiv:2303.10935•Frontiers of Computer Science•Nov 22, 2024•2 citations

Evaluation of exact quantum query complexities by semidefinite programming

Kıvanç Uyanık

Quantum Information Processing•Apr 26, 2019•1 citation

Nonadaptive quantum query complexity

Ashley Montanaro

arXiv:1001.0018•Information Processing Letters•Sep 22, 2010•16 citations

Exact Quantum 1-Query Algorithms and Complexity

Daowen Qiu, Guoliang Xu

Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.

SPIN•Aug 12, 2021•5 citations

Exact quantum algorithms have advantage for almost all Boolean functions

Andris Ambainis, Jozef Gruska, Shenggen Zheng

It has been proved that almost all n-bit Boolean functions have exact classical query complexity n. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all n-bit Boolean functions can be computed by an exact quantum algorithm with less than n queries. More exactly, we prove that ANDn is the only n-bit Boolean function, up to isomorphism, that requires n queries.

arXiv:1404.1684•Quantum Information and Computation•Apr 1, 2015•23 citations

From Quantum Query Complexity to State Complexity

Shenggen Zheng, Daowen Qiu

arXiv:1407.7342•Lecture notes in computer science•Jan 1, 2014•11 citations
Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.