Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors

• URL: http://arxiv.org/abs/2502.04291v1
• Date: Thu, 06 Feb 2025 18:34:59 GMT
• Title: Identifying hard native instances for the maximum independent set problem on neutral atoms quantum processors
• Authors: Pierre Cazals, Aymeric François, Loïc Henriet, Lucas Leclerc, Malory Marin, Yassine Naghmouchi, Wesley da Silva Coelho, Florian Sikora, Vittorio Vitale, Rémi Watrigant, Monique Witt Garzillo, Constantin Dalyac,
• Abstract summary: The Maximum Independent Set (MIS) problem is a fundamental optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. We generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth.
• Score: 0.48520567143062737
• License:
• Abstract: The Maximum Independent Set (MIS) problem is a fundamental combinatorial optimization task that can be naturally mapped onto the Ising Hamiltonian of neutral atom quantum processors. Given its connection to NP-hard problems and real-world applications, there has been significant experimental interest in exploring quantum advantage for MIS. Pioneering experiments on King's Lattice graphs suggested a quadratic speed-up over simulated annealing, but recent benchmarks using state-of-the-art methods found no clear advantage, likely due to the structured nature of the tested instances. In this work, we generate hard instances of unit-disk graphs by leveraging complexity theory results and varying key hardness parameters such as density and treewidth. For a fixed graph size, we show that increasing these parameters can lead to prohibitive classical runtime increases of several orders of magnitude. We then compare classical and quantum approaches on small instances and find that, at this scale, quantum solutions are slower than classical ones for finding exact solutions. Based on extended classical benchmarks at larger problem sizes, we estimate that scaling up to a thousand atoms with a 1 kHz repetition rate is a necessary step toward demonstrating a computational advantage with quantum methods.

Related papers

• 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)
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
  A superconducting quantum computer is used to investigate the performance of a hybrid quantum-classical algorithm. We benchmark the quantum solver against similarly high-performing classicals. A run-time analysis shows that the quantum solver on large-scale problems is competitive against Gurobi but short of others on a projected 100-qubit quantum computer.
  arXiv  Detail & Related papers  (2024-04-26T17:59:22Z)
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups [9.927706464212168]
  Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. We study the maximum independent set problem on unit-disk graphs with a broader range of classical solvers. We find that quasi-planar instances with Union-Jack-like connectivity can be solved to optimality for up to thousands of nodes within minutes.
  arXiv  Detail & Related papers  (2023-07-18T17:16:42Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• 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)
• Unbiasing Fermionic Quantum Monte Carlo with a Quantum Computer [0.4893345190925178]
  Many-electron problems pose some of the greatest challenges in computational science. Fermionic quantum Monte Carlo (QMC) methods are among the most powerful approaches to these problems. We propose an approach that combines constrained QMC with quantum computing tools to reduce such biases.
  arXiv  Detail & Related papers  (2021-06-30T17:43:47Z)
• 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.