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

Lecture notes in computer science

Quantum Query Complexity of Boolean Functions with Small On-Sets

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita

Published Jan 1, 2008• 11 citations
Publisher
DOI
10.1007/978-3-540-92182-0_79

Related papers

Query Complexity of Boolean Functions on the Middle Slice of the Cube

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy +4 more

•Jan 1, 2023•0 citations

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4 more

Computational Complexity•Jun 21, 2016•3 citations

Quantum speedups in query complexity

Shalev Ben-David

In this thesis, we study randomized and quantum algorithms in the query complexity model.We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting.We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm.In the process, we introduce the "cheat sheet" method for turning partial Boolean functions into total Boolean functions, and examine some of its other applications.We also study lower bound techniques for randomized algorithms.We introduce a measure called randomized sabotage complexity which lower bounds randomized query complexity and behaves well under compositions.This tool for controlling the randomized query complexity of composed functions combines nicely with the cheat sheet technique, which often features composed functions in its applications.In addition, we study the quantum analogue of this tool, and use it to show a new power 5 relationship between zero-error and bounded-error quantum query complexity.Finally, we characterize the total Boolean functions that exhibit exponential quantum speedups when their domain is restricted to an arbitrarily chosen set.We show that such a "sculpting" of a quantum speedup is possible if and only if the original total function has many inputs with large certificate complexity.Along the way, we also show that functions defined on very small domains or that are very unbalanced can display at most a quadratic quantum speedup.

•Jan 1, 2017•0 citations

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

arXiv:1111.0475•Algorithmica•Aug 29, 2013•48 citations

Characterizations of symmetrically partial Boolean functions with exact quantum query complexity

Daowen Qiu, Shenggen Zheng

We give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the promise problem (i.e., symmetric and partial Boolean function) $DJ_n^k$ defined as: $DJ_n^k(x)=1$ for $|x|=n/2$, $DJ_n^k(x)=0$ for $|x|$ in the set $\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}$, and it is undefined for the rest cases, where $n$ is even, $|x|$ is the Hamming weight of $x$. The case of $k=0$ is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function $f$ has exact quantum 1-query complexity if and only if $f$ can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight $\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}$ and Hamming weight in the set $\{ 0, n\}$ for all odd $n$. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.

arXiv:1603.06505•Mar 21, 2016•12 citations

The Quantum Query Complexity of Algebraic Properties

Sebastian Dörn, Thomas Thierauf

Lecture notes in computer science•Aug 27, 2007•20 citations
In this thesis, we study randomized and quantum algorithms in the query complexity model.We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting.We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm.In the process, we introduce the "cheat sheet" method for turning partial Boolean functions into total Boolean functions, and examine some of its other applications.We also study lower bound techniques for randomized algorithms.We introduce a measure called randomized sabotage complexity which lower bounds randomized query complexity and behaves well under compositions.This tool for controlling the randomized query complexity of composed functions combines nicely with the cheat sheet technique, which often features composed functions in its applications.In addition, we study the quantum analogue of this tool, and use it to show a new power 5 relationship between zero-error and bounded-error quantum query complexity.Finally, we characterize the total Boolean functions that exhibit exponential quantum speedups when their domain is restricted to an arbitrarily chosen set.We show that such a "sculpting" of a quantum speedup is possible if and only if the original total function has many inputs with large certificate complexity.Along the way, we also show that functions defined on very small domains or that are very unbalanced can display at most a quadratic quantum speedup.
We give and prove an optimal exact quantum query algorithm with complexity k+1k+1k+1 for computing the promise problem (i.e., symmetric and partial Boolean function) DJnkDJ_n^kDJnk​ defined as: DJnk(x)=1DJ_n^k(x)=1DJnk​(x)=1 for ∣x∣=n/2|x|=n/2∣x∣=n/2, DJnk(x)=0DJ_n^k(x)=0DJnk​(x)=0 for ∣x∣|x|∣x∣ in the set {0,1,…,k,n−k,n−k+1,…,n}\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}{0,1,…,k,n−k,n−k+1,…,n}, and it is undefined for the rest cases, where nnn is even, ∣x∣|x|∣x∣ is the Hamming weight of xxx. The case of k=0k=0k=0 is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function fff has exact quantum 1-query complexity if and only if fff can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight {⌊n/2⌋,⌈n/2⌉}\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}{⌊n/2⌋,⌈n/2⌉} and Hamming weight in the set {0,n}\{ 0, n\}{0,n} for all odd nnn. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.