Table of Contents
- Introduction to Quantum Advice
- Classical vs Quantum Advice
- Formal Definition of BQP/qpoly
- Role of Advice Strings in Computation
- BQP/qpoly vs BQP/poly
- The Power of Nonuniform Quantum Computation
- Encoding Quantum Advice: States, Qubits, and Fidelity
- Examples of Problems in BQP/qpoly
- Simulation and Compression of Quantum Advice
- Limitations of Quantum Advice
- Aaronson’s Theorem: BQP/qpoly ⊆ PP/poly
- Proof Sketch of BQP/qpoly ⊆ PP/poly
1. Introduction to Quantum Advice
In classical complexity theory, nonuniform computation refers to machines that are allowed different “advice strings” depending on the input length. These strings are not derived from the input, but assumed to be provided externally. In quantum complexity theory, quantum advice means a family of quantum states provided to the quantum computer as nonuniform resources.
2. Classical vs Quantum Advice
Classical advice is a string \( a_n \in \{0,1\}^{p(n)} \) for some polynomial \( p(n) \), and the machine can access this advice depending on input length \( n \).
Quantum advice is a family of quantum states \( \{ |\psi_n
angle \} \), where \( |\psi_n
angle \) is a quantum state on poly(n) qubits. These states are provided nonuniformly—fixed for each input length.
3. Formal Definition of BQP/qpoly
A language \( L \in ext{BQP/qpoly} \) if there exists a polynomial-time quantum algorithm \( Q \) and a family of quantum states \( \{ |\psi_n
angle \} \) such that for all inputs \( x \in \{0,1\}^n \):
\[
\Pr[Q(x, |\psi_n
angle) = L(x)] \geq 2/3
\]
The key difference is that the advice is quantum, not classical.
4. Role of Advice Strings in Computation
Advice strings model hardwired knowledge or hints that help the algorithm solve otherwise intractable problems. They serve as a bridge to study nonuniformity and its computational impact.
5. BQP/qpoly vs BQP/poly
The class BQP/poly refers to quantum polynomial-time algorithms with classical advice. Clearly:
\[
ext{BQP} \subseteq ext{BQP/poly} \subseteq ext{BQP/qpoly}
\]
This raises the question: Is quantum advice strictly more powerful than classical advice? The answer is nuanced and context-dependent.
6. The Power of Nonuniform Quantum Computation
Quantum advice can encode exponentially more information than classical advice in principle. However, practical limits such as state preparation, fidelity, and no-cloning restrict its usability.
7. Encoding Quantum Advice: States, Qubits, and Fidelity
A poly-size quantum advice state \( |\psi_n
angle \) can encode an exponential number of amplitudes. But real-world constraints make perfect encoding and transmission impossible. Noise, decoherence, and error-correction limit how advice states can be constructed and used.
8. Examples of Problems in BQP/qpoly
Some oracle separations suggest languages exist that are in BQP/qpoly but not in BQP/poly. Examples include:
- “Forrelation” problems (Aaronson)
- Certain relational problems in query complexity
However, natural problems in BQP/qpoly remain rare.
9. Simulation and Compression of Quantum Advice
Aaronson showed that any quantum advice can be replaced by classical advice for simulating the decision behavior using PP/poly. This leads to:
10. Limitations of Quantum Advice
Despite their expressive capacity, quantum advice states cannot do everything. The limitation results from the fact that quantum measurements are inherently probabilistic, and quantum states cannot be copied.
11. Aaronson’s Theorem: BQP/qpoly ⊆ PP/poly
A groundbreaking result by Scott Aaronson shows:
\[
ext{BQP/qpoly} \subseteq ext{PP/poly}
\]
This means that quantum advice doesn’t escape the realm of classical probabilistic polynomial-time algorithms with advice.
12. Proof Sketch of BQP/qpoly ⊆ PP/poly
The proof simulates a quantum computation with quantum advice using postselection. Using the class PostBQP = PP, Aaronson compresses the advice into a classical circuit and simulates the behavior using PP with classical advice.
13. Relationship with Relativized Worlds
Oracle separations suggest that BQP/qpoly may be strictly more powerful than BQP/poly, but no unrelativized separation is known. Thus, any separation is relative to oracle constructions.
14. Comparisons with Other Nonuniform Classes
Quantum advice adds richness to the nonuniform world:
- BPP/poly: Probabilistic poly-time with classical advice
- QMA/poly: QMA with classical advice
- QMA/qpoly: QMA with quantum advice
15. Uniqueness of Quantum Advice
A key subtlety is that advice must be independent of the input—only dependent on input length. This restricts using the advice for encoding input-specific shortcuts.
16. Quantum Finite Automata with Advice
In automata theory, adding quantum advice to quantum finite automata gives a theoretical boost in power but introduces verification and preparation complexity.
17. Advice Complexity and Kolmogorov Complexity
Advice strings relate to algorithmic information theory. Quantum advice can be seen as a low-Kolmogorov complexity quantum state that helps the machine efficiently decide a language.
18. Distinguishability and Trace Distance
Two quantum states can be distinguished with advantage proportional to their trace distance. This plays a role in how robust quantum advice must be to ensure correctness across all inputs.
19. Quantum vs Probabilistic Advice
Quantum advice is fundamentally different from randomized advice (used in BPP/rpoly). Quantum amplitudes enable interference patterns not achievable by mere sampling.
20. Implicit vs Explicit Advice
Quantum advice may implicitly encode properties hard to represent classically. However, without a method to verify correctness, such advice becomes practically meaningless.
21. Tradeoffs: Size of Advice vs Computational Time
Larger advice can reduce computation time, but encoding large amounts into quantum states is challenging. There’s a fundamental tension between advice length and algorithm efficiency.
22. Open Problems and Research Directions
- Is BQP/qpoly ⊂ EXP/poly?
- Can BQP/qpoly solve cryptographically hard problems?
- Are there natural complete problems for BQP/qpoly?
- How to verify untrusted quantum advice?
23. Implications for Cryptography and Oracle Constructions
Quantum advice could, in principle, break cryptographic assumptions if the advice encodes a trapdoor. Oracle results suggest stronger-than-classical separation, but do not impact unrelativized cryptography.
24. Quantum Advice in Physical Realizability
Theoretical models assume perfect quantum advice, but in physical systems, decoherence and measurement collapse reduce practicality. This limits the use of quantum advice outside abstract models.
25. Conclusion
Quantum advice offers a powerful nonuniform extension to quantum computation. It highlights both the promise and the limitations of quantum-enhanced models. While more powerful than classical advice in certain settings, it is still constrained by fundamental quantum limitations like measurement, verification, and no-cloning.
