Quantum Randomness and Nondeterminism

Abstract

Does the notion of a quantum randomized or nondeterministic algorithm make sense, and if so, does quantum randomness or nondeterminism add power? Although reasonable quantum random sources do not add computational power, the discussion of quantum randomness naturally leads to several definitions of the complexity of quantum states. Unlike classical string complexity, both deterministic and nondeterministic quantum state complexities are interesting. A notion of \emph{total quantum nondeterminism} is introduced for decision problems. This notion may be a proper extension of classical nondeterminism.

8 pages

Cited by in corpus (20)

• A new construction for a QMA complete 3-local Hamiltonian
• Quantum Proofs
• The Quantum PCP Conjecture
• Succinct quantum proofs for properties of finite groups
• Experimental demonstration of quantum advantage for NP verification with limited information
• Local Hamiltonians in Quantum Computation
• Improved Soundness for QMA with Multiple Provers
• Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap
• Quantum Certificate Verification: Single versus Multiple Quantum Certificates
• Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
• Computational Distinguishability of Quantum Channels
• Quantum Arthur-Merlin Games
• Turing-equivalent automata using a fixed-size quantum memory
• One-Sided Error QMA with Shared EPR Pairs -- A Simpler Proof
• Cosine series quantum sampling method with applications in signal and image processing
• The Power of Unentanglement
• Testing non-isometry is QMA-complete
• Quantum Weakly Nondeterministic Communication Complexity
• Quantum NP and a Quantum Hierarchy
• On the Complexity of Quantum Languages