FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing

• URL: http://arxiv.org/abs/2205.05004v1
• Date: Tue, 10 May 2022 16:20:21 GMT
• Title: FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing
• Authors: Phuc Thai, My T. Thai, Tam Vu, Thang N. Dinh
• Abstract summary: We introduce a novel notion of non-separablegroup, defined as a subset of qubits in a Hamiltonian that obtains the same value in optimal solutions. FastHare, iteratively, detects and merges non-separable groups into single qubits. It does so within a provable worst-case time complexity of only $O(alpha n2)$, for some user-defined parameter $alpha$.
• Score: 17.830687420962512
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum annealing (QA) that encodes optimization problems into Hamiltonians remains the only near-term quantum computing paradigm that provides sufficient many qubits for real-world applications. To fit larger optimization instances on existing quantum annealers, reducing Hamiltonians into smaller equivalent Hamiltonians provides a promising approach. Unfortunately, existing reduction techniques are either computationally expensive or ineffective in practice. To this end, we introduce a novel notion of non-separable~group, defined as a subset of qubits in a Hamiltonian that obtains the same value in optimal solutions. We develop a theoretical framework on non-separability accordingly and propose FastHare, a highly efficient reduction method. FastHare, iteratively, detects and merges non-separable groups into single qubits. It does so within a provable worst-case time complexity of only $O(\alpha n^2)$, for some user-defined parameter $\alpha$. Our extensive benchmarks for the feasibility of the reduction are done on both synthetic Hamiltonians and 3000+ instances from the MQLIB library. The results show FastHare outperforms the roof duality, the implemented reduction method in D-Wave's SDK library, with 3.6x higher average reduction ratio. It demonstrates a high level of effectiveness with an average of 62% qubits saving and 0.3s processing time, advocating for Hamiltonian reduction as an inexpensive necessity for QA.

Related papers

• 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)
• Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization [13.521769871808537]
  This paper proposes Choco-Q, a formal and universal framework for constrained binary optimization problems. The main innovation of Choco-Q is to embed the commute Hamiltonian as the driver Hamiltonian, resulting in a much more general encoding formulation. Our decomposition methods only take linear time complexity, achieving end-to-end acceleration.
  arXiv  Detail & Related papers  (2025-03-31T10:47:20Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• General, efficient, and robust Hamiltonian engineering [0.20482269513546453]
  We introduce an efficient and robust scheme to engineer arbitrary local many-body Hamiltonians. These sequences are constructed by efficiently solving a linear program (LP) which minimizes the total evolution time. In particular, we solve the Hamiltonian engineering problem for arbitrary two-body Hamiltonians on a 2D square lattice with $225$ qubits in only $60$ seconds.
  arXiv  Detail & Related papers  (2024-10-25T18:00:01Z)
• SHARC-VQE: Simplified Hamiltonian Approach with Refinement and Correction enabled Variational Quantum Eigensolver for Molecular Simulation [0.0]
  SHARC-VQE significantly reduces computational costs for molecular simulations. measurement outcomes using SHARC-VQE are less prone to errors induced by noise from quantum circuits.
  arXiv  Detail & Related papers  (2024-07-17T04:01:55Z)
• Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD. Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers. Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
  arXiv  Detail & Related papers  (2024-04-30T23:55:03Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin Models [8.463477025989542]
  We take advantage of a digitized-counterdiabatic quantum optimization (DCQO) algorithm to find an optimal solution of the $p$-spin model up to 4-local interactions. By further optimizing parameters using variational methods, we solve with unit accuracy 2-spin, 3-spin, and 4-spin problems for $100%$, $93%$, and $83%$ of instances, respectively.
  arXiv  Detail & Related papers  (2023-11-11T22:49:16Z)
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error [0.0]
  We introduce an algorithm to compute Hamiltonian dynamics on digital quantum computers. The algorithm achieves zero discretization error with finite depth. The gate count for simulation up to time $t$ is $O(t2mu2)$ with $mu$ the $1$-norm of the Hamiltonian.
  arXiv  Detail & Related papers  (2023-08-07T16:12:27Z)
• SqueezeLLM: Dense-and-Sparse Quantization [80.32162537942138]
  Main bottleneck for generative inference with LLMs is memory bandwidth, rather than compute, for single batch inference. We introduce SqueezeLLM, a post-training quantization framework that enables lossless compression to ultra-low precisions of up to 3-bit. Our framework incorporates two novel ideas: (i) sensitivity-based non-uniform quantization, which searches for the optimal bit precision assignment based on second-order information; and (ii) the Dense-and-Sparse decomposition that stores outliers and sensitive weight values in an efficient sparse format.
  arXiv  Detail & Related papers  (2023-06-13T08:57:54Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  We provide the first non-asymptotic, finite-time analysis for double Q-learning. We show that both synchronous and asynchronous double Q-learning are guaranteed to converge to an $epsilon$-accurate neighborhood of the global optimum.
  arXiv  Detail & Related papers  (2020-09-29T18:48:21Z)

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.