QMA-Complete Problems: The Local Hamiltonian Family
QMA-complete problems such as the local Hamiltonian problem are the hardest problems in QMA. Their origin, proofs and applications.
BasicsAlgorithmsHardwareError CorrectionCryptographyMachine LearningInformation TheoryPhysics & SimulationApplicationsIndustry & Careers
Quantum Information Theory
Entropy, channel capacity, teleportation, complexity classes and the theorems that define what quantum information can and cannot do.
155 articles
Quantum Computational Efficiency: How It Is Measured
How quantum computational efficiency is measured: gate counts, circuit depth and speedup, and where parallelism and interference help.
QPCP: The Quantum PCP Conjecture, Explained
The quantum PCP conjecture asks whether quantum proofs can be checked by reading only a few qubits. Its forms, known results and open questions.
QAM: Quantum Arthur-Merlin Protocols
Quantum Arthur-Merlin protocols let a verifier check a prover with public random coins. The QAM class, its relations and applications.
QSZK: Quantum Statistical Zero Knowledge
QSZK is the class of quantum statistical zero-knowledge proofs. Its definition, relation to classical SZK and uses in cryptography.
QCMA: Classical Proofs, Quantum Verification
QCMA is like QMA but with a classical proof and a quantum verifier. Its origin, how it compares with QMA and what is known about the gap.
QIP: Quantum Interactive Proofs and QIP = PSPACE
QIP is the class of problems with quantum interactive proofs. Its definition, protocols and the 2010 result that QIP equals PSPACE.
QMA: Quantum Merlin-Arthur and Quantum NP
QMA is the quantum analogue of NP: a quantum verifier checks a quantum proof. Its definition, relation to NP and BQP, and complete problems.
BQP: The Complexity Class of Quantum Computers
BQP is the class of problems quantum computers solve in polynomial time with bounded error. How it relates to BPP, NP and quantum algorithms.
Quantum Communication Complexity, Explained
Quantum communication complexity asks how many qubits parties must exchange to compute a function. Protocols, complexity classes and applications.
Quantum Games and Strategies: Game Theory, Quantised
Quantum game theory adds superposition and entanglement to strategic games. How quantum strategies change outcomes in games such as the prisoner’s dilemma.
Quantum Channel Capacity: How Much Can Get Through
Quantum channel capacity measures how much information a noisy quantum channel can carry. Classical, quantum, private and entanglement-assisted capacities.
