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

Computing Relations in the Quantum Query Model 1

Alina Vasilieva, Taisia Mischenko-Slatenkova

Published Jan 1, 2011• 0 citations
OpenAlex

Related papers

The power of various real-valued quantum queries

Arvid J. Bessen

arXiv:quant-ph/0308140•Journal of Complexity•Oct 15, 2003•7 citations

Quantum versus classical query complexity of relation

Alina Vasilieva

This paper investigates the computability of mathematical relations in a quantum query model. The important task in complexity theory is to find examples with a large gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design that allow achieving a large separation between classical and quantum query complexity of a specific relation. We demonstrate an example where quantum query algorithm for a finite relation needs more than two times fewer queries than the best possible classical analogue. We also show that relation can be extended to infinite family of relations with an input of general size N.

International Conference on Natural Computation (ICNC)•Jul 1, 2011•3 citations

Parameterized query complexity in quantum computation

Parijat Prashun Purohit

•Jan 1, 2017•0 citations

Models of Query Complexity for Boolean Functions

Sourav Chakraborty

In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially

•Aug 6, 2010•0 citations

Complexity Beyond Classical Limits: A Study of Quantum Query and Communication Models

Daiki Suruga

•Mar 25, 2025•0 citations

Characterization of exact one-query quantum algorithms

Weijiang Chen, Zekun Ye, Lvzhou Li

The quantum query model is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm, and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function $f:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ can be exactly computed by a one-query quantum algorithm if and only if $f(x)={x}_{{i}_{1}}$ or ${x}_{{i}_{1}}\ensuremath{\bigoplus}{x}_{{i}_{2}}$ (up to isomorphism). Note that, unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of $f$.

arXiv:1912.03493•Physical Review A•Feb 20, 2020•15 citations
This paper investigates the computability of mathematical relations in a quantum query model. The important task in complexity theory is to find examples with a large gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design that allow achieving a large separation between classical and quantum query complexity of a specific relation. We demonstrate an example where quantum query algorithm for a finite relation needs more than two times fewer queries than the best possible classical analogue. We also show that relation can be extended to infinite family of relations with an input of general size N.
In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially
The quantum query model is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm, and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function $f:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ can be exactly computed by a one-query quantum algorithm if and only if f(x)=xi1f(x)={x}_{{i}_{1}}f(x)=xi1​​ or ${x}_{{i}_{1}}\ensuremath{\bigoplus}{x}_{{i}_{2}}$ (up to isomorphism). Note that, unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of fff.