Quantum Computing and Automata

RSA encryption rests on the fact that factoring a 2048-bit integer takes 10^15 years. Shor's algorithm on a quantum computer would do it in hours. In 2024 NIST standardized post-quantum algorithms. The cryptographic migration is already underway.

• NIST 2024: CRYSTALS-Kyber and CRYSTALS-Dilithium are the first post-quantum cryptography standards
• Google Sycamore (2019): random circuit sampling, the first demonstration of quantum supremacy
• IBM Quantum: cloud access to quantum processors, used for chemical reaction simulation
• Hype cycle: the real payoff of NISQ today is molecular simulation for pharma and materials

Quantum Finite Automata

A quantum finite automaton (QFA) generalizes the DFA: instead of a single state, the machine is in a superposition of states. Transitions are unitary matrices (reversible transformations of amplitudes). Measurement projects the superposition onto a classical state.

A QFA is strictly more powerful than a DFA in terms of state count: the language {a^p : p prime} requires exponentially many states in a DFA but only O(log p) qubits in a QFA. However, a QFA is not more powerful than a DFA in terms of recognized languages, only in efficiency.

Quantum Turing Machine and BQP

A quantum Turing machine (QTM) generalizes the TM: the transition function produces a superposition of configurations. The class BQP (Bounded-error Quantum Polynomial time) contains problems solvable by a QTM in polynomial time with error probability at most 1/3.

• P ⊆ BQP ⊆ PSPACE: quantum computation sits between P and PSPACE
• Shor's algorithm: factoring in O((log N)^3). NP is not broken, but PKI is in danger
• Grover's algorithm: quadratic search speedup; it does not break NP-completeness
• BQP vs NP: open problem. Most experts believe BQP does not contain NP-hard problems
• Quantum supremacy (Google Sycamore, 2019): a task with no practical use

BQP and Quantum Limits

BQP is the central class of quantum computability. The invariant: error at most 1/3 (amplifiable by repetition to 1/2^k). Relations to classical classes: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE.

Quantum Advantage: Reality vs Hype

Quantum supremacy is a demonstration that a quantum computer can solve a task no classical computer can finish in reasonable time. Google Sycamore (2019): sampling from a random circuit in 200 seconds, allegedly 10,000 years on a classical machine. IBM pushed back: 2.5 days on Summit.

• Current NISQ (Noisy Intermediate-Scale Quantum): around 1000 physical qubits without error correction
• A logical qubit needs roughly 1000 physical qubits for fault-tolerant computation
• Shor's algorithm for RSA-2048: about 4000 logical qubits, around 4 million physical
• IBM roadmap: 100k qubits by 2033, but error correction is not guaranteed
• Real-world payoff today: molecule simulation (Variational Quantum Eigensolver)

Key Takeaways

• A QFA is more powerful than a DFA in state count, but not in the class of recognized languages
• BQP is the quantum analogue of P: P ⊆ BQP ⊆ PSPACE; the relation to NP is unknown
• Shor factors in O((log N)^3); Grover speeds up search to O(sqrt(N))
• NISQ era: no error correction. Fault-tolerance is far off. Post-quantum cryptography matters now

Related Topics

Quantum computing connects to classical complexity theory and to cryptography:

• P and NP classes — BQP joins the complexity map: P ⊆ BQP ⊆ PSPACE, but BQP vs NP is open
• Randomized algorithms — BPP is the classical analogue of BQP with a coin; BQP is conjecturally strictly stronger
• Finite automata — QFA extends DFA with amplitudes, giving exponential compression in state count
• Cryptography — Shor's algorithm breaks RSA and ECC. Post-quantum standards came from NIST in 2024

Вопросы для размышления

• If BQP contains problems outside P, why does that not prove P ≠ NP?
• Why does Grover's quadratic speedup not make NP-complete problems polynomial?
• Which classical algorithms in TLS 1.3 need to change for post-quantum security?

Связанные уроки

• qc-01