Guided quantum walk

Abstract

We utilize the theory of local amplitude transfers (LAT) to gain insights into quantum walks (QWs) and quantum annealing (QA) beyond the adiabatic theorem. By representing the eigenspace of the problem Hamiltonian as a hypercube graph, we demonstrate that probability amplitude traverses the search space through a series of local Rabi oscillations. We argue that the amplitude movement can be systematically guided towards the ground state using a time-dependent hopping rate based solely on the problem's energy spectrum. Building upon these insights, we extend the concept of multi-stage QW by introducing the guided quantum walk (GQW) as a bridge between QW-like and QA-like procedures. We assess the performance of the GQW on exact cover, traveling salesperson and garden optimization problems with 9 to 30 qubits. Our results provide evidence for the existence of optimal annealing schedules, beyond the requirement of adiabatic time evolutions. These schedules might be capable of solving large-scale combinatorial optimization problems within evolution times that scale linearly in the problem size.

References in corpus (30)

• Quantum Computing in the NISQ era and beyond
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• The theory of variational hybrid quantum-classical algorithms
• Adiabatic Quantum Computing
• The Variational Quantum Eigensolver: a review of methods and best practices
• Spatial search by quantum walk
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Quantum Search by Local Adiabatic Evolution
• Quantum Boltzmann Machine
• Architectural considerations in the design of a superconducting quantum annealing processor
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• First order phase transition in the Quantum Adiabatic Algorithm
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
• Quantum search by measurement
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Finding spin-glass ground states using quantum walks
• An energetic perspective on rapid quenches in quantum annealing
• Schedule path optimization for quantum annealing and adiabatic quantum computing
• Garden optimization problems for benchmarking quantum annealers
• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
• Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
• Continuous-time quantum walks for MAX-CUT are hot
• On the hardness of quadratic unconstrained binary optimization problems

Cited by in corpus (9)

• Quantum algorithms for scientific computing
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Grover Speedup from Many Forms of the Zeno Effect
• Continuous-time quantum optimisation without the adiabatic principle
• Zeno-effect Computation: Opportunities and Challenges
• Discovery of energy landscapes towards optimized quantum transport: Environmental effects and long-range tunneling
• Improving success probability in the LHZ parity embedding by computing with quantum walks
• Resource-Efficient Quantum Optimization via Higher-Order Encoding
• Quantum annealing and condensed matter physics