Quantum Hamiltonian Algorithms for Maximum Independent Sets

• URL: http://arxiv.org/abs/2310.14546v5
• Date: Wed, 4 Sep 2024 05:17:40 GMT
• Title: Quantum Hamiltonian Algorithms for Maximum Independent Sets
• Authors: Xianjue Zhao, Peiyun Ge, Hongye Yu, Li You, Frank Wilczek, Biao Wu,
• Abstract summary: An alternative algorithm, short named the PK algorithm, reveals that the independent sets diffuse over a media graph governed by a non-abelian gauge matrix of an emergent PXP model. Although the two are mathematically equivalent, the PK algorithm exhibits more efficient and resource-saving performance.
• Score: 6.772902928686719
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: With qubits encoded into atomic ground and Rydberg states and situated on the vertexes of a graph, the conditional quantum dynamics of Rydberg blockade, which inhibits simultaneous excitation of nearby atoms, has been employed recently to find maximum independent sets following an adiabatic evolution algorithm hereafter denoted by HV [Science 376, 1209 (2022)]. An alternative algorithm, short named the PK algorithm, reveals that the independent sets diffuse over a media graph governed by a non-abelian gauge matrix of an emergent PXP model. This work shows the above two algorithms are mathematically equivalent, despite of their seemingly different physical implementations. More importantly, we demonstrated that although the two are mathematically equivalent, the PK algorithm exhibits more efficient and resource-saving performance. Within the same range of experimental parameters, our numerical studies suggest that the PK algorithm performs at least 25% better on average and saves at least $6\times10^6$ measurements ($\sim 900$ hours of continuous operation) for each graph when compared to the HV algorithm. We further consider the measurement error and point out that this may cause the oscillations in the performance of the HV's optimization process.

Related papers

• A quantum algorithm for advection-diffusion equation by a probabilistic imaginary-time evolution operator [0.0]
  We propose a quantum algorithm for solving the linear advection-diffusion equation by employing a new approximate probabilistic imaginary-time evolution (PITE) operator. We construct the explicit quantum circuit for realizing the imaginary-time evolution of the Hamiltonian coming from the advection-diffusion equation. Our algorithm gives comparable result to the Harrow-Hassidim-Lloyd (HHL) algorithm with similar gate complexity, while we need much less ancillary qubits.
  arXiv  Detail & Related papers  (2024-09-27T08:56:21Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  We provide an efficient ($epsilon,$delta$)-DP algorithm tailored specifically for such graphs. Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters.
  arXiv  Detail & Related papers  (2024-03-21T11:57:16Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• 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)
• Quantum algorithms for anomaly detection using amplitude estimation [5.20363732303968]
  Anomaly detection algorithm based on density estimation (called ADDE algorithm) is one of widely used algorithms. In this paper, we propose a new quantum ADDE algorithm based on amplitude estimation.
  arXiv  Detail & Related papers  (2021-09-28T15:47:56Z)
• A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy [22.31288740171446]
  The PC algorithm is the state-of-the-art algorithm for causal structure discovery on observational data. It can be computationally expensive in the worst case due to the conditional independence tests are performed. This makes the algorithm computationally intractable when the task contains several hundred or thousand nodes. We propose a critical observation that the conditional set rendering two nodes independent is non-unique, and including certain redundant nodes do not sacrifice result accuracy.
  arXiv  Detail & Related papers  (2021-09-10T02:22:10Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters. The proposed algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
  arXiv  Detail & Related papers  (2021-04-27T11:03:52Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)

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.