Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo

• URL: http://arxiv.org/abs/2407.10205v1
• Date: Sun, 14 Jul 2024 13:51:35 GMT
• Title: Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
• Authors: Hao Wang, Zixuan Liu, Zhixin Xie, Langyu Li, Zibo Miao, Wei Cui, Yu Pan,
• Abstract summary: Ising annealer is a quantum-inspired computing architecture for optimization problems. Main innovation is the fusion of an approximate gradient-based approach into the Ising annealer. Prototype annealer solves Ising problems of both integer and fraction coefficients with up 200 spins on a single low-cost FPGA board.
• Score: 11.307633403964031
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ising annealer is a promising quantum-inspired computing architecture for combinatorial optimization problems. In this paper, we introduce an Ising annealer based on the Hamiltonian Monte Carlo, which updates the variables of all dimensions in parallel. The main innovation is the fusion of an approximate gradient-based approach into the Ising annealer which introduces significant acceleration and allows a portable and scalable implementation on the commercial FPGA. Comprehensive simulation and hardware experiments show that the proposed Ising annealer has promising performance and scalability on all types of benchmark problems when compared to other Ising annealers including the state-of-the-art hardware. In particular, we have built a prototype annealer which solves Ising problems of both integer and fraction coefficients with up to 200 spins on a single low-cost FPGA board, whose performance is demonstrated to be better than the state-of-the-art quantum hardware D-Wave 2000Q and similar to the expensive coherent Ising machine. The sub-linear scalability of the annealer signifies its potential in solving challenging combinatorial optimization problems and evaluating the advantage of quantum hardware.

Related papers

• Higher-Order Neuromorphic Ising Machines -- Autoencoders and Fowler-Nordheim Annealers are all you need for Scalability [6.455936422535347]
  We report a higher-order neuromorphic Ising machine that exhibits superior scalability compared to architectures based on quadratization.<n>Asymptotic convergence to the Ising ground state is ensured by sampling autoencoder latent space defined by the spins.<n>We show that the techniques based on the sparsity of the interconnection matrix, such as graph coloring, can be effectively applied to higher-order neuromorphic Ising machines.
  arXiv  Detail & Related papers  (2025-06-24T19:17:02Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks. We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings. We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers [0.4969640751053581]
  We show that p-computers can surpass state-of-the-art quantum annealers in solving hard optimization problems. We show that these algorithms are readily implementable in modern hardware thanks to the mature semiconductor technology. Our results raise the bar for a practical quantum advantage in optimization and present p-computers as scalable, energy-efficient hardware.
  arXiv  Detail & Related papers  (2025-03-13T12:24:13Z)
• MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
  Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling optimization challenges. The requisite circuit depth for satisfactory performance is problem-specific and often exceeds the maximum capability of current quantum devices. We introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians.
  arXiv  Detail & Related papers  (2024-09-27T12:28:18Z)
• Encoding arbitrary Ising Hamiltonians on Spatial Photonic Ising Machines [0.0]
  We introduce and experimentally validate a SPIM instance that enables direct control over the full interaction matrix. We demonstrate the conformity of the experimentally measured Ising energy with the theoretically expected values and then proceed to solve both the unweighted and weighted graph problems. Our approach greatly expands the applicability of SPIMs for real-world applications without sacrificing any of the inherent advantages of the system.
  arXiv  Detail & Related papers  (2024-07-12T10:54:07Z)
• Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems [0.0]
  We introduce a comprehensive quantum solver for binary optimization problems on gate-model quantum computers. It consistently delivers correct solutions for problems with up to 127 qubits. We benchmark this solver on IBM quantum computers for several classically nontrivial unconstrained binary optimization problems.
  arXiv  Detail & Related papers  (2024-06-03T19:08:01Z)
• Load Balancing For High Performance Computing Using Quantum Annealing [0.6144680854063939]
  We investigate the application of quantum annealing to load balance two paradigmatic algorithms in high performance computing. In a grid based context, quantum annealing is found to outperform classical methods such as the round robin protocol but lacks a decisive advantage over more advanced methods. This signals a noteworthy advancement in solution quality which can have a large impact on effective CPU usage.
  arXiv  Detail & Related papers  (2024-03-08T12:58:12Z)
• Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems [9.516147599772243]
  SSQA is designed based on computing and quantum Monte Carlo. It can handle a 100-times larger problem size compared to QA and atimes larger problem size compared to a traditional SA method.
  arXiv  Detail & Related papers  (2023-02-24T05:08:09Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Scaling overhead of embedding optimization problems in quantum annealing [0.0]
  Embedding fully-connected graphs incurs a quadratic space overhead and thus a significant overhead in the time to solution. Our results demonstrate that standard analog quantum hardware is at a disadvantage in comparison to classical digital annealers.
  arXiv  Detail & Related papers  (2021-03-29T23:52:08Z)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  A central component of variational quantum algorithms (VQA) is the state-preparation circuit, also known as ansatz or variational form. Here, we show that this approach is not always advantageous by introducing ans"atze that incorporate symmetry-breaking unitaries. This work constitutes a first step towards the development of a more general class of symmetry-breaking ans"atze with applications to physics and chemistry problems.
  arXiv  Detail & Related papers  (2020-08-03T18:00:05Z)

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.