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

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•Feb 20, 2026•1 citation

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

Testing and reconstruction via decision trees.

Guy Blanc, Jane Lange, Li-Yang Tan

We study sublinear and local computation algorithms for decision trees, focusing on testing and reconstruction. Our first result is a tester that runs in $\mathrm{poly}(\log s, 1/\varepsilon)\cdot n\log n$ time, makes $\mathrm{poly}(\log s,1/\varepsilon)\cdot \log n$ queries to an unknown function $f$, and: $\circ$ Accepts if $f$ is $\varepsilon$-close to a size-$s$ decision tree; $\circ$ Rejects if $f$ is $\Omega(\varepsilon)$-far from decision trees of size $s^{\tilde{O}((\log s)^2/\varepsilon^2)}$. Existing testers distinguish size-$s$ decision trees from those that are $\varepsilon$-far from from size-$s$ decision trees in $\mathrm{poly}(s^s,1/\varepsilon)\cdot n$ time with $\tilde{O}(s/\varepsilon)$ queries. We therefore solve an incomparable problem, but achieve doubly-exponential-in-$s$ and exponential-in-$s$ improvements in time and query complexities respectively. We obtain our tester by designing a reconstruction algorithm for decision trees: given query access to a function $f$ that is close to a small decision tree, this algorithm provides fast query access to a small decision tree that is close to $f$. By known relationships, our results yield reconstruction algorithms for numerous other boolean function properties -- Fourier degree, randomized and quantum query complexities, certificate complexity, sensitivity, etc. -- which in turn yield new testers for these properties. Finally, we give a hardness result for testing whether an unknown function is $\varepsilon$-close-to or $\Omega(\varepsilon)$-far-from size-$s$ decision trees. We show that an efficient algorithm for this task would yield an efficient algorithm for properly learning decision trees, a central open problem of learning theory. It has long been known that proper learning algorithms for any class $\mathcal{H}$ yield property testers for $\mathcal{H}$; this provides an example of a converse.

•Dec 16, 2020•2 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.
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.
We study sublinear and local computation algorithms for decision trees, focusing on testing and reconstruction. Our first result is a tester that runs in poly(log⁡s,1/ε)⋅nlog⁡n\mathrm{poly}(\log s, 1/\varepsilon)\cdot n\log npoly(logs,1/ε)⋅nlogn time, makes poly(log⁡s,1/ε)⋅log⁡n\mathrm{poly}(\log s,1/\varepsilon)\cdot \log npoly(logs,1/ε)⋅logn queries to an unknown function fff, and: ∘\circ∘ Accepts if fff is ε\varepsilonε-close to a size-sss decision tree; ∘\circ∘ Rejects if fff is Ω(ε)\Omega(\varepsilon)Ω(ε)-far from decision trees of size sO~((log⁡s)2/ε2)s^{\tilde{O}((\log s)^2/\varepsilon^2)}sO~((logs)2/ε2). Existing testers distinguish size-sss decision trees from those that are ε\varepsilonε-far from from size-sss decision trees in poly(ss,1/ε)⋅n\mathrm{poly}(s^s,1/\varepsilon)\cdot npoly(ss,1/ε)⋅n time with O~(s/ε)\tilde{O}(s/\varepsilon)O~(s/ε) queries. We therefore solve an incomparable problem, but achieve doubly-exponential-in-sss and exponential-in-sss improvements in time and query complexities respectively. We obtain our tester by designing a reconstruction algorithm for decision trees: given query access to a function fff that is close to a small decision tree, this algorithm provides fast query access to a small decision tree that is close to fff. By known relationships, our results yield reconstruction algorithms for numerous other boolean function properties -- Fourier degree, randomized and quantum query complexities, certificate complexity, sensitivity, etc. -- which in turn yield new testers for these properties. Finally, we give a hardness result for testing whether an unknown function is ε\varepsilonε-close-to or Ω(ε)\Omega(\varepsilon)Ω(ε)-far-from size-sss decision trees. We show that an efficient algorithm for this task would yield an efficient algorithm for properly learning decision trees, a central open problem of learning theory. It has long been known that proper learning algorithms for any class H\mathcal{H}H yield property testers for H\mathcal{H}H; this provides an example of a converse.