Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing

• URL: http://arxiv.org/abs/2105.02110v2
• Date: Tue, 26 Apr 2022 23:03:53 GMT
• Title: Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing
• Authors: Vicky Choi
• Abstract summary: A non-stoquastic Hamiltonian can be stoquastic or properly non-stoquastic when its ground state has both positive and negative amplitudes. We show how to design an appropriate XX-driver graph with an appropriate XX-coupler strength without knowing the prior problem structure. The speedup is exponential in the original AC-distance, which can be sub-exponential or exponential in the system size.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the distinct features of quantum mechanics is that the probability amplitude can have both positive and negative signs, which has no classical counterpart as the classical probability must be positive. Consequently, one possible way to achieve quantum speedup is to explicitly harness this feature. Unlike a stoquastic Hamiltonian whose ground state has only positive amplitudes (with respect to the computational basis), a non-stoquastic Hamiltonian can be eventually stoquastic or properly non-stoquastic when its ground state has both positive and negative amplitudes. In this paper, we describe that, for some hard instances which are characterized by the presence of an anti-crossing (AC) in a transverse-field quantum annealing (QA) algorithm, how to design an appropriate XX-driver graph (without knowing the prior problem structure) with an appropriate XX-coupler strength such that the resulting non-stoquastic QA algorithm is proper-non-stoquastic with two bridged anti-crossings (a double-AC) where the spectral gap between the first and second level is large enough such that the system can be operated diabatically in polynomial time. The speedup is exponential in the original AC-distance, which can be sub-exponential or exponential in the system size, over the stoquastic QA algorithm, and possibly the same order of speedup over the state-of-the-art classical algorithms in optimization. This work is developed based on the novel characterizations of a modified and generalized parametrization definition of an anti-crossing in the context of quantum optimization annealing introduced in [4].

Related papers

• Quantum Detection of Sequency-Band Structure [0.5729426778193398]
  We present a quantum algorithm for estimating the amplitude content of user-specified sequency bands in quantum-encoded signals.<n>The method employs a sequency-ordered Quantum Walsh-Hadamard Transform (QWHT), a comparator-based oracle that coherently marks basis states within an arbitrary sequency range.<n>This enables the detection of structured signal components, including both high- and low-sequency features, as well as the identification of rapid sign-change behavior associated with noise or anomalies.
  arXiv  Detail & Related papers  (2026-02-09T08:47:51Z)
• A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization [39.146761527401424]
  This work presents a rigorous worst-case runtime analysis of a measurement-driven quantum SAT solver.<n>We show that this quantum algorithm does not exclusively rely on Grover-type methods and shows promising numerical performance.<n>We also develop a new readout routine that efficiently finds a solution even for instances with multiple satisfying assignments.
  arXiv  Detail & Related papers  (2025-11-12T19:00:13Z)
• Quantum Random Feature Method for Solving Partial Differential Equations [36.58357595906332]
  Quantum computing holds promise for scientific computing due to its potential for exponential speedups over classical methods.<n>In this work, we introduce a quantum random method (QRFM) that leverages advantages from both numerical analysis and neural analysis.
  arXiv  Detail & Related papers  (2025-10-09T08:42:09Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Beyond Stoquasticity: Structural Steering and Interference in Quantum Optimization [0.0]
  We present a theoretical analysis of the DIC-DAC-DOA algorithm, a non-stoquastic quantum algorithm for solving the Independent Set (MIS) problem.<n>The core of this speedup lies in the ability of the evolving ground state to develop both positive and negative amplitudes, enabled by the non-stoquastic XX-driver.
  arXiv  Detail & Related papers  (2025-09-18T04:27:42Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians [0.0]
  ExcLQA is a classical, physics-inspired algorithm that identifies excited states of classical Ising Hamiltonians.<n>We benchmark ExcLQA on the shortest vector problem (SVP), a fundamental lattice problem underlying the security of many postquantum cryptographic schemes.<n>Our results show that ExcLQA manages to solve SVP instances up to rank 46, and outperforms the Metropolis-Hastings algorithm in solved ratio, number of shots, and approximation factor.
  arXiv  Detail & Related papers  (2025-07-16T16:40:49Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations. The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions. The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• Bayesian Quantum Amplitude Estimation [49.1574468325115]
  We introduce BAE, a noise-aware Bayesian algorithm for quantum amplitude estimation. We show that BAE achieves Heisenberg-limited estimation and benchmark it against other approaches.
  arXiv  Detail & Related papers  (2024-12-05T18:09:41Z)
• Schrödingerization based Quantum Circuits for Maxwell's Equation with time-dependent source terms [24.890270804373824]
  This paper explicitly constructs a quantum circuit for Maxwell's equations with perfect electric conductor (PEC) boundary conditions. We show that quantum algorithms constructed using Schr"odingerisation exhibit acceleration in computational complexity compared to the classical Finite Difference Time Domain (FDTD) format.
  arXiv  Detail & Related papers  (2024-11-17T08:15:37Z)
• Solving the homogeneous Bethe-Salpeter equation with a quantum annealer [34.173566188833156]
  The homogeneous Bethe-Salpeter equation (hBSE) was solved for the first time by using a D-Wave quantum annealer. A broad numerical analysis of the proposed algorithms was carried out using both the proprietary simulated-anneaing package and the D-Wave Advantage 4.1 system.
  arXiv  Detail & Related papers  (2024-06-26T18:12:53Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm [0.0]
  Two-stage programming is a problem formulation for decision-making under uncertainty. This work uses a quantum algorithm to estimate the expected value function with a speedup.
  arXiv  Detail & Related papers  (2024-02-23T00:07:34Z)
• Quadratic acceleration of multi-step probabilistic algorithms for state preparation [0.0]
  A non-unitary operator is typically designed to decay undesirable states contained in an initial state. Probabilistic algorithms do not accelerate the computational process compared to classical ones.
  arXiv  Detail & Related papers  (2023-08-07T14:07:03Z)
• Effectiveness of quantum annealing for continuous-variable optimization [0.0]
  We test the performance of quantum annealing applied to a one-dimensional continuous-variable function with a rugged energy landscape. We conclude that the hardware realization of quantum annealing has the potential to significantly outperform the best classical algorithms.
  arXiv  Detail & Related papers  (2023-05-11T07:59:19Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  An ideal state preparation protocol can be characterized by being easily generated classically. We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC) We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
  arXiv  Detail & Related papers  (2022-11-18T20:31:10Z)
• On optimization of coherent and incoherent controls for two-level quantum systems [77.34726150561087]
  This article considers some control problems for closed and open two-level quantum systems. The closed system's dynamics is governed by the Schr"odinger equation with coherent control. The open system's dynamics is governed by the Gorini-Kossakowski-Sudarshan-Lindblad master equation.
  arXiv  Detail & Related papers  (2022-05-05T09:08:03Z)
• Accelerated Convergence of Contracted Quantum Eigensolvers through a Quasi-Second-Order, Locally Parameterized Optimization [0.0]
  A contracted quantum eigensolver (CQE) finds a solution to the many-electron Schr"odinger equation on a quantum computer. In this work, we accelerate the convergence of the CQE and its wavefunction ansatz via tools from classical optimization theory.
  arXiv  Detail & Related papers  (2022-05-03T18:48:04Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Digitized-Counterdiabatic Quantum Optimization [4.336065967298193]
  We propose digitized-diabatic quantum optimization (DCQO) to achieve enhancement over adiabatic quantum optimization for the general Ising spin-glass model. This is accomplished via the digitization of adiabatic quantum algorithms that are catalysed by the addition of non-stoquastic counterdiabatic terms.
  arXiv  Detail & Related papers  (2022-01-03T18:21:54Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Stoquasticity in circuit QED [78.980148137396]
  We show that scalable sign-problem free path integral Monte Carlo simulations can typically be performed for such systems. We corroborate the recent finding that an effective, non-stoquastic qubit Hamiltonian can emerge in a system of capacitively coupled flux qubits.
  arXiv  Detail & Related papers  (2020-11-02T16:41:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.