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:quant-ph/0501142

On Randomized and Quantum Query Complexities

Gatis Midrijānis

Published Jan 25, 2005• 14 citations
arXivHTMLPDF

Abstract

We study randomized and quantum query (a.k.a. decision tree) complexity for all total Boolean functions, with emphasis to derandomization and dequantization (removing quantumness from algorithms). Firstly, we show that $D(f) = O(Q_1(f)^3)$ for any total function $f$, where $D(f)$ is the minimal number of queries made by a deterministic query algorithm and $Q_1(f)$ is the number of queries made by any quantum query algorithm (decision tree analog in quantum case) with one-sided constant error; both algorithms compute function $f$. Secondly, we show that for all total Boolean functions $f$ holds $R_0(f)=O(R_2(f)^2 \log N)$, where $R_0(f)$ and $R_2(f)$ are randomized zero-sided (a.k.a Las Vegas) and two-sided (a.k.a. Monte Carlo) error query complexities.

DOI
10.48550/arxiv.quant-ph/0501142

Related papers

Separations in query complexity based on pointer functions

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3 more

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function f on n=2k bits defined by a complete binary tree of NAND gates of depth k, which achieves R0(f) = O(D(f)0.7537…). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Ω(n/log(n)) while its zero-error randomized query complexity is Õ(√n). We further show that the quantum query complexity of the same function is Õ(n1/4), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.

ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•39 citations

Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity

Andris Ambainis, Jānis Iraids, Martins Kokainis

We study how large the certificate complexity ${C}(f)$ of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function $f$ whose randomized query complexity with one-sided error satisfies ${R}_1(f) = Θ(\sqrt{{C}(f)})$. This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function $F$ with bounded-error quantum query complexity ${Q}(F) = \widetilde O({C}(F)^{1/4})$, attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are $\widetilde O(\sqrt{{C}(F)})$. We also prove matching lower bounds for these two measures on $F$.

quant-pharXiv:2609.11664•Sep 11, 2026•1 citation

Towards Better Separation between Deterministic and Randomized Query Complexity

Sagnik Mukhopadhyay, Swagato Sanyal

We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R_0(F)) and randomized one-sided error query complexity (R_1(F)): R_1(F) = ~O(sqrt{D(F)) and R_0(F)=~O(D(F))^3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R_0(f)=Omega(D(f))^0.753.. . This also shows widest separation between R_1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R_0(f), and polynomial separation between R_0(f) and R_1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.

arXiv:1506.06399•Leibniz international proceedings in informatics•Jan 1, 2015•10 citations

Constructive derandomization of query algorithms

Guy Blanc, Jane Lange, Li-Yang Tan

We give efficient deterministic algorithms for converting randomized query algorithms into deterministic ones. We first give an algorithm that takes as input a randomized $q$-query algorithm $R$ with description length $N$ and a parameter $\varepsilon$, runs in time $\mathrm{poly}(N) \cdot 2^{O(q/\varepsilon)}$, and returns a deterministic $O(q/\varepsilon)$-query algorithm $D$ that $\varepsilon$-approximates the acceptance probabilities of $R$. These parameters are near-optimal: runtime $N + 2^{Ω(q/\varepsilon)}$ and query complexity $Ω(q/\varepsilon)$ are necessary. Next, we give algorithms for instance-optimal and online versions of the problem: $\circ$ Instance optimal: Construct a deterministic $q^\star_R$-query algorithm $D$, where $q^\star_R$ is minimum query complexity of any deterministic algorithm that $\varepsilon$-approximates $R$. $\circ$ Online: Deterministically approximate the acceptance probability of $R$ for a specific input $\underline{x}$ in time $\mathrm{poly}(N,q,1/\varepsilon)$, without constructing $D$ in its entirety. Applying the techniques we develop for these extensions, we constructivize classic results that relate the deterministic, randomized, and quantum query complexities of boolean functions (Nisan, STOC 1989; Beals et al., FOCS 1998). This has direct implications for the Turing machine model of computation: sublinear-time algorithms for total decision problems can be efficiently derandomized and dequantized with a subexponential-time preprocessing step.

arXiv:1912.03042•Dec 6, 2019•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

Separation Between Deterministic and Randomized Query Complexity

Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal

Saks and Wigderson [in Proceedings of the $27$th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that $R_0(f) = \Omega(D(f)^{0.753\ldots})$ for all Boolean functions $f$, where $R_0$ denotes the randomized zero-error query complexity and $D$ denotes the deterministic query complexity. We show that for the pointer function $\mathsf{GPW}^{r \times s}$ defined by Göös, Pitassi, and Watson [in Proceedings of the $56$th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a) $R_1(\mathsf{GPW}^{r \times s}) = \widetilde{\Theta}({r+s})$ and (b) $R_1(\overline{\mathsf{GPW}^{r \times s}}) = \widetilde{\Theta}(r+\sqrt{r}s)$, where $R_1$ denotes the randomized one-sided error query complexity. These results imply that (i) $R_0(\mathsf{GPW}^{s^2 \times s}) = O(D(\mathsf{GPW}^{s^2 \times s})^{2/3})$, thereby refuting the conjecture of Saks and Wigderson, and (ii) $R_1(\mathsf{GPW}^{s \times s})=\widetilde{O}(R_0(\mathsf{GPW}^{s \times s})^{2/3})$, thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.

SIAM Journal on Computing•Jan 1, 2018•6 citations
We study randomized and quantum query (a.k.a. decision tree) complexity for all total Boolean functions, with emphasis to derandomization and dequantization (removing quantumness from algorithms). Firstly, we show that D(f)=O(Q1(f)3)D(f) = O(Q_1(f)^3)D(f)=O(Q1​(f)3) for any total function fff, where D(f)D(f)D(f) is the minimal number of queries made by a deterministic query algorithm and Q1(f)Q_1(f)Q1​(f) is the number of queries made by any quantum query algorithm (decision tree analog in quantum case) with one-sided constant error; both algorithms compute function fff. Secondly, we show that for all total Boolean functions fff holds R0(f)=O(R2(f)2log⁡N)R_0(f)=O(R_2(f)^2 \log N)R0​(f)=O(R2​(f)2logN), where R0(f)R_0(f)R0​(f) and R2(f)R_2(f)R2​(f) are randomized zero-sided (a.k.a Las Vegas) and two-sided (a.k.a. Monte Carlo) error query complexities.
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function f on n=2k bits defined by a complete binary tree of NAND gates of depth k, which achieves R0(f) = O(D(f)0.7537…). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Ω(n/log(n)) while its zero-error randomized query complexity is Õ(√n). We further show that the quantum query complexity of the same function is Õ(n1/4), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.
We study how large the certificate complexity C(f){C}(f)C(f) of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function fff whose randomized query complexity with one-sided error satisfies R1(f)=Θ(C(f)){R}_1(f) = Θ(\sqrt{{C}(f)})R1​(f)=Θ(C(f)​). This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function FFF with bounded-error quantum query complexity Q(F)=O~(C(F)1/4){Q}(F) = \widetilde O({C}(F)^{1/4})Q(F)=O(C(F)1/4), attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are O~(C(F))\widetilde O(\sqrt{{C}(F)})O(C(F)​). We also prove matching lower bounds for these two measures on FFF.
We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R_0(F)) and randomized one-sided error query complexity (R_1(F)): R_1(F) = ~O(sqrt{D(F)) and R_0(F)=~O(D(F))^3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R_0(f)=Omega(D(f))^0.753.. . This also shows widest separation between R_1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R_0(f), and polynomial separation between R_0(f) and R_1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.
We give efficient deterministic algorithms for converting randomized query algorithms into deterministic ones. We first give an algorithm that takes as input a randomized qqq-query algorithm RRR with description length NNN and a parameter ε\varepsilonε, runs in time poly(N)⋅2O(q/ε)\mathrm{poly}(N) \cdot 2^{O(q/\varepsilon)}poly(N)⋅2O(q/ε), and returns a deterministic O(q/ε)O(q/\varepsilon)O(q/ε)-query algorithm DDD that ε\varepsilonε-approximates the acceptance probabilities of RRR. These parameters are near-optimal: runtime N+2Ω(q/ε)N + 2^{Ω(q/\varepsilon)}N+2Ω(q/ε) and query complexity Ω(q/ε)Ω(q/\varepsilon)Ω(q/ε) are necessary. Next, we give algorithms for instance-optimal and online versions of the problem: ∘\circ∘ Instance optimal: Construct a deterministic qR⋆q^\star_RqR⋆​-query algorithm DDD, where qR⋆q^\star_RqR⋆​ is minimum query complexity of any deterministic algorithm that ε\varepsilonε-approximates RRR. ∘\circ∘ Online: Deterministically approximate the acceptance probability of RRR for a specific input x‾\underline{x}x​ in time poly(N,q,1/ε)\mathrm{poly}(N,q,1/\varepsilon)poly(N,q,1/ε), without constructing DDD in its entirety. Applying the techniques we develop for these extensions, we constructivize classic results that relate the deterministic, randomized, and quantum query complexities of boolean functions (Nisan, STOC 1989; Beals et al., FOCS 1998). This has direct implications for the Turing machine model of computation: sublinear-time algorithms for total decision problems can be efficiently derandomized and dequantized with a subexponential-time preprocessing step.
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
Saks and Wigderson [in Proceedings of the 272727th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that R0(f)=Ω(D(f)0.753…)R_0(f) = \Omega(D(f)^{0.753\ldots})R0​(f)=Ω(D(f)0.753…) for all Boolean functions fff, where R0R_0R0​ denotes the randomized zero-error query complexity and DDD denotes the deterministic query complexity. We show that for the pointer function GPWr×s\mathsf{GPW}^{r \times s}GPWr×s defined by Göös, Pitassi, and Watson [in Proceedings of the 565656th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a) R1(GPWr×s)=Θ~(r+s)R_1(\mathsf{GPW}^{r \times s}) = \widetilde{\Theta}({r+s})R1​(GPWr×s)=Θ(r+s) and (b) R1(GPWr×s‾)=Θ~(r+rs)R_1(\overline{\mathsf{GPW}^{r \times s}}) = \widetilde{\Theta}(r+\sqrt{r}s)R1​(GPWr×s)=Θ(r+r​s), where R1R_1R1​ denotes the randomized one-sided error query complexity. These results imply that (i) R0(GPWs2×s)=O(D(GPWs2×s)2/3)R_0(\mathsf{GPW}^{s^2 \times s}) = O(D(\mathsf{GPW}^{s^2 \times s})^{2/3})R0​(GPWs2×s)=O(D(GPWs2×s)2/3), thereby refuting the conjecture of Saks and Wigderson, and (ii) R1(GPWs×s)=O~(R0(GPWs×s)2/3)R_1(\mathsf{GPW}^{s \times s})=\widetilde{O}(R_0(\mathsf{GPW}^{s \times s})^{2/3})R1​(GPWs×s)=O(R0​(GPWs×s)2/3), thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.