Table of Contents
- Introduction
- What Is Approximation in Quantum Contexts?
- Exact vs Approximate Computation
- Complexity of Approximate Decision Problems
- Quantum Approximation Algorithms
- Variational Quantum Algorithms and Heuristics
- Approximating Ground State Energies
- The Local Hamiltonian Problem
- QMA-Hardness of Approximate Ground Energy Estimation
- Hardness of Approximating Quantum Separability
- Quantum PCP Conjecture
- Approximate Quantum Error Correction
- Approximate State Discrimination
- Approximation of Quantum Channel Capacities
- Hardness in Estimating Entanglement Measures
- Approximating Fidelity and Trace Distance
- Complexity of Approximate Quantum Measurements
- Approximating Quantum Circuit Output Probabilities
- Sampling Problems and Quantum Supremacy
- Additive vs Multiplicative Approximations
- Quantum Interactive Proofs and Approximation
- Robustness of Quantum Proof Systems
- Approximating Quantum Non-Local Games
- Implications for Quantum Cryptography
- Conclusion
1. Introduction
In computational complexity, approximation problems arise when finding exact solutions is infeasible. In quantum computing, many naturally occurring problems — especially in quantum chemistry, simulation, and cryptography — require approximating certain properties rather than solving them exactly. The hardness of quantum approximation refers to the computational difficulty of these tasks, even for quantum computers.
2. What Is Approximation in Quantum Contexts?
Approximation refers to:
- Estimating numerical values (e.g., energy levels)
- Distinguishing states within some threshold
- Simulating distributions to within statistical error
3. Exact vs Approximate Computation
- Exact: Compute precise outputs or classifications
- Approximate: Accept near-accurate solutions within defined bounds
- Often measured in additive or multiplicative error margins
4. Complexity of Approximate Decision Problems
Example: Decide if a value is ≤ a or ≥ b (with gap \( b – a \geq \epsilon ))
This forms the basis of promise problems, critical in quantum complexity (e.g., QMA).
5. Quantum Approximation Algorithms
Quantum algorithms may:
- Approximate functions (e.g., amplitudes, matrix elements)
- Estimate physical properties (energy, fidelity)
- Rely on variational or probabilistic techniques
6. Variational Quantum Algorithms and Heuristics
- VQE and QAOA are key algorithms
- Approximate ground states using parameterized circuits
- Success depends on optimization landscape and noise resilience
7. Approximating Ground State Energies
Central to physics and quantum chemistry:
- Find the lowest eigenvalue of a local Hamiltonian
- Exact computation is QMA-hard
- Approximation is also QMA-hard within inverse polynomial precision
8. The Local Hamiltonian Problem
Analogous to classical MAX-SAT:
- Given local Hamiltonian \( H ), estimate ground energy
- Decide if energy ≤ \( a ) or ≥ \( b ), with \( b – a \geq \frac{1}{\text{poly}(n)} )
- Known to be QMA-complete
9. QMA-Hardness of Approximate Ground Energy Estimation
Even approximating ground state energy to inverse polynomial accuracy is QMA-hard, making simulation of quantum materials computationally intractable in general.
10. Hardness of Approximating Quantum Separability
Deciding whether a state is:
- Close to separable
- Or far from any separable state
Is NP-hard and believed QMA-hard in various distance measures (trace norm, fidelity)
11. Quantum PCP Conjecture
Quantum analog of classical PCP:
- Suggests even approximate verification of quantum proofs is QMA-hard
- Would imply robust inapproximability of quantum constraint satisfaction problems
- Still unresolved
12. Approximate Quantum Error Correction
Finding optimal codes for approximate error correction:
- Requires estimating fidelity of recovery
- Generally hard; best known methods are heuristic
13. Approximate State Discrimination
- Given two mixed quantum states, distinguish them
- Optimal measurement success probability is hard to approximate
- Relevant in quantum communications and cryptography
14. Approximation of Quantum Channel Capacities
- Computing classical/quantum capacity of a quantum channel is open
- Additive approximation is known to be QIP-complete in some cases
15. Hardness in Estimating Entanglement Measures
Estimating:
- Entanglement of formation
- Relative entropy of entanglement
- Are hard due to optimization over exponentially large Hilbert spaces
16. Approximating Fidelity and Trace Distance
Given two quantum states:
- Computing fidelity: \( F(\rho, \sigma) = \left( \text{Tr} \sqrt{\sqrt{\rho} \sigma \sqrt{\rho}} \right)^2 )
- Trace distance: \( \frac{1}{2} |\rho – \sigma|_1 )
Hard to compute for high-dimensional systems
17. Complexity of Approximate Quantum Measurements
- Determining if a measurement approximates an ideal observable
- Affects quantum metrology and tomography
- Approximation quality is sensitive to noise and system size
18. Approximating Quantum Circuit Output Probabilities
- Sampling from output distribution of a quantum circuit
- Estimating specific amplitudes (additive error) is #P-hard
- Underlies arguments for quantum supremacy
19. Sampling Problems and Quantum Supremacy
Hardness of approximate sampling:
- Random circuit sampling
- Boson sampling
- Instantaneous quantum polynomial time (IQP)
Are believed hard for classical computers, but feasible for noisy quantum systems
20. Additive vs Multiplicative Approximations
- Additive: Absolute error (e.g., within 0.01)
- Multiplicative: Relative error (e.g., within 5%)
- Additive approximations are more common in quantum hardness results
21. Quantum Interactive Proofs and Approximation
- QIP = PSPACE
- Approximate acceptance probabilities are PSPACE-hard to compute
- Used to show hardness of various estimation problems
22. Robustness of Quantum Proof Systems
- QMA protocols may be fragile under approximation
- Quantum PCP seeks to develop robust quantum proof systems
- Still a major open area
23. Approximating Quantum Non-Local Games
- Many non-local games (e.g., Magic Square) involve approximating win probabilities
- Related to Tsirelson bounds and quantum value of games
- Often NEXP or MIP* hard
24. Implications for Quantum Cryptography
- Cryptographic hardness may be tied to inapproximability
- Quantum-secure primitives may rely on approximate indistinguishability
- Examples: Quantum one-way functions, obfuscation schemes
25. Conclusion
Approximating quantum properties — from ground states to channel capacities — lies at the heart of quantum computing, physics, and cryptography. Despite the promise of quantum computers, many of these problems remain provably hard, even to approximate. As such, understanding the hardness of quantum approximation is critical for assessing the true capabilities and limitations of quantum technologies.