Quantum Computation by Adiabatic Evolution
read the original abstract
We give a quantum algorithm for solving instances of the satisfiability problem, based on adiabatic evolution. The evolution of the quantum state is governed by a time-dependent Hamiltonian that interpolates between an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes the satisfying assignment. To ensure that the system evolves to the desired final ground state, the evolution time must be big enough. The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general. We give some special symmetric cases of the satisfiability problem where the symmetry allows us to estimate the gap and we show that, in these cases, our algorithm runs in polynomial time.
This paper has not been read by Pith yet.
Forward citations
Cited by 39 Pith papers
-
A Quantum Approximate Optimization Algorithm
A p-layer alternating-operator ansatz on n qubits yields approximation ratios that increase with p, achieving ≥0.6924 for MaxCut on 3-regular graphs at p=1 and approaching 1 in the p→∞ adiabatic limit.
-
Quantum Glassiness From Efficient Learning
Efficient learning algorithms for energy estimation imply that stable quantum algorithms cannot prepare low-energy states in systems exhibiting the quantum overlap gap property, as proven for a sparsified quantum p-sp...
-
Multivariate Decoded Quantum Interferometry for Weighted Optimization
The work develops multivariate DQI states for weighted Max-LINSAT over prime fields, derives closed-form asymptotic expressions for expectation values and concentration, provides an explicit single-decoder preparation...
-
Multivariate Decoded Quantum Interferometry for Weighted Optimization
Multivariate DQI uses N-variable polynomials for weighted Max-LINSAT, derives closed-form asymptotics for expectation and concentration, provides a single-decoder preparation circuit, and shows outperformance over wei...
-
Breaking QAOA's Fixed Target Hamiltonian Barrier: A Fully Connected Quantum Boltzmann Machine via Bilevel Optimization
A bilevel optimization method turns QAOA into a fully connected QBM that achieves 0.9559 target state probability noiseless and retains top probability under realistic noise levels.
-
Q3SAT-GPT: A Generative Model for Discovering Quantum Circuits for the 3-SAT Problem
A generative model learns patterns from adaptive QAOA circuits to generate high-quality shallow quantum circuits for Max-E3-SAT that scale better than variational baselines.
-
QAOA Parameter Transfer for Hypergraphs
Analytical reweighting rules for QAOA parameters on hypergraphs improve performance by adjusting mixing terms beyond previous graph-based methods.
-
Beyond Single Trajectories: Optimal Control and Jordan-Lie Algebra in Hybrid Quantum Walks for Combinatorial Optimization
Hybrid quantum walks with optimal dynamical coin operators outperform QAOA on Max-Cut and MIS by accessing a strictly larger Jordan-Lie algebra that enables faster convergence and higher accuracy.
-
Exhaustive and feasible parametrisation with applications to the travelling salesperson problem
Exhaustively parametrised feasibility-respecting quantum circuits can reach every feasible solution to problems like TSP with certainty using fixed parameters by leveraging group actions and generating sequences.
-
Constrained Quantum Optimization meets Model Reduction
A projection-based model reduction enables exponential state-space reduction for constrained quantum optimization applied to random 3-SAT and agent coordination on graphs.
-
Multi-Mode Quantum Annealing for Generative Representation Learning with Boltzmann Priors
A multi-mode quantum annealing approach enables VAEs with Boltzmann priors, showing faster training and better generation than Gaussian-prior VAEs on MNIST, Fashion-MNIST, and CelebA plus improved out-of-distribution ...
-
Phase Estimation with Compressed Controlled Time Evolution
A compression protocol for controlled time evolution of local translationally invariant Hamiltonians achieves O(t polylog(t N/ε)) circuit depth with additive control overhead, demonstrated via 414 CNOT gates for itera...
-
Cobble: Compiling Block Encodings for Quantum Computational Linear Algebra
Cobble is a domain-specific language for quantum block encodings that compiles high-level matrix expressions to optimized circuits using analyses and quantum singular value transformation, achieving 2.6x-25.4x speedup...
-
Magnetic Hysteresis Experiments Performed on Quantum Annealers
The paper introduces the first general protocol for magnetic hysteresis on programmable quantum annealers and reports non-monotonic dependence of loop area on quantum fluctuations along with disorder-induced steps.
-
The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
The paper decomposes dynamical Lie algebras of XY-mixer topologies and demonstrates warm-starting QAOA via pre-training on restricted generators to improve convergence on constrained optimization problems.
-
Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives
Product-State Lifting (PSL) upgrades any basis-state vQSDP to k-degree polynomial optimization via product-register encoding, with linear resource scaling and k-independent constraints.
-
Proof of avoidability of the quantum first-order transition in transverse magnetization in quantum annealing of finite-dimensional spin glasses
Rigorous proof that appropriate quantum annealing avoids quantum first-order transitions in transverse magnetization for all finite-dimensional spin systems.
-
Controlled Gate Networks: Theory and Application to Eigenvalue Estimation
Controlled gate networks reduce two-qubit gate counts for linear combinations of unitary operators in quantum circuits, shown in variational calculations, rodeo eigenvalue estimation, and lattice nucleon evolution on ...
-
Adiabatic Quantum Phase Estimation
An adiabatic protocol for quantum phase estimation that reaches optimal scaling T = O(1/ε log(1/δ)) by encoding eigenvalues in computational basis populations rather than phases.
-
Quantum circuit design via dynamic Pauli constraints
Defines a Pauli-constraint model of quantum circuits proven equivalent to coupling-graph-restricted circuits, universal for BQP with O(D² N log N) overhead.
-
Near-Optimal Quantum Time Evolution Circuits via Provably Convergent Compression
A recipe for initial points in variational compression of quantum time-evolution operators that provably converges to near-optimal O(N t polylog(N t/ε)) gate complexity for local translationally invariant Hamiltonians.
-
Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms
Engineered local Hamiltonian controls in Rydberg arrays accelerate adiabatic convergence to MIS solutions, raise success probabilities over global controls, and cut fidelity decay rate by 25% as graphs harden.
-
Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms
Local degree-dependent controls in Rydberg adiabatic MIS algorithms accelerate convergence and reduce fidelity decay by 25% compared to global controls in numerical simulations.
-
Quantum End-to-End Learning for Contextual Combinatorial Optimization
QEL is the first quantum end-to-end learning framework for contextual combinatorial optimization using QAOA with a context re-uploading phase-separator, achieving competitive performance with fewer parameters.
-
CVaR-Assisted Custom Penalty Function for Constrained Optimization
A nonlinear custom penalty without slack variables plus CVaR sampling improves optimality gaps and consistency on knapsack instances for quantum constrained optimization.
-
Hybrid Real-Imaginary Time Evolution for Low-Depth Hamiltonian Simulation in Quantum Optimization
HAVQDS achieves higher approximation ratios on 6-14 qubit SK instances than adiabatic or CD methods while cutting CNOT counts by 1-2 orders of magnitude.
-
Quantum algorithms for equational reasoning
Presents a quantum Hamiltonian whose ground state encodes equivalence classes of expressions, enabling verification, counting, and structural queries on instances far beyond classical reach.
-
Quantum dynamics of two $XX$ interacting PT-symmetric non-Hermitian qubits: enhancement of quantum annealing
Tiny PT-symmetric non-Hermitian terms added to two XX-coupled qubits increase the success probability of reaching the ground state in quantum annealing.
-
Reducibility of native weighted graphs on Rydberg Arrays
Classical kernelisation fully reduces many small and sparse unit-disk graphs for MIS and MWIS native to Rydberg arrays, but dense graphs retain finite irreducible kernels, with vertex weights increasing reducibility a...
-
Large-Scale Quantum Circuit Simulation on an Exascale System for QPU Benchmarking
Exascale classical simulation validates noise-tolerant performance of a 98-qubit QPU up to 48 qubits for LR-QAOA, with statistical analysis showing coherent regime up to 93 qubits before outputs become indistinguishab...
-
No quantum advantage implies improved bounds and classical algorithms for the binary paint shop problem
Absence of quantum advantage for log-depth QAOA on the binary paint shop problem implies a classical mean-field algorithm achieving a paint-swap ratio of approximately 0.2799, outperforming known heuristics and quantu...
-
Multi-tasking through quantum annealing
MTQA embeds multiple NP-hard problems such as minimum vertex cover and graph partitioning into spatially distinct regions on quantum hardware, delivering comparable solution quality to single-task annealing with reduc...
-
Engineered Robustness for Nonadiabatic Geometric Quantum Gates
A streamlined framework for nonadiabatic geometric quantum gates on superconducting qubits achieves O(ε^4) infidelity scaling against Rabi amplitude errors, outperforming conventional dynamical gates.
-
Phase-Sensitive Measurements on a Fermi-Hubbard Quantum Processor
Hardware-efficient protocol for measuring complex Loschmidt echoes in a Fermi-Hubbard optical-lattice processor via quench dynamics and tailored imaginary-time pulses.
-
Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
Optimization-free Recursive QAOA solves the Binary Paint Shop Problem near-optimally with reduced quantum resources and robustness to parameter choice compared to standard QAOA.
-
Benchmarking quantum trial wavefunctions for phaseless auxiliary-field quantum Monte Carlo
Adaptive quantum ansatze outperform fixed UCCSD in ph-AFQMC projected energies for stretched H chains while using more compact circuits.
-
Quantum speed-up for solving the one-dimensional Hubbard model using quantum annealing
Classical simulation of quantum annealing for the 1D Hubbard model up to 40 qubits reports substantial speed-up over Bethe-ansatz methods for half-filled cases.
-
Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut
Light cone cancellation decomposes VQE circuits for Max-Cut into smaller subcircuits, yielding higher approximation ratios on simulated noisy backends up to 100 qubits compared to standard VQE.
-
The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
A synthesis of expert insights from the ADAC Quantum Computing Working Group and member survey on the complementary roles of quantum and classical high-performance computing in future hybrid infrastructures.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.