A Quantum Unique Games Conjecture

• URL: http://arxiv.org/abs/2409.20028v1
• Date: Mon, 30 Sep 2024 07:34:41 GMT
• Title: A Quantum Unique Games Conjecture
• Authors: Hamoon Mousavi, Taro Spirig,
• Abstract summary: We introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: After the NP-hardness of computational problems such as 3SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum extensions of some of these problems are known to be hard-indeed undecidable-their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.

Related papers

• A Dequantized Algorithm for the Guided Local Hamiltonian Problem [2.891413712995642]
  The guided local Hamiltonian (GLH) problem can be efficiently solved on a quantum computer and is proved to be BQP-complete. This makes the GLH problem a valuable framework for exploring the fundamental separation between classical and quantum computation. We introduce a dequantized classical algorithm for a randomized quantum imaginary-time evolution quantum algorithm.
  arXiv  Detail & Related papers  (2024-11-25T07:38:16Z)
• Solving eigenvalue problems obtained by the finite element method on a quantum annealer using only a few qubits [0.0]
  One of the main obstacles for achieving a practical quantum advantage in quantum computing lies in the relatively small number of qubits currently available in quantum hardware. We show how to circumvent this problem in the context of eigenvalue problems obtained by the finite element method. As an example, we apply AQAE to eigenvalue problems that are relevant in a wide range of contexts, such as electromagnetism, acoustics and seismology.
  arXiv  Detail & Related papers  (2024-10-17T16:39:03Z)
• State-Averaged Orbital-Optimized VQE: A quantum algorithm for the democratic description of ground and excited electronic states [0.0]
  The SA-OO-VQE package aims to answer both problems with its hybrid quantum-classical conception based on a typical Variational Quantum Eigensolver approach. The SA-OO-VQE has the ability to treat degenerate (or quasi-degenerate) states on the same footing, thus avoiding known numerical optimization problems around avoided crossings or conical intersections.
  arXiv  Detail & Related papers  (2024-01-22T12:16:37Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.69353915790503]
  There are problems for which there is no trivial' computational advantage possible with the current quantum hardware. We would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity? By the use of the QSETH framework [Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT.
  arXiv  Detail & Related papers  (2023-09-28T13:30:20Z)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement. Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
  arXiv  Detail & Related papers  (2023-01-23T19:23:54Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more [0.0]
  We show that all quantum constraint problems can be realized on qubits, a trait not shared with classical constraint problems. Results suggest a significant diversity of classes present in quantum constraint problems.
  arXiv  Detail & Related papers  (2021-01-21T01:08:04Z)

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.