zbMATH — the first resource for mathematics

Quantum computing and quadratically signed weight enumerators. (English) Zbl 1032.68080
Summary: We prove that quantum computing is polynomially equivalent to classical probabilistic computing with an oracle for estimating the value of simple sums, quadratically signed weight enumerators (QWGTs). The problem of estimating these sums is cast in terms of promise problems and has two interesting variants. An oracle for the unconstrained variant may be more powerful than quantum computing, while an oracle for a more constrained variant is efficiently solvable in the one-bit model of quantum computing. Thus, problems involving QWGTs yield new problems in BQPP (BQP promise problems) and a natural BQPP complete problem. They can be used to define and study complexity classes and their relationships to quantum computing.

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI
[1] Shor, P.W., Algorithms for quantum computation: discrete logarithms and factoring, (), 124-134
[2] Shor, P.W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. comput., 26, 1484-1509, (1997) · Zbl 1005.11065
[3] Shor, P.W., Fault-tolerant quantum computation, (), 56-65
[4] Kitaev, A.Y., Quantum computations: algorithms and error correction, Uspekhi mat. nauk, 52, 53-112, (1997)
[5] Knill, E.; Laflamme, R.; Zurek, W.H., Resilient quantum computation, Science, 279, 342-345, (1998)
[6] Aharonov, D.; Ben-Or, M., Fault-tolerant quantum computation with constant error, (), 176-188 · Zbl 0962.68065
[7] Aharonov, D.; Ben-Or, M., Fault-tolerant quantum computation with constant error, 1999 · Zbl 0962.68065
[8] Bernstein, E.; Vazirani, U., Quantum complexity theory, SIAM J. comput., 26, 1411-1473, (1997) · Zbl 0895.68042
[9] Knill, E.; Laflamme, R., On the power of one bit of quantum information, Phys. rev. lett., 81, 5672-5675, (1998)
[10] Aharonov, D., Quantum computation, () · Zbl 0962.68065
[11] Cleve, R., An introduction to quantum complexity theory, 1999
[12] Selman, A.L., Promise problems complete for complexity classes, Inform. and comput., 78, 87-97, (1988) · Zbl 0655.68050
[13] Cay, J.; Hemachandra, L.; Vyskoč, J., Promises and fault-tolerant database access, (), 101-146 · Zbl 0794.68059
[14] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033
[15] Vertigan, D.L., Bycycle dimension and special points of the Tutte polynomial, J. combin. theory A, 220, 53-162, (1992)
[16] Adleman, L.M.; DeMarrais, U.; Huang, M.-D.A., Quantum computability, SIAM J. comput., 26, 1524-1540, (1997) · Zbl 0895.68043
[17] R. Solovay, A. Yao, Manuscript, 1996
[18] Bennett, C.H., Time/space trade-offs for reversible computation, SIAM J. comput., 18, 766-776, (1989) · Zbl 0676.68010
[19] R.M. Solovay, Private communication, 1998
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.