This paper proves that every language in NP is recognized by an RP[ \\Phi P] machine whose time complexity is quasilinear, apart from the time to verify witnesses. The results significantly improve the number of random bits, success probability, and running time of Valiant and Vazirani's original construction [VV86], and beat both the 2n random bits and time/success tradeoff in subsequent methods based on universal hashing. Questions of further improvements are connected to open problems in the theory of error-correcting codes. 1. Introduction Valiant and Vazirani [VV86] proved that every language L 2 NP is accepted by a polynomial-time bounded probabilistic oracle Turing machine M o which, on any input x, computes a Boolean formula OE x as an oracle query, and accepts if the answer is `1'. The oracle of M o has the "promise property" that whenever OE x has a unique satisfying assignment, it always answers `1', and whenever OE x has no satisfying assignments, it answers `0'. An ...
This paper proves that every language in NP is recognized by an RP[ \Phi P] machine whose time complexity is quasilinear, apart from the time to verify witnesses. The results significantly improve the number of random bits, success probability, and running time of Valiant and Vazirani's original construction [VV86], and beat both the 2n random bits and time/success tradeoff in subsequent methods based on universal hashing. Questions of further improvements are connected to open problems in the theory of error-correcting codes. 1. Introduction Valiant and Vazirani [VV86] proved that every language L 2 NP is accepted by a polynomial-time bounded probabilistic oracle Turing machine M o which, on any input x, computes a Boolean formula OE x as an oracle query, and accepts if the answer is 1'. The oracle of M o has the "promise property" that whenever OE x has a unique satisfying assignment, it always answers 1', and whenever OE x has no satisfying assignments, it answers `0'. An ...
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn) NP queries, then BPPNP[o(n)] contains a PNP-complete problem if the algorithm is classical and FBQPNP[o(n)] contains an FPNP-complete problem if the algorithm is quantum.
There is growing interest in extensions of the standard model of gate-based quantum computation to include auxiliary degrees of freedom evolving according to a nonlinear Schrödinger equation. By reducing the
Boolean satisfiability problem SAT to quantum state discrimination, Abrams and Lloyd argued that the right type of nonlinearity can be used to solve NP and #P problems in polynomial time, at least in an
idealized noise-free limit. For practical implementation, however, we are restricted to simulated and emergent nonlinearities, such as that appearing in mean field models for ultracold atoms and similar
ensembles. A prominent example is the torsion model, which arises in two-component Bose-Einstein condensates and spin models with all-to-all Ising interaction. But torsion-based state discrimination appears to
fall short of solving SAT. Here we close this gap by constructing the filtered oracle of the Valiant-Vazirani theorem, providing a randomized polynomial-time reduction from SAT to UNIQUE SAT, a promise problem
where there is at most 1 satisfying assignment. In the noise-free limit, the UNIQUE SAT problem can be solved in polynomial time using torsion nonlinearity. Quantum Valiant-Vazirani reduction is no faster than
the efficient classical version, but a fault-tolerant implementation coupled to a nonlinear quantum coprocessor simulating torsion would enable polynomial time solution to NP (but not #P) problems.
We show that for deterministic polynomial time computations, oracle access to
APP, the class of real functions
approximable by probabilistic Turing machines, is the same as having oracle access to
promise-BPP. First,
we construct a mapping that maps every function in APP to a promise problem
in prBPP, and that preserves completeness, i.e. maps complete functions to complete promise problems.
Next, we construct
a mapping from
prBPP into APP, that maps every promise problem to a function
in APP, and which preserves completeness.
Then, we prove that PAPP=PprBPP.
Finally, we use our results to simplify proofs of important results on APP, such as
the APP-completeness of the function fCAPP,
which approximates the acceptance
probability of a Boolean circuit, the error probability reduction Theorem
for APP functions, and the conditional derandomization result
APP=AP iff prBPP is easy.
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle.
For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier.
The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size 2poly(n) changes its output with probability above 2−Ω(n) when the answer of a random instance is flipped by changing a single leaf.
We consider a class, denoted APP, of real-valued functions f : f0; 1g n ! [0; 1] such that f can be approximated, to within any ffl ? 0, by a probabilistic Turing machine running in time poly(n; 1=ffl). We argue that APP can be viewed as a generalization of BPP, and show that APP contains a natural complete problem: computing the acceptance probability of a given Boolean circuit; in contrast, no complete problems are known for BPP. We observe that all known complexity-theoretic assumptions under which BPP is easy (i.e., can be efficiently derandomized) imply that APP is easy; on the other hand, we show that BPP may be easy while APP is not, by constructing an appropriate oracle. 1 Introduction The complexity class BPP is traditionally considered a class of languages that can be efficiently decided with the help of randomness. While it does contain some natural problems, the "semantic" nature of its definition (on every input, a BPP machine must have either at least 3=4 or at...
In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time O(nk) for every k∈N1 and accepts a language Ld∈/P. We further show that Ld∈BPP, thereby separating BPP from P (i.e., P⫋BPP). Since the complexity class BQP of {\em bounded error quantum polynomial-time computation} contains BPP (i.e., BPP⊆BQP), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic computers (i.e., P⫋BQP). As an important consequence of the above results, we disprove the {\bf Extended Church-Turing Thesis}. Furthermore, we establish the following separations: (1) P⫋RP; (2) P⫋coRP; (3) P⫋ZPP. These relationships were long-standing open questions in complexity theory. In addition, the separation P⫋BPP demonstrates that {\em randomness} plays an essential role in probabilistic computation. In particular, we prove the following: (4) The number of random bits used by any probabilistic algorithm accepting Ld cannot be reduced to O(logn); (5) There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG): G:{0,1}O(logn)→{0,1}n; (6) There exists no quick HSG H:k(n)→n with k(n)=O(logn).