Quantum Optimization

Optimizing delivery routes for 50 cities takes hours on classical machines. Configuring a 200-atom protein molecule: a classical computer will never manage. Quantum computers promise to attack these problems in a fundamentally different way, through the physics of superposition and tunneling. What is reality, and what is hype?

• **Volkswagen and D-Wave**: traffic optimization in Lisbon for 1000+ buses via QUBO on D-Wave, quantum annealing found solutions in seconds comparable to SOTA classical methods
• **IBM Quantum for chemistry**: VQE for energy calculation of the FeMoco molecule (iron-molybdenum cofactor of nitrogenase), understanding this protein could revolutionize fertilizer production
• **Google Sycamore**: in 2023 demonstrated quantum advantage in Random Circuit Sampling: the first empirically confirmed example, though not a practical problem

QAOA: Hybrid Quantum-Classical Algorithm

**QAOA** (Quantum Approximate Optimization Algorithm, Farhi et al. 2014) is an algorithm for solving combinatorial optimization problems on NISQ (Noisy Intermediate-Scale Quantum) computers. The idea: encode the problem in a Hamiltonian H_C, alternate quantum evolutions by H_C and H_B, and optimize the parameters (γ, β) classically.

QAOA is a **variational** algorithm: we parametrize a family of quantum states and optimize the parameters. This is a hybrid architecture: the quantum computer prepares a state and measures the expectation value; the classical optimizer (Nelder-Mead, SPSA, gradient-based) updates parameters (γ, β). This approach is called VQA, Variational Quantum Algorithm.

**Barren plateau**: a core problem: for random parameter initializations in deep VQAs, the gradient is exponentially small in the number of qubits n. Expected gradient: E[∂C/∂θ] = 0, variance ∝ 2⁻ⁿ. Gradient descent becomes a random walk. This is the vanishing gradient analogue for quantum circuits. Solutions: local initialization, structured ansatz design, graduated learning.

VQE: Ground State Search via the Variational Principle

**VQE** (Variational Quantum Eigensolver, Peruzzo et al. 2014) is a hybrid quantum-classical algorithm for finding the minimum eigenvalue (ground state) of a Hamiltonian. The main application is quantum chemistry: a molecule's energy equals the minimum eigenvalue of its molecular Hamiltonian. This is exponentially hard on classical computers; VQE uses a quantum computer to evaluate the energy.

For a molecule with N orbitals, the Hilbert space has dimension 2^N. Exact classical diagonalization requires O(4^N) operations, for N=50 that is 10^30 operations, unattainable. VQE uses a quantum computer with N qubits, estimating E(θ) in O(poly(N)) quantum operations. The central question: how expressive is the ansatz? If it cannot represent the true ground state, VQE finds only a local minimum within the ansatz family.

Quantum Annealing: D-Wave and Tunneling

**Quantum Annealing (QA)** is a physically different approach to optimization. Instead of gate-based quantum computation, the system physically implements the problem Hamiltonian in superconducting qubits. The system evolves from a simple initial Hamiltonian to the problem Hamiltonian, using **quantum tunneling** to cross energy barriers.

QUBO (Quadratic Unconstrained Binary Optimization): min x^T Q x, x ∈ {0,1}^n. This is the standard format for D-Wave. QUBO can encode: Max-Cut, TSP, portfolio optimization, protein folding, logistics problems. Constraints are added as penalties: Ax = b → +λ‖Ax-b‖² in the objective. The complexity of embedding a problem into the D-Wave graph is often NP-hard itself (minor embedding problem).

When Quantum Optimization Wins

The central question of quantum computation for optimization: is there a **quantum advantage**: problems where a quantum algorithm is exponentially or polynomially faster than the best classical? The answer depends on the problem type, complexity class, and the maturity of the technology.

The honest answer for 2026: **quantum optimization is the future, but not yet the present** for most practical problems. NISQ devices are too noisy for the circuit depths needed for real problems. That said, VQE already delivers results in quantum chemistry beyond classical reach. The field is rapidly evolving: Google, IBM and IonQ are competing for the fault-tolerant milestone.

Key Ideas

• **QAOA**: hybrid algorithm, quantum computer evaluates ⟨H_C⟩, classical computer optimizes parameters (γ,β); for Max-Cut and other QUBO problems
• **VQE**: variational principle on a quantum computer for the Hamiltonian ground state; primary application, quantum chemistry
• **Quantum Annealing (D-Wave)**: physical analog evolution via tunneling; specialized hardware for Ising/QUBO problems
• **Quantum advantage** for optimization is still an open question; in 2026 NISQ is limited to small problems; fault-tolerant QC ~2030+

Related Topics

Quantum optimization bridges quantum physics with classical complexity theory:

• Bayesian Optimization — QAOA parameters (γ,β) are optimized classically including with BO, the objective landscape is often smooth
• Theoretical Convergence Guarantees — The adiabatic theorem gives QA convergence conditions; barren plateaus are the QAOA analogue of poor conditioning
• Optimization on Manifolds — VQE/QAOA parameters live on the manifold of unitary operators U(2^n); natural gradient on this manifold = quantum Fisher information

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

• Why are barren plateaus a more fundamental problem for VQAs than NISQ device noise?
• Which complexity class (NP-hard, BQP, NP-complete) can quantum computers solve in polynomial time according to current theoretical knowledge?
• How can one verify that D-Wave genuinely uses quantum tunneling rather than just a fast classical annealer?

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

• la-33-la-in-qm