Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more

• URL: http://arxiv.org/abs/2101.08381v3
• Date: Wed, 21 Jul 2021 00:08:03 GMT
• Title: Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more
• Authors: Alex Meiburg
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A quantum constraint problem is a frustration-free Hamiltonian problem: given a collection of local operators, is there a state that is in the ground state of each operator simultaneously? It has previously been shown that these problems can be in P, NP-complete, MA-complete, or QMA_1-complete, but this list has not been shown to be exhaustive. We present three quantum constraint problems, that are (1) BQP_1-complete (also known as coRQP), (2) QCMA_1-complete and (3) coRP-complete. This provides the first natural complete problem for BQP_1. We also show that all quantum constraint problems can be realized on qubits, a trait not shared with classical constraint problems. These results suggest a significant diversity of complexity classes present in quantum constraint problems.

Related papers

• 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)
• A Quantum Unique Games Conjecture [0.0]
  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.
  arXiv  Detail & Related papers  (2024-09-30T07:34:41Z)
• 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)
• 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)
• Complexity Classification of Product State Problems for Local Hamiltonians [0.94371657253557]
  We classify the complexity of finding minimum-energy product states for Hamiltonians defined by any fixed set of allowed 2-qubit interactions. We prove that estimating the minimum energy of a product state is in P if and only if all allowed interactions are 1-local, and NP-complete otherwise.
  arXiv  Detail & Related papers  (2024-01-12T17:51:09Z)
• Four Related Combinatorial Problems [0.0]
  We show that a quantum measure $mu$ satisfies a grade-2 additivity condition. We then show that this solves the original quantum measure problem.
  arXiv  Detail & Related papers  (2023-11-13T19:57:12Z)
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs [1.2179548969182574]
  An experiment is presented to demonstrate the use of Rydberg atoms to solve (i.e., to program and obtain the solution of) the satisfiability (3-SAT) problem.
  arXiv  Detail & Related papers  (2023-02-28T07:49:10Z)
• 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)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• 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)

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.