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

Quantum Information Processing

A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function

Wanqing Wu, Huanguo Zhang

Published Jan 16, 2019• 2 citations
Publisher
DOI
10.1007/s11128-019-2175-z

Related papers

Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms

Raitis Ozols, Rūsiņš Freivalds, Jevgeņijs Ivanovs +5 more

Lecture notes in computer science•Jan 1, 2005•3 citations

How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

Andris Ambainis, Ronald de Wolf

arXiv:1206.0717•Computational Complexity•May 8, 2014•11 citations

Polynomial Representation of General Partial Boolean Functions with a Single Quantum Query

Guoliang Xu, Daowen Qiu

Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Recently, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Under a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm.

arXiv:2112.12416•International Journal of Foundations of Computer Science•Jan 30, 2026•1 citation

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

Zekun Ye, Lv-Zhou Li

Journal of Computer Science and Technology•Nov 30, 2023•1 citation

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

Algorithms for Boolean Function Query Properties

Scott Aaronson

We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2 n ) as input. Our main results are the following: O(N log 2 3 log N) algorithms for many common properties, an O(N log 2 5 log N) algorithm for block sensitivity, an O(N) algorithm for testing "quasi symmetry," a notion of a "tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log 2 3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.

arXiv:cs/0107010•SIAM Journal on Computing•Jan 1, 2003•20 citations
Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Recently, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Under a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm.
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.
We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2 n ) as input. Our main results are the following: O(N log 2 3 log N) algorithms for many common properties, an O(N log 2 5 log N) algorithm for block sensitivity, an O(N) algorithm for testing "quasi symmetry," a notion of a "tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log 2 3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.