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:1912.03042

Constructive derandomization of query algorithms

Guy Blanc, Jane Lange, Li-Yang Tan

Published Dec 6, 2019• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1912.03042

Related papers

On Randomized and Quantum Query Complexities

Gatis Midrijānis

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.

arXiv:quant-ph/0501142•Jan 25, 2005•14 citations

Quantum Query Algorithm Constructions for Computing AND, OR and MAJORITY Boolean Functions

Alina Vasiljeva

Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box and the aim is to compute function value for arbitrary input using as few queries as possible. We concentrate on quantum query algorithm designing tasks in this paper. The main aim of the research was to find new efficient algorithms and develop general algorithm designing techniques. First, we present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next, we introduce algorithm transformation methods that allow significant enlarging of exactly computable functions sets. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design a more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries. Methods offer constructions for computing AND, OR and MAJORITY kinds of Boolean functions.

•Jan 1, 2008•1 citation

Quantum Query Algorithm Constructions for Computing AND, OR and MAJORITY Boolean Functions

Alina Vasilieva

Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box and the aim is to compute function value for arbitrary input using as few queries as possible. We concentrate on quantum query algorithm designing tasks in this paper. The main aim of the research was to find new efficient algorithms and develop general algorithm designing techniques. First, we present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next, we introduce algorithm transformation methods that allow significant enlarging of exactly computable functions sets. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design a more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries. Methods offer constructions for computing AND, OR and MAJORITY kinds of Boolean functions.

arXiv:0710.5592•Oct 30, 2007•1 citation

Pseudo-deterministic Quantum Algorithms

Hugo Aaronson, Tom Gur, Jiawei Li

We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is $O(1)$ but is maximally hard for pseudo-deterministic quantum algorithms ($Ω(N)$ query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms ($O(\log(N))$ vs. $Θ(\sqrt{N})$), while the randomized query complexity is $O(1)$. Complementing these separations, we show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., $D(R) = \tilde O(psQ(R)^5)$. On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, $k$-sum, and graph collision.

quant-pharXiv:2602.17647•Leibniz international proceedings in informatics•Feb 20, 2026•2 citations

Quantum query algorithms for certain functions and general algorithm construction techniques

Alina Dubrovska

Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box, but the aim is to compute function value for arbitrary input using as few queries as possible. In this paper we concentrate on quantum query algorithm designing tasks. The main aim of research was to find new efficient algorithms and develop general algorithm designing techniques. We present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next we introduce algorithm transformation methods that allow significant enlarging of sets of exactly computable functions. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 27, 2007•3 citations

Properties and application of nondeterministic quantum query algorithms

Alina Dubrovska

Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.

arXiv:quant-ph/0606248•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 27, 2007•3 citations
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.
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.
Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box and the aim is to compute function value for arbitrary input using as few queries as possible. We concentrate on quantum query algorithm designing tasks in this paper. The main aim of the research was to find new efficient algorithms and develop general algorithm designing techniques. First, we present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next, we introduce algorithm transformation methods that allow significant enlarging of exactly computable functions sets. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design a more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries. Methods offer constructions for computing AND, OR and MAJORITY kinds of Boolean functions.
Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box and the aim is to compute function value for arbitrary input using as few queries as possible. We concentrate on quantum query algorithm designing tasks in this paper. The main aim of the research was to find new efficient algorithms and develop general algorithm designing techniques. First, we present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next, we introduce algorithm transformation methods that allow significant enlarging of exactly computable functions sets. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design a more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries. Methods offer constructions for computing AND, OR and MAJORITY kinds of Boolean functions.
We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is O(1)O(1)O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N)Ω(N)Ω(N) query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log⁡(N))O(\log(N))O(log(N)) vs. Θ(N)Θ(\sqrt{N})Θ(N​)), while the randomized query complexity is O(1)O(1)O(1). Complementing these separations, we show that for any total problem RRR, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., D(R)=O~(psQ(R)5)D(R) = \tilde O(psQ(R)^5)D(R)=O~(psQ(R)5). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, kkk-sum, and graph collision.
Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box, but the aim is to compute function value for arbitrary input using as few queries as possible. In this paper we concentrate on quantum query algorithm designing tasks. The main aim of research was to find new efficient algorithms and develop general algorithm designing techniques. We present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next we introduce algorithm transformation methods that allow significant enlarging of sets of exactly computable functions. Finally, we propose quantum algorithm designing methods. Given algorithms for the set of sub-functions, our methods use them to design more complex one, based on algorithms described before. Methods are applicable for input algorithms with specific properties and preserve acceptable error probability and number of queries.
Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.