Distributed Quantum Advantage for Local Problems

• URL: http://arxiv.org/abs/2411.03240v1
• Date: Tue, 05 Nov 2024 16:38:49 GMT
• Title: Distributed Quantum Advantage for Local Problems
• Authors: Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren,
• Abstract summary: We show a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. We present a problem that we call iterated GHZ, which is defined using only local constraints.
• Score: 3.1024627815534593
• License:
• Abstract: We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree $\Delta$, any classical (deterministic or randomized) LOCAL model algorithm will require $\Omega(\Delta)$ rounds to solve the iterated GHZ problem, while the problem can be solved in $1$ round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires $\Omega(\Delta)$ rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.

Related papers

• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
  We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round $i$HVA. Our ansatz solves MaxCut exactly for graphs with up to 24 nodes and $D leq 5$, whereas only approximate solutions can be derived by the classical near-optimal Goemans-Williamson algorithm.
  arXiv  Detail & Related papers  (2024-08-17T03:34:17Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Online Locality Meets Distributed Quantum Computing [2.3821076274208552]
  Three lines of research have recently explored extensions of the classical LOCAL model of distributed computing. We prove new results on the capabilities and limitations of all of these models, for locally checkable labeling problems (LCLs) Our work implies limitations on the advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds.
  arXiv  Detail & Related papers  (2024-03-04T10:03:54Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  Normalized-Cut (N-Cut) is a famous model of spectral clustering. Traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via $K$-means or spectral rotation. We propose a novel N-Cut solver based on the famous coordinate descent method.
  arXiv  Detail & Related papers  (2023-11-26T07:11:58Z)
• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  We develop a first-order term to bridge the original problem and discretization algorithm. Since the non-heuristic method is aware of the original graph cut problem, the final discrete solution is more reliable.
  arXiv  Detail & Related papers  (2023-10-19T13:57:38Z)
• Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems [7.723735038335632]
  Quantum Approximate Optimization Algorithm (QAOA) is considered as a promising candidate to demonstrate quantum supremacy. limited qubit availability and restricted coherence time challenge QAOA to solve large-scale pseudo-Boolean problems. We propose a distributed QAOA which can solve a general pseudo-Boolean problem by converting it to a simplified Ising model.
  arXiv  Detail & Related papers  (2023-10-08T08:07:11Z)
• No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
  We give an almost complete characterization of the hardness of $c$-coloring $chi$-chromatic graphs with distributed algorithms. We show that these problems do not admit any distributed quantum advantage.
  arXiv  Detail & Related papers  (2023-07-18T17:17:27Z)
• 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)
• Quantum Assisted Eigensolver [0.0]
  We propose a hybrid quantum-classical algorithm for approxing the ground state and ground state energy of a Hamiltonian. The output from the quantum part of the algorithm is utilized as input for the classical computer.
  arXiv  Detail & Related papers  (2020-09-23T08:33:18Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.