Applications of Quantum Computing
Quantum chemistry, optimization, machine learning, and cryptography
6.1 Quantum Chemistry and Molecular Simulation
Quantum chemistry is widely considered the first "killer application" for quantum computers. The electronic structure problem -- finding the ground state of the molecular Hamiltonian -- is QMA-hard in general, but structured instances relevant to chemistry are believed to be efficiently solvable on quantum computers.
The Electronic Structure Problem
The molecular Hamiltonian in second quantization (Born-Oppenheimer approximation) is:
$$\hat{H} = \sum_{pq} h_{pq} \hat{a}_p^\dagger \hat{a}_q + \frac{1}{2}\sum_{pqrs} h_{pqrs} \hat{a}_p^\dagger \hat{a}_q^\dagger \hat{a}_r \hat{a}_s + E_{\text{nuc}}$$
where $h_{pq}$ and $h_{pqrs}$ are one- and two-electron integrals, and $\hat{a}_p^\dagger$, $\hat{a}_q$ are fermionic creation/annihilation operators. To simulate on a qubit-based quantum computer, we need a fermion-to-qubit mapping.
Fermion-to-Qubit Mappings
- Jordan-Wigner transformation:$\hat{a}_j^\dagger = \frac{1}{2}(X_j - iY_j) \prod_{k<j} Z_k$. Maps $N$ spin-orbitals to $N$ qubits. The Z-string enforces fermionic antisymmetry but creates non-local operators.
- Bravyi-Kitaev transformation:A more balanced encoding where both occupation and parity information are distributed logarithmically, reducing operator weight from $O(N)$ to $O(\log N)$.
- Parity mapping:Encodes parity instead of occupation numbers. Can reduce qubit count by 2 through symmetry reduction.
Quantum Advantage Timeline
- Now (NISQ): Small molecules (H2, LiH, BeH2) at chemical accuracy with VQE
- Near-term: Transition metal catalysts, reaction mechanisms (~50-100 logical qubits)
- Medium-term: Nitrogen fixation (FeMoco), drug-protein interactions (~200-500 logical qubits)
- Long-term: Full ab initio simulation of complex biochemical processes
The estimated resources for a classically intractable chemistry problem (e.g., FeMoco active site with 54 electrons in 54 orbitals): ~4,000 logical qubits and $\sim 10^{10}$ T gates using qubitization-based QPE.
6.2 Combinatorial Optimization
Many important optimization problems (scheduling, routing, portfolio optimization) are NP-hard. Quantum approaches offer potential advantages, though provable exponential speedups for NP-hard problems remain unlikely (unless NP is contained in BQP).
QUBO Formulation
Many optimization problems can be cast as Quadratic Unconstrained Binary Optimization (QUBO):
$$\min_{\vec{x} \in \{0,1\}^n} \vec{x}^T Q \vec{x} = \min_{\vec{z} \in \{-1,+1\}^n} \sum_{ij} J_{ij} z_i z_j + \sum_i h_i z_i$$
This maps directly to finding the ground state of an Ising Hamiltonian:
$$H_{\text{Ising}} = \sum_{ij} J_{ij} Z_i Z_j + \sum_i h_i Z_i$$
Quantum Approaches to Optimization
- QAOA: Parameterized circuit alternating cost and mixer unitaries. Depth $p$ controls the quality of approximation. Practical for moderate-size problems.
- Quantum Annealing: Adiabatically evolve from the ground state of $H_M$ to $H_C$. D-Wave implements this with 5000+ qubits, though demonstrating advantage over classical solvers remains challenging.
- Grover Adaptive Search (GAS): Use Grover's search to find solutions better than the current best, iteratively lowering the threshold. Gives quadratic speedup for any optimization problem.
- Quantum walks: Continuous-time or discrete-time quantum walks on solution graphs can provide speedups for specific problem structures.
Application Areas
- - Finance: Portfolio optimization, risk analysis, option pricing (Monte Carlo speedup)
- - Logistics: Vehicle routing, supply chain optimization, scheduling
- - Energy: Power grid optimization, battery material design
- - Telecom: Network optimization, resource allocation
6.3 Quantum Machine Learning
Quantum machine learning (QML) explores the intersection of quantum computing and machine learning. The landscape includes four quadrants:
CC: Classical data, Classical computer
Standard ML (TensorFlow, PyTorch)
CQ: Classical data, Quantum computer
Variational classifiers, quantum kernels
QC: Quantum data, Classical computer
Classical shadows, tensor networks
QQ: Quantum data, Quantum computer
Quantum state tomography, quantum error correction decoding
Variational Quantum Classifiers
A quantum classifier encodes input data $x$ into a quantum state via a feature map $U_\phi(x)$, then applies a trainable ansatz $U_W(\vec{\theta})$:
$$\hat{y} = f\left(\langle 0| U_W^\dagger(\vec{\theta})\, U_\phi^\dagger(x)\, M\, U_\phi(x)\, U_W(\vec{\theta})|0\rangle\right)$$
The parameters $\vec{\theta}$ are trained to minimize a classical loss function (e.g., cross-entropy). Open question: when and whether quantum classifiers outperform classical neural networks for practical datasets.
Quantum Speedups for ML Subroutines
- HHL for linear regression:Exponential speedup in $N$ (number of data points) under certain conditions. Caveats: data loading and output readout bottlenecks.
- Quantum PCA:Exponentially faster principal component analysis given quantum access to the data covariance matrix.
- Quantum sampling:Quantum Boltzmann machines may sample from distributions faster than classical MCMC, useful for generative modeling.
- Grover-enhanced training:Quadratic speedup for searching over model hyperparameters or data subsets.
Dequantization and Caveats
Ewin Tang's "dequantization" results (2019) showed that quantum-inspired classical algorithms can achieve similar (polynomial) speedups for some QML tasks (recommendation systems, PCA) when the data has low rank. This has tempered expectations for CQ-type quantum ML, shifting focus to problems where quantum structure is intrinsic (QQ quadrant).
6.4 Quantum Cryptography
The Quantum Threat to Classical Cryptography
Shor's algorithm threatens the security of widely-used public-key cryptosystems:
- RSA: Based on integer factoring -- broken by Shor's algorithm in polynomial time
- ECC (Elliptic Curve): Based on discrete logarithm -- broken by quantum period finding
- Diffie-Hellman: Based on discrete logarithm -- broken
- AES (symmetric): Grover gives quadratic speedup; doubling key length suffices (AES-256 remains safe)
Post-Quantum Cryptography (PQC)
NIST standardized the first post-quantum algorithms in 2024, designed to resist both classical and quantum attacks:
- ML-KEM (CRYSTALS-Kyber):Key encapsulation based on Module Learning with Errors (MLWE). Security relies on the hardness of structured lattice problems.
- ML-DSA (CRYSTALS-Dilithium):Digital signatures based on MLWE and Module-SIS.
- SLH-DSA (SPHINCS+):Hash-based signatures with minimal security assumptions. Conservative choice, larger signatures.
Quantum Key Distribution (QKD)
QKD uses quantum mechanics to distribute encryption keys with information-theoretic security -- security guaranteed by the laws of physics, not computational assumptions.
BB84 Protocol (Bennett & Brassard, 1984)
- Alice randomly encodes bits in one of two bases: rectilinear ($|0\rangle$, $|1\rangle$) or diagonal ($|+\rangle$, $|-\rangle$)
- Bob measures each qubit in a randomly chosen basis
- They publicly compare bases (not measurement results) and keep only matching-basis bits
- They sacrifice a subset to check for eavesdropping (elevated error rate indicates interception)
- Privacy amplification yields a shorter, secure key
Security relies on the no-cloning theorem: an eavesdropper (Eve) cannot copy the quantum states without disturbing them. Any interception attempt introduces detectable errors. The maximum tolerable error rate (QBER) is approximately 11% for BB84.
QKD Milestones
- - 2017: Micius satellite demonstrates 1,200 km QKD (China)
- - 2021: 4,600 km quantum-secured network (Beijing-Shanghai backbone)
- - 2024: Commercial QKD systems deployed in banking and government networks
6.5 Quantum Simulation of Physical Systems
Feynman's original vision: use quantum computers to simulate quantum systems that are exponentially hard to simulate classically. This remains one of the most promising near-term applications.
Hamiltonian Simulation
Given a Hamiltonian $H = \sum_j H_j$, simulate the time evolution $e^{-iHt}$. The Trotter-Suzuki decomposition approximates:
$$e^{-iHt} \approx \left(\prod_j e^{-iH_j t/r}\right)^r + O(t^2/r)$$
More advanced methods (qubitization, quantum signal processing) achieve optimal scaling $O(t \cdot \|H\| / \epsilon)$ for the simulation error $\epsilon$.
Target Applications
- Condensed matter: Hubbard model, frustrated magnets, topological phases, high-temperature superconductivity
- Nuclear and particle physics: Lattice gauge theory simulations, nuclear structure, scattering processes
- Materials science: Strongly correlated electron systems, catalysis mechanisms, battery materials
- Quantum field theory: Real-time dynamics inaccessible to classical lattice QCD methods
6.6 The Road Ahead
The quantum computing field is at an inflection point. Key milestones on the horizon:
Near-term (2025-2028)
- - Error rates below surface code threshold on 100+ qubits
- - First demonstrations of logical qubit operations with QEC advantage
- - Quantum utility demonstrations beyond classical reach using error mitigation
- - Practical quantum advantage for specific optimization or simulation instances
Medium-term (2028-2033)
- - 1,000+ logical qubits with full error correction
- - Practical quantum advantage for chemistry and materials simulation
- - Quantum-classical hybrid workflows in drug discovery and finance
- - Deployment of quantum-safe cryptography across critical infrastructure
Long-term (2033+)
- - Cryptographically relevant quantum computers (breaking RSA-2048)
- - Full-scale molecular simulation for drug design and catalyst discovery
- - Quantum machine learning with demonstrated exponential advantages
- - Quantum internet connecting quantum processors globally
"Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy." -- Richard Feynman, 1981