| name | limited-memory-quantum-testing |
| description | Stabilizer state testing and learning under quantum memory constraints. Proves testing complexity is Θ(n-k) with k-qubit memory, learning is Θ(n²/k), and exponential lower bound for purity testing. Identifies coherent quantum memory as the resource enabling testing-vs-learning separation. |
| category | quantum |
| trigger_words | stabilizer testing, quantum memory constraint, hidden shift problem, stochastic orthogonal group, purity testing, quantum state learning, memory-bounded quantum algorithms, likelihood ratio bounds |
| arxiv_id | 2607.02444 |
| created | 2026-07-05T00:00:00.000Z |
Optimal Stabilizer Testing and Learning with Limited Quantum Memory
Core Methodology
1. Problem Setting
- Algorithm receives copies of unknown n-qubit state sequentially
- May keep only k qubits of coherent quantum memory between measurements
- Classical setting (Gross, Nezami, Walter): testing uses 6 copies (dimension-independent), learning uses Θ(n)
2. Main Results
Testing Complexity: Θ(n-k)
- Upper bound via novel connection to hidden shift problem
- Lower bound via average-case bounds on likelihood ratios using combinatorics of stochastic orthogonal group
Learning Complexity: Θ(n²/k) (non-adaptive framework)
3. Key Insight
- Coherent quantum memory is the resource enabling separation between testing and learning
- Even with k=0.99n qubits memory, no constant-copy stabilizer tester exists
- For k=cn (0<c<1), testing is as hard as learning: both require Θ(n) copies
4. Purity Testing
- Proves exponential lower bound for purity testing
- Holds even when memory may be left coherent throughout protocol
Implementation Steps
- Formulate stabilizer testing problem with k-qubit memory constraint
- Map to hidden shift problem for upper bound construction
- Use stochastic orthogonal group combinatorics for lower bound
- Analyze purity testing as application of techniques
Applications
- Quantum state verification protocols
- Memory-constrained quantum algorithm design
- Quantum property testing complexity theory
- Quantum learning theory foundations
Pitfalls
- The separation between testing (6 copies) and learning (Θ(n)) is lost under memory constraints
- k must be o(n) for meaningful results — near-full memory trivializes
- Non-adaptive learning framework — adaptive case may differ
- Purity testing lower bound is exponential — fundamental hardness
