Table of Contents

1. Introduction
2. Classical PCP Theorem: A Quick Recap
3. Motivation for Quantum PCPs
4. What Are Probabilistically Checkable Quantum Proofs?
5. Quantum PCP Conjecture
6. Quantum Locally Checkable Proofs
7. Complexity Classes: QMA and QPCP
8. The QPCP Theorem (Conjectured)
9. Quantum vs Classical Proof Verification
10. Quantum Low-Degree Testing
11. Quantum Error-Correcting Codes and PCPs
12. Stabilizer Codes and Local Hamiltonians
13. Gap Amplification in Quantum Systems
14. Hardness of Approximating Local Hamiltonian Problems
15. Entanglement and Multi-Prover PCPs
16. Nonlocal Games and MIP* = RE
17. Soundness and Completeness in QPCP
18. Limitations and Known Barriers
19. Research Directions and Open Problems
20. Conclusion

1. Introduction

Probabilistically Checkable Quantum Proofs (PCQPs) extend the classical PCP framework into the quantum domain. They aim to define proof systems where the correctness of a quantum statement can be verified with high confidence using only limited quantum queries.

2. Classical PCP Theorem: A Quick Recap

The classical PCP theorem states that every problem in NP has a proof that can be verified with high probability by inspecting only a few bits. This result underpins hardness of approximation and robust verification in classical complexity theory.

3. Motivation for Quantum PCPs

Quantum proofs are fragile and non-clonable. Verifying them efficiently, and with high robustness, is crucial for quantum complexity theory, error correction, and the hardness of quantum approximation problems.

4. What Are Probabilistically Checkable Quantum Proofs?

A PCQP allows the verifier to query a few qubits from a quantum proof and decide with high probability whether the input is valid. The verifier is allowed quantum computation but accesses the proof only in a limited way.

5. Quantum PCP Conjecture

The quantum PCP conjecture posits that approximating the ground state energy of local Hamiltonians is QMA-hard even for constant relative error. It would be the quantum analog of the classical PCP theorem.

6. Quantum Locally Checkable Proofs

A locally checkable quantum proof allows the verifier to measure small subsets (e.g., constant-sized) of the total proof state, ideally without disturbing the rest. This models partial verification of entangled quantum states.

7. Complexity Classes: QMA and QPCP

• QMA: Quantum Merlin-Arthur (quantum analog of NP)
• QPCP: Class of problems with quantum PCPs
  Whether QMA = QPCP is open, and central to the quantum PCP conjecture.

8. The QPCP Theorem (Conjectured)

If proven, the QPCP theorem would imply:

• Robust verification of quantum computations
• Hardness of approximation for quantum optimization
• Stronger quantum error resilience

9. Quantum vs Classical Proof Verification

Classical PCPs allow repeated queries to a copyable proof. Quantum proofs cannot be cloned, so QPCPs must balance verification accuracy with non-destructive access strategies.

10. Quantum Low-Degree Testing

Quantum low-degree tests ensure that a state encodes a low-degree polynomial function over a finite field. These are foundational for constructing quantum analogs of PCP proof systems.

11. Quantum Error-Correcting Codes and PCPs

Stabilizer codes and holographic codes form the basis of some QPCP models. They allow encoding of quantum information in a form that supports local checkability.

12. Stabilizer Codes and Local Hamiltonians

Many QPCP constructions are based on mapping Hamiltonians onto stabilizer codes. The ground state properties encode a quantum witness whose validity can be verified locally.

13. Gap Amplification in Quantum Systems

Gap amplification magnifies the spectral gap between accepted and rejected proofs. This is crucial for achieving robust soundness in PCQPs, especially in noisy or entangled settings.

14. Hardness of Approximating Local Hamiltonian Problems

The k-Local Hamiltonian problem is the canonical QMA-complete problem. Proving it hard to approximate within a constant factor would support the QPCP conjecture.

15. Entanglement and Multi-Prover PCPs

Multi-prover quantum PCPs (MPCQPs) involve multiple entangled provers. These are connected to quantum nonlocal games and underpin results like MIP* = RE, showing the power of quantum correlations.

16. Nonlocal Games and MIP* = RE

The recent result MIP* = RE shows that quantum multi-prover interactive proofs can verify any computably enumerable language. This connects PCQPs to undecidability and infinite-dimensional entanglement.

17. Soundness and Completeness in QPCP

• Completeness: Honest prover convinces the verifier with high probability
• Soundness: Cheating prover fails to do so unless the proof is near-correct
  Maintaining both under limited access is a major challenge.

18. Limitations and Known Barriers

Challenges include:

• No-cloning constraints
• Lack of full gap amplification tools in quantum settings
• Measurement disturbance from verification

19. Research Directions and Open Problems

• Proving or refuting the quantum PCP conjecture
• Constructing efficient quantum locally testable codes
• Developing scalable quantum low-degree tests
• Characterizing QPCP vs QMA complexity

20. Conclusion

Probabilistically checkable quantum proofs aim to bring classical ideas of robust verification into the quantum realm. While the QPCP conjecture remains unresolved, progress in quantum coding, interactive proofs, and Hamiltonian complexity continues to shape this exciting frontier.

Table of Contents

1. Introduction
2. Classical Hardness vs Randomness: A Brief Overview
3. Quantum Analogs of Pseudorandomness
4. Derandomization and Quantum Algorithms
5. Quantum Pseudorandom Generators (QPRGs)
6. BQP vs BPP and Randomness Elimination
7. Hardness Assumptions in Quantum Cryptography
8. Yao’s Principle in the Quantum Setting
9. Quantum One-Way Functions and Randomness Extraction
10. Quantum Hardness Amplification
11. Relationship Between Quantum Advice and Randomness
12. Quantum Kolmogorov Complexity and Random Strings
13. Entropy, Min-Entropy, and Quantum Extractors
14. Randomness Expansion with Quantum Devices
15. Quantum Randomness Certification and Bell Inequalities
16. Quantum Indistinguishability and PRFs
17. Oracle Constructions and Separation Results
18. Open Problems in Quantum Hardness vs Randomness
19. Implications for Quantum Foundations
20. Conclusion

1. Introduction

The “hardness vs randomness” paradigm explores how computational hardness can substitute for randomness, and vice versa. In quantum computing, this relationship is reshaped by entanglement, quantum advice, and non-classical correlations.

2. Classical Hardness vs Randomness: A Brief Overview

In classical complexity, the idea is that if some problems are sufficiently hard, then pseudorandom generators (PRGs) can be built, enabling derandomization. This is formalized in results connecting circuit lower bounds to BPP = P.

3. Quantum Analogs of Pseudorandomness

Quantum pseudorandomness deals with generating quantum states or operations that are indistinguishable from Haar-random ones. These have applications in encryption, verification, and quantum supremacy.

4. Derandomization and Quantum Algorithms

The goal of derandomization is to reduce or eliminate reliance on randomness. For quantum algorithms, this means finding deterministic algorithms or reusing entropy sources efficiently while maintaining quantum speedups.

5. Quantum Pseudorandom Generators (QPRGs)

A QPRG outputs quantum states or unitaries that appear random to efficient quantum observers. Their existence relies on quantum-secure hardness assumptions and enables reductions in algorithmic randomness.

6. BQP vs BPP and Randomness Elimination

BQP (quantum polytime) can simulate BPP (bounded-error classical polytime). This suggests quantum machines can eliminate some classical randomness, although derandomization of BPP itself remains unresolved.

7. Hardness Assumptions in Quantum Cryptography

Quantum-secure PRGs and encryption rely on problems like lattice-based LWE and quantum-resistant hash functions. These demonstrate how quantum hardness underpins randomness generation and security.

8. Yao’s Principle in the Quantum Setting

Yao’s minimax principle connects worst-case and average-case complexity. In quantum settings, it underlies randomized-to-deterministic reductions and the design of quantum strategies that simulate average-case scenarios.

9. Quantum One-Way Functions and Randomness Extraction

Quantum-secure one-way functions lead to randomness extractors that can purify weak entropy into nearly uniform random strings. These are crucial for cryptographic protocols and secure quantum randomness expansion.

10. Quantum Hardness Amplification

Hardness amplification transforms mildly hard problems into very hard ones. In the quantum realm, it relates to hiding structure from quantum adversaries, thus enhancing cryptographic and algorithmic randomness.

11. Relationship Between Quantum Advice and Randomness

Quantum advice (quantum inputs from an all-powerful source) may contain hard-to-generate randomness. Separating BQP/poly from BQP/qpoly reveals how randomness can or cannot be embedded in quantum advice.

12. Quantum Kolmogorov Complexity and Random Strings

Quantum Kolmogorov complexity measures the compressibility of quantum states. Random states have high complexity and cannot be generated efficiently—serving as a quantum notion of randomness.

13. Entropy, Min-Entropy, and Quantum Extractors

Quantum extractors convert weak sources of entropy into usable randomness, even in the presence of quantum side information. These are vital for randomness expansion and privacy amplification.

14. Randomness Expansion with Quantum Devices

Quantum protocols can expand short seeds into long random sequences using entanglement and nonlocality. Devices like Bell-test randomness generators are based on provably hard-to-simulate quantum processes.

15. Quantum Randomness Certification and Bell Inequalities

Quantum systems can certify their own randomness through violation of Bell inequalities. This provides device-independent randomness, assuming only minimal quantum-mechanical assumptions.

16. Quantum Indistinguishability and PRFs

Pseudorandom functions (PRFs) remain indistinguishable from random functions under quantum access. Quantum hardness assumptions define whether PRFs can survive adversaries with superposition query capability.

17. Oracle Constructions and Separation Results

Oracle separations help understand if randomness and hardness trade-offs differ in quantum models. For instance, there exist oracles where BQP ≠ P, affecting derandomization paths.

18. Open Problems in Quantum Hardness vs Randomness

• Does BQP = BPP imply circuit lower bounds?
• Can quantum PRGs eliminate quantum randomness in BQP?
• Is there a full derandomization of QMA or QIP?

19. Implications for Quantum Foundations

Hardness vs randomness touches foundational questions:

• Is randomness intrinsic or computable?
• Can quantum computers simulate fundamental stochasticity?
• What distinguishes quantum entropy from classical sources?

20. Conclusion

The interplay between hardness and randomness in quantum computing drives research in cryptography, complexity, and foundations. Understanding how quantum systems generate, amplify, and simulate randomness is central to unlocking the full power of quantum algorithms and secure systems.

Table of Contents

1. Introduction
2. What Are Black-Box Models?
3. Motivation for Black-Box Separations
4. Classical Black-Box Separation Examples
5. Quantum Black-Box Access
6. Oracle Constructions in Quantum Complexity
7. Quantum vs Classical Separation Techniques
8. Separating BQP from BPP via Oracles
9. Black-Box Separation of BQP and PH
10. Simon’s Problem and Hidden Subgroup Separations
11. Oracle Separations for QMA and QCMA
12. Relativized World Constructions
13. Query Complexity and Oracle Models
14. Limits of Black-Box Separations
15. Relativizing and Non-Relativizing Techniques
16. Algebraic and Combinatorial Oracle Designs
17. Implications for Cryptography
18. Separations and Quantum Advantage
19. Open Questions in Black-Box Quantum Separations
20. Conclusion

1. Introduction

Black-box separations (also called oracle separations) are used to demonstrate that two computational models or complexity classes behave differently when given access to the same abstract subroutine or “oracle.” In quantum computing, they highlight fundamental differences between quantum and classical complexity.

2. What Are Black-Box Models?

In black-box models, algorithms can only access information about a function or problem via queries to an oracle. They cannot analyze or exploit internal structure, making the oracle a powerful abstraction for studying complexity.

3. Motivation for Black-Box Separations

Black-box separations help:

• Prove relative strengths of complexity classes
• Show limitations of reductions or techniques
• Indicate that separating classes in the unrelativized world may require non-black-box methods

4. Classical Black-Box Separation Examples

In classical theory:

• There exists an oracle A such that P^A ≠ NP^A
• P^A = NP^A under other oracles
  These show that questions like P vs NP are not resolvable by relativizing techniques alone.

5. Quantum Black-Box Access

Quantum algorithms query black-box oracles in superposition. This allows interference-based approaches that yield speedups, such as in Grover’s and Simon’s algorithms.

6. Oracle Constructions in Quantum Complexity

An oracle A can be constructed so that BQP^A ≠ BPP^A. These relativized separations demonstrate problems solvable efficiently with quantum queries that resist all classical approaches under oracle constraints.

7. Quantum vs Classical Separation Techniques

Quantum separations rely on:

• Query complexity bounds
• Fourier analysis over boolean functions
• Information-theoretic limitations
  These differ from classical circuit or Turing machine arguments.

8. Separating BQP from BPP via Oracles

Examples include:

• Simon’s Problem: exponential separation
• Fourier Checking: relativized separation with polynomial advantage
  Such results prove that BQP is strictly stronger than BPP relative to some oracles.

9. Black-Box Separation of BQP and PH

The Polynomial Hierarchy (PH) is suspected not to contain BQP. Oracle constructions support this:

• Oracle A such that BQP^A ⊄ PH^A
  This strengthens the conjecture that quantum polynomial time goes beyond classical bounded hierarchy levels.

10. Simon’s Problem and Hidden Subgroup Separations

Simon’s problem and the Hidden Subgroup Problem (HSP) give exponential quantum-classical gaps. In the black-box model, they separate BQP from classical probabilistic classes with provable lower bounds.

11. Oracle Separations for QMA and QCMA

Oracles can separate QMA (quantum witness) from QCMA (classical witness). These separations help define the power of quantum proofs and verifiers, under relativized access.

12. Relativized World Constructions

Black-box separations imply that certain proof techniques won’t settle class separations without non-relativizing arguments. This forces researchers to explore new frameworks beyond oracle-based reasoning.

13. Query Complexity and Oracle Models

Query models formalize black-box access and define bounds on the number of queries required. These are central to quantum speedups and underpin black-box separation results.

14. Limits of Black-Box Separations

Such separations are not conclusive for the unrelativized world. A black-box separation does not mean two classes are actually different—it only shows that current relativizing techniques cannot prove equality.

15. Relativizing and Non-Relativizing Techniques

Relativizing techniques (e.g., simulation) respect oracle boundaries. Non-relativizing techniques (e.g., arithmetization, diagonalization) may bypass oracle limitations and are necessary for proving unrelativized separations.

16. Algebraic and Combinatorial Oracle Designs

Oracle functions are often constructed using algebraic properties (Fourier coefficients) or combinatorial gadgets (pseudo-random generators) to achieve separations without revealing structural shortcuts.

17. Implications for Cryptography

Black-box models relate to cryptographic hardness assumptions. Oracle separations help model scenarios where quantum adversaries outperform classical ones, influencing quantum security design.

18. Separations and Quantum Advantage

Demonstrating oracle-based separations helps validate claims of quantum advantage by showing fundamental limits of classical simulation, even with access to idealized resources.

19. Open Questions in Black-Box Quantum Separations

• Are there relativized separations between QMA and PSPACE?
• Can black-box techniques separate BQP from NP?
• Do all quantum speedups require black-box access?

20. Conclusion

Black-box separations remain a powerful tool in quantum complexity theory. They clarify class boundaries, challenge classical assumptions, and guide the search for new, non-relativizing proof techniques.

Table of Contents

1. Introduction
2. What Are Reductions in Complexity Theory?
3. Classical vs Quantum Reductions
4. Types of Quantum Reductions
5. Turing Reductions in Quantum Settings
6. Many-One Quantum Reductions
7. Oracle Reductions and Relativized Worlds
8. Reductions and Quantum Hardness Amplification
9. Reductions in Quantum Cryptography
10. Quantum Reductions and QMA-Completeness
11. Local Hamiltonian Problem and Reductions
12. Reductions in Quantum Interactive Proofs
13. Adiabatic Reductions and Problem Encodings
14. Quantum Reductions to Black-Box Problems
15. Promise Problems and Reductions
16. Quantum Reductions and Query Complexity
17. Role in Proving Quantum Advantage
18. Open Problems and Separations
19. Limitations and Caveats
20. Conclusion

1. Introduction

Quantum reductions are theoretical tools used to relate the hardness of problems in quantum computing. Like classical reductions, they show that solving one problem efficiently implies an efficient solution to another, helping us classify the relative difficulty of quantum problems.

2. What Are Reductions in Complexity Theory?

In classical theory, reductions transform instances of one problem into instances of another, preserving properties like solvability. They are essential for completeness results and hardness classification.

3. Classical vs Quantum Reductions

Quantum reductions differ in allowing quantum queries, superposition access, and unitary transformations. They extend classical notions but face constraints from measurement collapse, reversibility, and unitarity.

4. Types of Quantum Reductions

Types include:

• Many-one reductions: single-shot transformation
• Turing reductions: adaptive queries
• Non-adaptive reductions: parallel queries
• Black-box reductions: access via oracle
  Each serves different purposes in quantum complexity.

5. Turing Reductions in Quantum Settings

Quantum Turing reductions allow adaptive access to an oracle or subroutine. These are used in defining classes like BQP^A (BQP with oracle A), capturing relativized quantum power.

6. Many-One Quantum Reductions

Quantum many-one reductions transform inputs via quantum circuits. They are used to define QMA-complete problems, ensuring hardness of the target problem under efficient unitary transformations.

7. Oracle Reductions and Relativized Worlds

Oracle reductions help separate classes like BQP and PH (Polynomial Hierarchy). Quantum oracle constructions test class inclusions and simulate adversarial access to external knowledge.

8. Reductions and Quantum Hardness Amplification

Reductions amplify hardness by mapping easy instances to hard ones. They are useful in cryptography and average-case complexity, transforming weak problems into robust hard instances.

9. Reductions in Quantum Cryptography

Quantum-secure reductions prove that breaking a cryptosystem implies solving a quantum-hard problem. For example, reductions show that breaking lattice-based schemes implies solving LWE, which is believed hard for quantum adversaries.

10. Quantum Reductions and QMA-Completeness

Reductions are central to QMA-completeness. The Local Hamiltonian problem is QMA-complete via quantum many-one reductions, showing its role as the quantum analog of SAT.

11. Local Hamiltonian Problem and Reductions

Reductions to Local Hamiltonian variants (e.g., 2-local, 5-local) help establish completeness. Encodings involve mapping circuits to ground states, preserving accept/reject structure via spectral gaps.

12. Reductions in Quantum Interactive Proofs

In classes like QIP and QIP(2), reductions structure transformations between interactive verification protocols. They define equivalence classes of quantum-verifiable problems.

13. Adiabatic Reductions and Problem Encodings

Adiabatic computation maps problems to Hamiltonian ground states. Reductions encode computational histories into physical systems, showing equivalence to standard quantum computation.

14. Quantum Reductions to Black-Box Problems

Some reductions treat oracle functions as black boxes, enabling lower-bound proofs. Reductions to Grover’s or Simon’s problem capture quantum search and hidden subgroup hardness.

15. Promise Problems and Reductions

Many quantum problems are promise problems. Reductions must preserve promise validity—mapping yes/no instances without producing invalid queries or ambiguity.

16. Quantum Reductions and Query Complexity

In query models, reductions help bound the number of quantum oracle queries needed to solve problems. Adversary methods and span programs derive such bounds from reduction principles.

17. Role in Proving Quantum Advantage

Quantum reductions help establish separation results like BQP vs PH. They formalize evidence for quantum advantage by showing that no efficient classical reduction can simulate the quantum process.

18. Open Problems and Separations

Open questions include:

• Quantum analogs of NP-complete reductions
• Reductions between quantum learning tasks
• Hardness preservation in noisy and hybrid models

19. Limitations and Caveats

Quantum reductions face issues like:

• Measurement collapse
• Irreversibility in intermediate steps
• Unitarity constraints
  These limit how some classical reductions can be translated.

20. Conclusion

Quantum reductions are essential for organizing quantum complexity theory. They define completeness, classify hardness, and connect cryptographic and physical problems through rigorous transformations.

Table of Contents

1. Introduction
2. Classical Computability: A Brief Review
3. What Is Quantum Computability?
4. Quantum Turing Machines (QTMs)
5. Relationship to Church-Turing Thesis
6. Quantum Extensions of Recursive Functions
7. Quantum Decidability and Semidecidability
8. Halting Problem for Quantum Turing Machines
9. Measurement and Unitarity Constraints
10. Quantum Algorithms vs Quantum Computability
11. BQP and Effective Quantum Computation
12. Oracle Quantum Machines
13. Probabilistic Computation and Quantum Analogs
14. Quantum Automata and Computability
15. Limitations of Quantum Computability
16. Quantum Analogs of the Arithmetical Hierarchy
17. Quantum Diagonalization Techniques
18. Non-Deterministic Quantum Computability
19. Physical Church-Turing Thesis and Quantum Theory
20. Conclusion

1. Introduction

Quantum computability theory explores the fundamental question of what quantum computers can compute—beyond questions of efficiency or resource bounds. It extends classical computability into the quantum domain, examining limits, models, and decision problems under quantum rules.

2. Classical Computability: A Brief Review

Classical computability theory deals with what functions can be computed by a Turing machine. Core concepts include recursive functions, decidability, semidecidability, the halting problem, and the Church-Turing thesis.

3. What Is Quantum Computability?

Quantum computability seeks to define computable functions using quantum mechanical operations. It includes models like quantum Turing machines and examines whether the introduction of quantum rules changes the boundaries of computability.

4. Quantum Turing Machines (QTMs)

Proposed by Deutsch, a QTM generalizes classical Turing machines to include quantum state transitions and unitary evolution. It serves as a theoretical model to study quantum computability akin to the classical TM.

5. Relationship to Church-Turing Thesis

The (classical) Church-Turing thesis posits that any effectively computable function can be computed by a Turing machine. A “Quantum Church-Turing Thesis” considers whether quantum models can compute more than classical ones.

6. Quantum Extensions of Recursive Functions

Attempts have been made to define quantum analogs of primitive recursive and general recursive functions using quantum gates and quantum recursion theory, often embedding unitarity constraints.

7. Quantum Decidability and Semidecidability

Some problems may be quantum-decidable (resolvable by a quantum procedure) even if not classically decidable. However, in most known formulations, the class of quantum computable functions matches the classical set.

8. Halting Problem for Quantum Turing Machines

The halting problem remains undecidable in quantum models. However, quantum superposition complicates halting definitions: does the machine halt on all branches, some branches, or in an entangled state?

9. Measurement and Unitarity Constraints

Quantum computability must address issues of:

• Irreversible measurement
• No-cloning
• Preservation of norm
  These impose fundamental limits on how classical computation maps into quantum regimes.

10. Quantum Algorithms vs Quantum Computability

Quantum algorithms like Shor’s or Grover’s solve problems faster—but not necessarily different problems. They lie within BQP, which is contained within the class of computable functions.

11. BQP and Effective Quantum Computation

BQP is the class of decision problems solvable by a quantum computer in polynomial time with bounded error. All BQP problems are classically computable, hence do not expand the set of computable functions.

12. Oracle Quantum Machines

Adding oracles to QTMs defines relativized quantum computability. Oracle access can change complexity but typically does not alter computability unless oracles are uncomputable themselves.

13. Probabilistic Computation and Quantum Analogs

Quantum computation extends probabilistic computation by allowing interference. However, the set of quantum-computable functions coincides with the set of functions computable by probabilistic Turing machines with arbitrary accuracy.

14. Quantum Automata and Computability

Quantum finite automata (QFA) are weaker than classical Turing machines. They recognize only a proper subset of regular languages, showing that adding quantum rules to weak machines doesn’t enhance computability.

15. Limitations of Quantum Computability

Quantum models cannot compute the uncomputable. Problems like the halting problem, truth in arithmetic, or general first-order theorem proving remain undecidable in the quantum realm.

16. Quantum Analogs of the Arithmetical Hierarchy

Explorations into analogs of classical hierarchies (Σ₁, Π₁, etc.) have begun. These efforts aim to build quantum complexity versions of undecidable problems and the degrees of uncomputability.

17. Quantum Diagonalization Techniques

Diagonalization—a key classical tool—faces challenges in quantum theory due to linearity and no-cloning. Some restricted diagonalization methods exist, but generalizations are still under development.

18. Non-Deterministic Quantum Computability

Non-deterministic computation in quantum theory doesn’t behave like classical NP. Quantum parallelism offers superpositions, but accepting paths must be carefully defined to avoid ambiguity and collapse.

19. Physical Church-Turing Thesis and Quantum Theory

The Physical Church-Turing Thesis claims that no physical device can compute more than a Turing machine. Quantum theory doesn’t disprove this thesis—though it challenges its efficiency assumptions.

20. Conclusion

Quantum computability preserves the boundary of what is computable, matching classical Turing computability in scope. Its key contribution lies in redefining computation’s efficiency and nature, not its ultimate limits.