An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

• URL: http://arxiv.org/abs/2412.19623v1
• Date: Fri, 27 Dec 2024 12:57:06 GMT
• Title: An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
• Authors: Marco Aldi, Sevag Gharibian, Dorian Rudolph,
• Abstract summary: We define two new subclasses of Total Function NP (TFNP) based on the study of complex systems. At the heart of our study is the computational problem known as Quantum SAT with a System of Distinct Representatives (SDR) We show how to embed the roots of a sparse, high-degree complexity into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of SDR.
• Score: 0.0
• License:
• Abstract: The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on B\'ezout's theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, L\"auchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA is contained in MHS.

Related papers

• A unified approach to quantum de Finetti theorems and SoS rounding via geometric quantization [0.0]
  We study a connection between a Hermitian version of the SoS hierarchy, related to the quantum de Finetti theorem. We show that previously known HSoS rounding algorithms can be recast as quantizing an objective function.
  arXiv  Detail & Related papers  (2024-11-06T17:09:28Z)
• Bosonic Quantum Computational Complexity [0.0]
  We lay foundations for such a research program. We introduce natural complexity classes and problems based on bosonic generalizations of BQP. We show that the problem of deciding the boundedness of the spectrum of a bosonic Hamiltonian is co-NP-hard.
  arXiv  Detail & Related papers  (2024-10-05T19:43:41Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem [14.693394941317843]
  We present a new verifiable proof-producing method based on a combination of a Boolean satisfiability solver and a computer algebra system. Our method shows that a KS system in 3D must contain at least 24 vectors. We also provide the first computer-verifiable proof certificate of a lower bound to the KS problem with a size of 40.3 TiB in order 23.
  arXiv  Detail & Related papers  (2023-06-23T06:42:59Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  This paper presents and describes a hybrid quantum computing strategy for solving 3-SAT problems. The performance of this approximation has been tested over a set of representative scenarios when dealing with 3-SAT from the quantum computing perspective.
  arXiv  Detail & Related papers  (2023-06-07T12:19:22Z)
• TheoremQA: A Theorem-driven Question Answering dataset [100.39878559382694]
  GPT-4's capabilities to solve these problems are unparalleled, achieving an accuracy of 51% with Program-of-Thoughts Prompting. TheoremQA is curated by domain experts containing 800 high-quality questions covering 350 theorems.
  arXiv  Detail & Related papers  (2023-05-21T17:51:35Z)
• T-SciQ: Teaching Multimodal Chain-of-Thought Reasoning via Mixed Large Language Model Signals for Science Question Answering [59.63860993280275]
  Large Language Models (LLMs) have demonstrated exceptional performance in various Natural Language Processing (NLP) tasks. We propose a novel method termed T-SciQ that aims at teaching science question answering with LLM signals. Our approach achieves a new state-of-the-art performance on the ScienceQA benchmark, with an accuracy of 96.18%.
  arXiv  Detail & Related papers  (2023-05-05T11:56:30Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary. Characterizing the complexity of these problems requires new algorithmic techniques and lower bound methods. We present a unitary property testing-based approach towards an oracle separation between $mathsfQMA$ and $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2022-10-12T03:01:00Z)
• 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)

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.