Table of Contents

1. Introduction
2. What Is Meta-Complexity?
3. Classical Meta-Complexity: A Recap
4. Meta-Complexity in the Quantum Setting
5. Quantum Kolmogorov Complexity
6. Measuring Descriptions of Quantum States
7. Quantum Circuit Minimization
8. Meta-Computational Complexity Classes
9. Quantum Circuit Lower Bounds and Meta-Complexity
10. Quantum Descriptive Complexity and QKC
11. Advice Complexity and Meta-Reasoning
12. QMA vs QCMA and Meta-Verification
13. Universal Quantum Circuits and Meta-Programming
14. Meta-Complexity of Quantum Machines
15. Quantum Self-Testing and Introspection
16. Quantum Meta-Algorithms
17. Cryptographic Connections
18. Open Questions in Quantum Meta-Complexity
19. Philosophical and Foundational Implications
20. Conclusion

1. Introduction

Quantum meta-complexity studies the complexity of problems about quantum complexity itself. This includes reasoning about the minimal description of quantum circuits, the verification of circuit hardness, and introspective models of computation.

2. What Is Meta-Complexity?

In classical complexity, meta-complexity addresses problems like:

• What is the size of the smallest circuit for a function?
• Can we efficiently verify whether a function is in a given class?
  These translate into quantum analogs in the context of quantum circuits, states, and machines.

3. Classical Meta-Complexity: A Recap

Classical meta-complexity includes:

• Circuit minimization problem (MCSP)
• Kolmogorov complexity
• Descriptive complexity of languages
  These problems are often hard (e.g., MCSP is believed not to be in P or NP-complete).

4. Meta-Complexity in the Quantum Setting

Quantum meta-complexity extends these questions to:

• Descriptions of quantum circuits and quantum states
• Verifiability of class membership (e.g., is a function in BQP?)
• Resource minimization in quantum computation

5. Quantum Kolmogorov Complexity

Quantum Kolmogorov Complexity (QKC) measures the length of the shortest quantum description (or circuit) that prepares a given quantum state. It generalizes the classical notion of algorithmic information.

6. Measuring Descriptions of Quantum States

A pure quantum state |ψ⟩ may require exponentially many classical bits to describe, but could be generated by a short quantum circuit. Meta-complexity analyzes such cases, focusing on compressibility and representability.

7. Quantum Circuit Minimization

The quantum circuit minimization problem (QCMP) asks: what is the smallest quantum circuit (in depth or size) that computes a given unitary or prepares a given state? This has analogs to MCSP and is also likely intractable.

8. Meta-Computational Complexity Classes

Just as P, NP, and PSPACE define function classes, meta-classes define reasoning tasks over these. In quantum theory, this might include:

• META-BQP: Reasoning about BQP computations
• Q-MCSP: Meta-complexity problem for BQP

9. Quantum Circuit Lower Bounds and Meta-Complexity

Studying quantum lower bounds often reduces to meta-complexity: proving that no small quantum circuit exists for a certain function. Such bounds are rare and difficult, linking to derandomization and pseudo-randomness.

10. Quantum Descriptive Complexity and QKC

Descriptive complexity connects logic and computation. Its quantum analog attempts to define how logical expressibility (in quantum logic) relates to circuit size or state preparation.

11. Advice Complexity and Meta-Reasoning

BQP/qpoly vs BQP/poly distinctions relate to meta-reasoning: what kind of advice lets us simulate or reason about computations at higher abstraction layers?

12. QMA vs QCMA and Meta-Verification

In QCMA, the verifier receives classical proofs; in QMA, quantum proofs. Determining the power gap requires meta-analysis: what is the complexity of verifying that a quantum circuit is a valid verifier?

13. Universal Quantum Circuits and Meta-Programming

Universal circuits that can emulate others with specified input parameters are a cornerstone of meta-computation. Their size overhead and structural properties are critical in defining quantum MCSP.

14. Meta-Complexity of Quantum Machines

Studying the minimal QTM (Quantum Turing Machine) that accepts a language or generates a state mirrors classical discussions about minimal automata, TMs, and programs—but with additional constraints due to unitarity and no-cloning.

15. Quantum Self-Testing and Introspection

Quantum meta-complexity includes self-testing protocols—ways to verify quantum computations or state properties using only external measurement. These are deeply introspective and essential to delegation protocols.

16. Quantum Meta-Algorithms

Meta-algorithms produce or verify quantum algorithms. They optimize across search spaces of circuits, simulate quantum devices, or verify that an output is consistent with a known quantum process.

17. Cryptographic Connections

Hardness of quantum meta-complexity may underlie the security of:

• Quantum obfuscation
• One-way state generation
• Unforgeable quantum tokens
  These often rely on the difficulty of learning or verifying properties of a quantum computation.

18. Open Questions in Quantum Meta-Complexity

• Is Q-MCSP BQP-hard?
• Can QKC be approximated with quantum resources?
• Are there quantum versions of meta-theorems in logic?

19. Philosophical and Foundational Implications

Quantum meta-complexity touches deep questions:

• What does it mean to “understand” a quantum state?
• Can we measure the “simplicity” of quantum phenomena?
• How do introspection and self-reference manifest in quantum theory?

20. Conclusion

Quantum meta-complexity brings self-referential reasoning into quantum computing. It combines logic, compression, circuit theory, and foundational philosophy to define and measure the complexity of quantum processes themselves.

Table of Contents

1. Introduction
2. Classical Advice and Non-uniform Computation
3. Quantum Advice: Definition and Motivation
4. The Class BQP/qpoly
5. Comparison with BQP/poly
6. Quantum Advice States vs Classical Advice Strings
7. Measuring Power of Quantum Advice
8. Limitations of Quantum Advice (No-Cloning, Measurement)
9. Untrusted vs Trusted Advice Models
10. Quantum Advice and One-Way Communication
11. Relationship with Quantum Communication Complexity
12. Oracle Separations Involving BQP/qpoly
13. BQP/qpoly vs QMA and QCMA
14. Advice in Multi-Prover Quantum Protocols
15. Quantum Advice and Random Access Codes
16. Cryptographic Implications
17. Hardness vs Randomness with Advice
18. Known Barriers and Open Problems
19. Physical Interpretations of Quantum Advice
20. 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.

Table of Contents

1. Introduction
2. What Is Property Testing?
3. Classical vs Quantum Property Testing
4. Quantum Query Models
5. Why Property Testing Is Important in Quantum Computing
6. Key Measures: Query Complexity and Distance
7. Property Testing for Functions
8. Testing Linearity with Quantum Queries
9. Quantum Fourier Sampling and Periodicity Testing
10. Testing Graph Properties with Quantum Algorithms
11. Quantum Junta Testing
12. Quantum Distribution Testing
13. Quantum Algorithms for Group Property Testing
14. Quantum vs Classical Complexity Gaps
15. Limits and Lower Bounds in Quantum Testing
16. Quantum Testing of Quantum States
17. Property Testing in Quantum Machine Learning
18. Applications to Cryptography and Verification
19. Open Questions and Research Directions
20. Conclusion

1. Introduction

Quantum property testing is the study of algorithms that determine whether a function or object possesses a certain global property or is far from having it, using only a few quantum queries. It offers exponential speedups over classical methods in certain settings.

2. What Is Property Testing?

Property testing involves designing algorithms that decide whether an object has a specific property or is ε-far from any object having that property, typically with high probability and few queries.

3. Classical vs Quantum Property Testing

Quantum testers leverage superposition and interference to extract global information with fewer queries than classical testers. This can lead to exponential query savings, depending on the property.

4. Quantum Query Models

Quantum testers access oracles that encode functions or data, querying them in superposition. The models include:

• Boolean functions
• Graphs and matrices
• Distributions
• Quantum states

5. Why Property Testing Is Important in Quantum Computing

Testing is central to:

• Fast verification of computations
• Error detection in quantum systems
• Learning and PAC testing
• Design of interactive proof systems and QMA protocols

6. Key Measures: Query Complexity and Distance

The two main complexity measures are:

• Query complexity: number of oracle accesses
• ε-distance: fraction of inputs on which the function must be changed to obtain the property

7. Property Testing for Functions

In Boolean function testing, common properties include:

• Linearity
• Monotonicity
• Symmetry
  Quantum testers use tools like the Hadamard transform and Fourier analysis to test these properties efficiently.

8. Testing Linearity with Quantum Queries

Quantum linearity tests use Fourier sampling and phase estimation. For example, the Blum–Luby–Rubinfeld (BLR) linearity test can be accelerated using quantum queries, requiring fewer samples.

9. Quantum Fourier Sampling and Periodicity Testing

Quantum property testers can efficiently test periodicity using quantum Fourier sampling, as in Simon’s problem and the Bernstein–Vazirani algorithm, offering exponential savings.

10. Testing Graph Properties with Quantum Algorithms

Quantum testers can analyze:

• Connectivity
• Expansion
• Bipartiteness
• Triangle-freeness
  They use quantum walks, amplitude amplification, and adjacency matrix access for efficient testing.

11. Quantum Junta Testing

A k-junta is a Boolean function that depends on at most k variables. Quantum algorithms can test if a function is a k-junta using significantly fewer queries than classical methods, especially in the uniform distribution setting.

12. Quantum Distribution Testing

Quantum testers can compare or estimate distributions using fewer samples. Examples include:

• Testing closeness of two distributions
• Identity testing
• Uniformity testing
  Quantum tests rely on techniques like quantum state discrimination and swap tests.

13. Quantum Algorithms for Group Property Testing

Quantum testers can detect group properties such as:

• Commutativity
• Associativity
• Subgroup relations
  These use oracle access to group operations and exploit structure using the quantum Fourier transform.

14. Quantum vs Classical Complexity Gaps

Some properties admit quantum testers with exponential advantage, e.g. Simon’s periodicity testing or some distribution identity tests. Others show only polynomial improvements.

15. Limits and Lower Bounds in Quantum Testing

Not all properties can be tested exponentially faster. Lower bounds use the adversary method, polynomial method, or communication complexity to prove limitations.

16. Quantum Testing of Quantum States

Quantum property testing extends to verifying properties of quantum states:

• Entanglement testing
• Purity testing
• State distinguishability
  These often require only a few copies of the quantum state.

17. Property Testing in Quantum Machine Learning

Testing serves in quantum data filtering and validation. For instance:

• Is a given circuit a good classifier?
• Is the dataset near a low-entropy distribution?
  These tests assist in building robust QML pipelines.

18. Applications to Cryptography and Verification

Quantum property testing is used in:

• Interactive proofs and QMA
• Verification of quantum computation (e.g., delegated protocols)
• Zero-knowledge systems
• Quantum money and fingerprinting schemes

19. Open Questions and Research Directions

• Tight bounds for quantum testers on new properties
• Quantum property testing of quantum channels
• Hybrid quantum-classical testers
• Derandomization of testers with noise tolerance

20. Conclusion

Quantum property testing combines the efficiency of quantum computation with robustness guarantees of property testing. It offers a promising framework for verification, learning, and complexity classification in both theoretical and practical quantum systems.

Table of Contents

1. Introduction
2. What Are Lattices in Computational Mathematics?
3. Key Lattice Problems: SVP, CVP, SIVP
4. Relevance to Cryptography and Complexity
5. Lattices and Worst-Case to Average-Case Reductions
6. Ajtai’s Theorem and Its Quantum Implications
7. Learning with Errors (LWE) and Quantum Reductions
8. LWE Hardness Based on Worst-Case Lattice Problems
9. SIS Problem and Quantum Security
10. Reductions from LWE to SVP and SIVP
11. Regev’s Quantum Reduction for LWE
12. GapSVP and Approximation Hardness
13. Quantum Reductions vs Classical Reductions
14. Oracle Access in Quantum Lattice Reductions
15. Bounded Distance Decoding (BDD) and QBDDP
16. Applications in Post-Quantum Cryptography
17. Security Assumptions Against Quantum Attacks
18. Open Problems in Quantum Lattice Reductions
19. Lattice-Based Quantum Advantage and Limits
20. Conclusion

1. Introduction

Lattice-based problems play a central role in post-quantum cryptography and quantum complexity. Quantum reductions allow us to connect the hardness of cryptographic schemes to worst-case assumptions, ensuring security even in the face of quantum adversaries.

2. What Are Lattices in Computational Mathematics?

A lattice is a discrete additive subgroup of \( \mathbb{R}^n \), defined by integer linear combinations of basis vectors. Lattice problems involve finding shortest, closest, or good approximations to vectors within such structured spaces.

3. Key Lattice Problems: SVP, CVP, SIVP

• SVP (Shortest Vector Problem): Find the shortest nonzero vector in a lattice.
• CVP (Closest Vector Problem): Find the closest lattice vector to a target point.
• SIVP (Shortest Independent Vectors Problem): Find n short linearly independent lattice vectors.

4. Relevance to Cryptography and Complexity

Lattice problems are hard to solve even approximately. Their presumed quantum resistance makes them ideal for secure cryptographic primitives like public-key encryption, digital signatures, and homomorphic encryption.

5. Lattices and Worst-Case to Average-Case Reductions

Ajtai pioneered reductions that show solving average-case lattice problems implies solving worst-case instances. This is crucial for basing cryptography on strong complexity-theoretic foundations.

6. Ajtai’s Theorem and Its Quantum Implications

Ajtai’s theorem showed that certain random lattice instances are as hard as worst-case problems. These ideas extend into quantum complexity by constructing secure schemes that resist quantum algorithms.

7. Learning with Errors (LWE) and Quantum Reductions

LWE involves solving noisy linear equations modulo q. Regev showed a quantum reduction from worst-case SIVP to average-case LWE, making LWE a cornerstone of quantum-secure cryptography.

8. LWE Hardness Based on Worst-Case Lattice Problems

The LWE problem is conjectured to be hard for quantum adversaries, assuming the worst-case hardness of lattice problems like GapSVP and SIVP. This underpins post-quantum encryption like Kyber and Frodo.

9. SIS Problem and Quantum Security

The Short Integer Solution (SIS) problem is another lattice challenge used in cryptographic constructions. Quantum reductions show its hardness also stems from worst-case lattice assumptions.

10. Reductions from LWE to SVP and SIVP

Regev’s reduction shows that solving LWE with small noise lets you solve approximate versions of SVP and SIVP on n-dimensional lattices using quantum computation.

11. Regev’s Quantum Reduction for LWE

This landmark result shows:

• LWE is quantumly hard under worst-case SIVP
• The reduction is efficient and relies on discrete Gaussian sampling
• It established the basis for LWE-based encryption and learning systems

12. GapSVP and Approximation Hardness

GapSVP asks whether the shortest vector is smaller or larger than a given threshold. It is a promise problem believed hard for quantum computers for certain approximation factors.

13. Quantum Reductions vs Classical Reductions

Quantum reductions use interference and entanglement to encode multiple lattice problems. They may achieve tighter hardness guarantees than classical reductions, but require more involved oracle constructions.

14. Oracle Access in Quantum Lattice Reductions

Quantum reductions often assume access to oracles that solve average-case LWE or SIS. Queries to these oracles are performed in superposition, amplifying the hardness relationship.

15. Bounded Distance Decoding (BDD) and QBDDP

BDD asks to find the lattice point nearest to a target when the distance is less than half the minimum vector length. Quantum BDD (QBDDP) models query this under quantum constraints.

16. Applications in Post-Quantum Cryptography

Lattice-based primitives with quantum reductions include:

• LWE-based public-key cryptosystems
• Homomorphic encryption
• Signature schemes (e.g., Dilithium, Falcon)
• Identity-based encryption

17. Security Assumptions Against Quantum Attacks

Quantum reductions strengthen security claims by tying scheme breakage to worst-case lattice problems, which currently resist both Grover’s and quantum Fourier-based techniques.

18. Open Problems in Quantum Lattice Reductions

• Can tighter quantum reductions be developed for NIST candidates?
• Do quantum reductions apply to Ring-LWE or Module-LWE?
• Can hybrid quantum-classical reductions yield practical benefits?

19. Lattice-Based Quantum Advantage and Limits

While lattices resist known quantum algorithms, it remains open whether future quantum methods could break current assumptions. Quantum reductions provide our strongest current guarantees.

20. Conclusion

Lattice problems form the backbone of quantum-resistant cryptography. Quantum reductions bridge worst-case complexity and cryptographic security, playing a foundational role in building the next generation of secure systems.

Table of Contents

1. Introduction
2. What Are Relativized Worlds?
3. Classical Context: P vs NP with Oracles
4. Motivation for Studying Relativization
5. Quantum Oracle Machines
6. BQP with Oracles (BQP^O)
7. Relativized Separations: BQP vs BPP
8. BQP vs PH in Oracle Worlds
9. Simon’s Problem and Oracle Constructions
10. Fourier Checking and Relativized BQP
11. QMA and QCMA with Oracles
12. MIP*, Entanglement, and Relativized Protocols
13. Random Oracles in Quantum Complexity
14. Limitations of Relativization
15. Non-Relativizing Techniques
16. Barriers to Quantum Lower Bounds
17. Oracle Separations and Cryptography
18. Oracle Separations and Hardness vs Randomness
19. Open Problems and Conjectures
20. Conclusion

1. Introduction

Relativized worlds are hypothetical universes where all computations have access to the same oracle function. In quantum complexity theory, these models allow researchers to explore the power of quantum algorithms under controlled assumptions.

2. What Are Relativized Worlds?

A relativized world gives all Turing or quantum machines access to an oracle—a black-box subroutine—modifying the landscape of what problems are solvable and what class relationships exist.

3. Classical Context: P vs NP with Oracles

In classical complexity, Baker-Gill-Solovay showed there exist oracles A and B such that:

• P^A = NP^A
• P^B ≠ NP^B
  This implies that relativizing techniques alone cannot resolve P vs NP.

4. Motivation for Studying Relativization

Oracle-based reasoning:

• Highlights class separations
• Identifies barriers in proof techniques
• Suggests limits of generalization from query models to real-world computation

5. Quantum Oracle Machines

Quantum oracle machines can query functions in superposition. This enhances power and speed for some tasks, such as Simon’s problem, Grover search, and hidden subgroup problems.

6. BQP with Oracles (BQP^O)

The class BQP^O consists of problems solvable by a bounded-error quantum polynomial-time machine with access to oracle O. This class changes depending on the oracle, revealing how quantum algorithms differ from classical counterparts.

7. Relativized Separations: BQP vs BPP

There exist oracles relative to which:

• BPP^O ≠ BQP^O
• BPP^O ⊂ BQP^O
  These results show that quantum models are strictly stronger in some relativized settings.

8. BQP vs PH in Oracle Worlds

Quantum algorithms (e.g., Fourier checking) have shown that BQP can lie outside PH (polynomial hierarchy) relative to some oracles. This supports the conjecture that BQP ∉ PH even in the unrelativized world.

9. Simon’s Problem and Oracle Constructions

Simon’s problem was one of the first to demonstrate an exponential separation between quantum and classical query complexity. It forms the basis for oracle A where BQP^A ≠ BPP^A.

10. Fourier Checking and Relativized BQP

Fourier checking is used to construct an oracle problem solvable in BQP but hard for PH. This supports relativized separation between quantum polynomial time and classical hierarchy classes.

11. QMA and QCMA with Oracles

Oracles can also separate QMA (quantum proof) from QCMA (classical proof). For instance, there exist oracles such that QMA^O ≠ QCMA^O, revealing differences in verification power under relativized conditions.

12. MIP*, Entanglement, and Relativized Protocols

Entangled-prover interactive proof systems (MIP) use nonlocal correlations. Relativized worlds show how MIP can exceed classical MIP limits, leading to major results like MIP* = RE.

13. Random Oracles in Quantum Complexity

In random oracle models, the oracle is chosen uniformly at random. Quantum separations have been shown to persist even with random oracles, reinforcing the robustness of quantum advantages.

14. Limitations of Relativization

Relativized results cannot resolve unrelativized questions like P vs NP or BQP vs PH. They serve as heuristics, not proofs of separation in the real world.

15. Non-Relativizing Techniques

Some quantum class separations require non-relativizing tools:

• Interactive proof rewinding
• Circuit lower bounds
• Diagonalization beyond oracles

16. Barriers to Quantum Lower Bounds

Despite oracle separations, proving lower bounds (e.g., that PH ⊄ BQP) without oracles remains hard. Relativized worlds highlight this gap.

17. Oracle Separations and Cryptography

Quantum oracle separations help analyze quantum security. They show limits of classical reductions and inform the design of quantum-resistant cryptographic schemes.

18. Oracle Separations and Hardness vs Randomness

Oracle constructions also inform the relationship between randomness and computational hardness in quantum models. They help define limits of quantum derandomization and PRG-based reductions.

19. Open Problems and Conjectures

• Can BQP be shown to not be in PH unrelativized?
• Are there oracles separating QMA from PSPACE?
• What is the role of advice in oracle models?

20. Conclusion

Relativized worlds serve as a vital tool in quantum complexity. While they don’t resolve class separations conclusively, they shape our understanding of what is likely separable and illuminate quantum-classical distinctions in computation.