Table of Contents
- Introduction
- Classical Computability: A Brief Review
- What Is Quantum Computability?
- Quantum Turing Machines (QTMs)
- Relationship to Church-Turing Thesis
- Quantum Extensions of Recursive Functions
- Quantum Decidability and Semidecidability
- Halting Problem for Quantum Turing Machines
- Measurement and Unitarity Constraints
- Quantum Algorithms vs Quantum Computability
- BQP and Effective Quantum Computation
- Oracle Quantum Machines
- Probabilistic Computation and Quantum Analogs
- Quantum Automata and Computability
- Limitations of Quantum Computability
- Quantum Analogs of the Arithmetical Hierarchy
- Quantum Diagonalization Techniques
- Non-Deterministic Quantum Computability
- Physical Church-Turing Thesis and Quantum Theory
- 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.
