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

Quantum Computation and BQP

Richard J. Lipton, Kenneth W. Regan

Published Jan 1, 2014• 0 citations
OpenAlex

Abstract

This chapter contains sections titled: 16.1 The Class BQP, 16.2 Equations, Solutions, and Complexity, 16.3 A Circuit Labeling Algorithm, 16.4 Sum-Over-Paths and Polynomial Roots, 16.5 The Additive Polynomial Simulation, 16.6 Bounding BQP, 16.7 Problems, 16.8 Summary and Notes

Related papers

Phil's Algorithm

Richard J. Lipton, Kenneth W. Regan

This chapter contains sections titled: 7.1 The Algorithm, 7.2 The Analysis, 7.3 An Example, 7.4 A Two-Qubit Example, 7.5 Phil Measures Up, 7.6 Quantum Mazes versus Circuits versus Matrices, 7.7 Problems, 7.8 Summary and Notes

•Jan 1, 2014•0 citations

BQP is not in NP

J.T. Librande

Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.

arXiv:2209.10398•Sep 19, 2022•0 citations

Quantum computing and polynomial equations over Z_2

Christopher M. Dawson, Henry L. Haselgrove, Andrew P. Hines +3 more

What is the computational power of a quantum computer? We show that determining the output of a quantum computation is equivalent to counting the number of solutions to an easily computed set of polynomials defined over the finite field Z_2. This connection allows simple proofs to be given for two known relationships between quantum and classical complexity classes, namely BQP/P/\#P and BQP/PP.

arXiv:quant-ph/0408129•Quantum Information and Computation•May 1, 2005•81 citations

One‐way Quantum Computation

Dan E. Browne, Hans J. Briegel

This chapter contains sections titled: Introduction Simple examples Beyond quantum circuit simulation Implementations Recent developments Outlook

Wiley eBooks•Nov 6, 2006•23 citations

Boolean Functions, Quantum Bits, and Feasibility

Richard J. Lipton, Kenneth W. Regan

This chapter contains sections titled: 4.1 Feasible Boolean Functions, 4.2 An Example, 4.3 Quantum Representation of Boolean Arguments, 4.4 Quantum Feasibility, 4.5 Problems, 4.6 Summary and Notes

•Jan 1, 2014•0 citations

Computational Model for the One‐Way Quantum Computer: Concepts and Summary

Robert Raussendorf, Hans J. Briegel

This chapter contains sections titled: Introduction The QC C as a Universal Simulator of Quantum Logic Networks Non-Network Character of the QC C Computational Model Conclusion References

Quantum Information Processing•Feb 17, 2005•6 citations
Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.