Optimizing QUBO on a quantum computer by mimicking imaginary time evolution

• URL: http://arxiv.org/abs/2505.22924v2
• Date: Wed, 18 Jun 2025 16:10:05 GMT
• Title: Optimizing QUBO on a quantum computer by mimicking imaginary time evolution
• Authors: Yahui Chai, Alice Di Tucci,
• Abstract summary: We propose a hybrid quantum-classical algorithm for solving QUBO problems using an Imaginary Time Evolution-Mimicking Circuit (ITEMC)<n>The circuit parameters are optimized to closely mimic imaginary time evolution, using only single- and two-qubit expectation values.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a hybrid quantum-classical algorithm for solving QUBO problems using an Imaginary Time Evolution-Mimicking Circuit (ITEMC). The circuit parameters are optimized to closely mimic imaginary time evolution, using only single- and two-qubit expectation values. This significantly reduces the measurement overhead by avoiding full energy evaluation. By updating the initial state based on results from last step iteratively, the algorithm quickly converges to the low-energy solutions. With a pre-sorting step that optimizes quantum gate ordering based on QUBO coefficients, the convergence is further improved. Our classical simulations achieve approximation ratios above 0.99 up to 150 qubits. Furthermore, the linear scaling of entanglement entropy with system size suggests that the circuit is challenging to simulate classically using tensor networks. We also demonstrate hardware runs on IBM's device for 40, 60, and 80 qubits, and obtain solutions compatible with that from simulated annealing.

Related papers

• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Fast Convex Optimization with Quantum Gradient Methods [2.5094874597551913]
  We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles.<n>We demonstrate the first dimension-independent query complexities for zeroth-order convex optimization in both smooth and nonsmooth settings.<n>By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games.
  arXiv  Detail & Related papers  (2025-03-21T17:58:12Z)
• Large-scale quantum annealing simulation with tensor networks and belief propagation [0.0]
  We show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000qubit gates. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. For degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states.
  arXiv  Detail & Related papers  (2024-09-18T18:00:08Z)
• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI)<n>For approximating to data over finite fields, DQI achieves a better approximation ratio than any time known to us.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Light Cone Cancellation for Variational Quantum Eigensolver Ansatz [3.1347083354427707]
  Variational Quantum Algorithms (VQAs) represent a class of algorithms that utilize a hybrid approach.<n>In this study, we apply a method known as Light Cone Cancellation (LCC) to optimize circuit variational circuits.<n>LCC yields higher approximation ratios than those cases without LCC.
  arXiv  Detail & Related papers  (2024-04-30T12:31:03Z)
• Nonlinear dynamics as a ground-state solution on quantum computers [39.58317527488534]
  We present variational quantum algorithms (VQAs) that encode both space and time in qubit registers. The spacetime encoding enables us to obtain the entire time evolution from a single ground-state computation.
  arXiv  Detail & Related papers  (2024-03-25T14:06:18Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  We present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding. We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms.
  arXiv  Detail & Related papers  (2023-05-23T16:17:57Z)
• Approximate Quantum Compiling for Quantum Simulation: A Tensor Network based approach [1.237454174824584]
  We introduce AQCtensor, a novel algorithm to produce short-depth quantum circuits from Matrix Product States (MPS)<n>Our approach is specifically tailored to the preparation of quantum states generated from the time evolution of quantum many-body Hamiltonians.<n>For simulation problems on 100 qubits, we show that AQCtensor achieves at least an order of magnitude reduction in the depth of the resulting optimized circuit.
  arXiv  Detail & Related papers  (2023-01-20T14:40:29Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)

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.