Recognition: unknown
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 14 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.
-
Decoded Quantum Interferometry for Weighted Optimization Problems
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...
-
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.
-
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.
-
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...
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.