Polynomial time quantum computation with advice
- 31 May 2004
- journal article
- research article
- Published by Elsevier BV in Information Processing Letters
- Vol. 90 (4), 195-204
- https://doi.org/10.1016/j.ipl.2004.02.005
Abstract
Advice is supplementary information that enhances the computational power of an underlying computation. This paper focuses on advice that is given in the form of a pure quantum state and examines the influence of such advice on the behaviors of an underlying polynomial-time quantum computation with bounded-error probability.Keywords
Other Versions
This publication has 16 references indexed in Scilit:
- Dense quantum coding and quantum finite automataJournal of the ACM, 2002
- Quantum FingerprintingPhysical Review Letters, 2001
- The structure of logarithmic advice complexity classesTheoretical Computer Science, 1998
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- Quantum ComputabilitySIAM Journal on Computing, 1997
- Elementary gates for quantum computationPhysical Review A, 1995
- Quantum computational networksProceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 1989
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 1985
- Circuit-size lower bounds and non-reducibility to sparse setsInformation and Control, 1982
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977