Table of Contents
- Introduction
- Classical Advice and Non-uniform Computation
- Quantum Advice: Definition and Motivation
- The Class BQP/qpoly
- Comparison with BQP/poly
- Quantum Advice States vs Classical Advice Strings
- Measuring Power of Quantum Advice
- Limitations of Quantum Advice (No-Cloning, Measurement)
- Untrusted vs Trusted Advice Models
- Quantum Advice and One-Way Communication
- Relationship with Quantum Communication Complexity
- Oracle Separations Involving BQP/qpoly
- BQP/qpoly vs QMA and QCMA
- Advice in Multi-Prover Quantum Protocols
- Quantum Advice and Random Access Codes
- Cryptographic Implications
- Hardness vs Randomness with Advice
- Known Barriers and Open Problems
- Physical Interpretations of Quantum Advice
- Conclusion
1. Introduction
Quantum advice extends the concept of non-uniform computation into the quantum world. It involves providing a quantum state—rather than a classical string—as auxiliary input to a quantum machine, enabling potentially more powerful computation.
2. Classical Advice and Non-uniform Computation
In classical complexity, P/poly and BPP/poly represent polynomial-time classes augmented by polynomial-length classical advice strings. These strings encode useful auxiliary information about the input size but not specific input instances.
3. Quantum Advice: Definition and Motivation
Quantum advice refers to a quantum state of polynomial size that a quantum algorithm can use to decide a language. It is independent of the actual input but depends on the input length.
4. The Class BQP/qpoly
BQP/qpoly is the class of languages decidable in bounded-error quantum polynomial time with access to polynomial-size quantum advice. It generalizes BQP by allowing non-uniform, quantum auxiliary information.
5. Comparison with BQP/poly
BQP/qpoly ⊇ BQP/poly, but the separation is not known to be strict. Quantum advice may offer advantages via entanglement and superposition, though it’s harder to reuse or verify than classical advice.
6. Quantum Advice States vs Classical Advice Strings
Quantum advice can encode exponentially more information than classical strings, due to the Hilbert space dimension. However, the information is fragile and cannot be read arbitrarily without disturbance.
7. Measuring Power of Quantum Advice
Studies of BQP/qpoly often focus on:
- Languages decidable with minimal queries using advice
- Simulation of circuits with high circuit complexity
- Separations relative to oracles
8. Limitations of Quantum Advice (No-Cloning, Measurement)
Quantum advice cannot be cloned, reused arbitrarily, or error-checked without destructive measurement. These constraints limit how powerful and reliable advice can be in practice.
9. Untrusted vs Trusted Advice Models
In untrusted models, the verifier must verify the advice’s validity (like QMA). Trusted models assume perfect advice. Verifiability issues are central to protocols like QMA with advice or advice-based delegation.
10. Quantum Advice and One-Way Communication
Quantum advice is related to one-way quantum communication complexity, where Alice sends a quantum message to Bob. The study of how much information can be packed into quantum states informs limits on advice power.
11. Relationship with Quantum Communication Complexity
The class QMA/qpoly relates closely to results in communication complexity. These models help establish bounds on how much useful information can be transmitted through unmeasured quantum states.
12. Oracle Separations Involving BQP/qpoly
There exist oracle worlds where:
- BQP/qpoly ≠ BQP/poly
- BQP/qpoly ⊄ QMA
These separations illustrate the independence of quantum advice from proof-based complexity classes.
13. BQP/qpoly vs QMA and QCMA
QMA uses quantum witnesses per instance; BQP/qpoly uses global advice for input lengths. BQP/qpoly is non-interactive, while QMA involves interaction and verification. Their relative power remains an open area.
14. Advice in Multi-Prover Quantum Protocols
Quantum advice can be shared among entangled provers in MIP* settings. This leads to questions of how advice influences protocol soundness and provability, especially with nonlocal resources.
15. Quantum Advice and Random Access Codes
Quantum advice can be viewed as a compact random access code: encoding many bits into a small state from which individual bits can be approximately recovered. This frames limits on advice-based computation.
16. Cryptographic Implications
Quantum advice models impact cryptography through:
- Public-key distribution via advice
- Quantum indistinguishability assumptions
- Hardness of verifying or forging advice-dependent outputs
17. Hardness vs Randomness with Advice
Quantum advice challenges traditional derandomization paradigms. The presence of advice can eliminate randomness for certain problems, but not always efficiently or in a verifiable way.
18. Known Barriers and Open Problems
- Does BQP/qpoly contain all of EXP?
- Are there natural problems solvable in BQP/qpoly but not in BQP/poly?
- Can quantum advice be verified without destroying it?
19. Physical Interpretations of Quantum Advice
Quantum advice may represent pre-shared entanglement, precomputed states, or physical tokens in quantum protocols. These interpretations influence how advice is stored, prepared, and used securely.
20. Conclusion
Quantum advice introduces rich complexity-theoretic and physical questions. While it theoretically enhances computational power, practical limitations on verification and reuse present deep challenges and fertile ground for future exploration.
