We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.
We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}/sup N/ in the black-box model. We show that, in the black-box model, the exponential quantum speed-up obtained for partial functions (i.e. problems involving a promise on the input) by Deutsch and Jozsa and by Simon cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with bounded-error using T black-box queries then there is a classical deterministic algorithm that computes f exactly with O(T/sup 6/) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors.
Assuming NP ⊈ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.
We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on {0,1} N in the black-box model. We show that the exponential quantum speed-up obtained for partial functions (i.e., problems involving a promise on the input) by Deutsch and Jozsa, Simon, and Shor cannot be obtained for any total function: if a quantum algorithm computes some total Boolean function f with small error probability using T black-box queries, then there is a classical deterministic algorithm that computes f exactly with O ( Ts 6 ) queries. We also give asymptotically tight characterizations of T for all symmetric f in the exact, zero-error, and bounded-error settings. Finally, we give new precise bounds for AND, OR, and PARITY. Our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by Nisan about a polynomial relationship between randomized and deterministic decision tree complexity.
Building on the work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated, nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer.
Building on work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer. The results given in this paper have been presented at the 7th Annual IEEE Symposium on Structure in Complexity Theory, Boston, June 1992, and at the Workshop on Physics and Computation, PhysComp '92, Dallas, October 1992; they have appeared in preliminary form in those Proceedings [7, 8]. y Supported in part by an Nserc postgraduate fellowship. z Supported in part by Canada's Nserc E. W. R. Steacie Memorial Fellowship an...