# [SCI] Quantum Computing Theory

**Quantum Computing Theory** studies the computational power of systems governed by quantum mechanics — qubits, quantum gates, algorithms — and the fundamental question of whether quantum computers can efficiently solve problems intractable for classical machines.

## Overview

Feynman (1982) proposed quantum computers to simulate quantum systems. Deutsch (1985) defined the quantum circuit model. Shor's algorithm (1994) factors integers exponentially faster than any known classical algorithm, threatening RSA cryptography. Grover's algorithm (1996) gives a quadratic speedup for search. The quantum threshold theorem shows fault-tolerant quantum computation is possible with error rates below ~1% per gate. Quantum error correction codes (Shor 1995, Steane 1996, surface code) are the current frontier.

## Key Figures & Recognition

- **Peter Shor** (1959–): Shor's algorithm. Turing Award 1998, Nevanlinna Prize.
- **Lov Grover** (1961–): Grover search algorithm.
- **John Preskill** (1953–): Coined "quantum supremacy," quantum error correction.

## Seminal Papers

- [Shor, P. "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." *FOCS* (1994)](https://doi.org/10.1109/SFCS.1994.365700)
- [Grover, L. "A fast quantum mechanical algorithm for database search." *STOC* (1996)](https://arxiv.org/abs/quant-ph/9605043)
- [Preskill, J. "Quantum Computing in the NISQ Era and Beyond." *Quantum* 2 (2018)](https://arxiv.org/abs/1801.00862)

## What This Enables
⏎
- **[TECH] Quantum Computing Hardware** — Theoretical requirements — fault tolerance thresholds, qubit connectivity, gate fidelity targets — directly guide hardware roadmaps.
⏎
# Parents

* [SCI] Quantum Optics
* [SCI] Quantum Field Theory (QED/QCD)
* [SCI] Quantum Optics
* [SCI] Deep Learning⏎