New Approaches to Complexity via Quantum Graphs

• URL: http://arxiv.org/abs/2309.12887v1
• Date: Fri, 22 Sep 2023 14:20:14 GMT
• Title: New Approaches to Complexity via Quantum Graphs
• Authors: Eric Culf and Arthur Mehta
• Abstract summary: We introduce and study the clique problem for quantum graphs. inputs for our problems are presented as quantum channels induced by circuits. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes $textsfNP$, $textsfMA$, $textsfQMA$, and $textsfQMA(2)$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Problems based on the structure of graphs -- for example finding cliques, independent sets, or colourings -- are of fundamental importance in classical complexity. It is well motivated to consider similar problems about quantum graphs, which are an operator system generalisation of graphs. Defining well-formulated decision problems for quantum graphs faces several technical challenges, and consequently the connections between quantum graphs and complexity have been underexplored. In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We also use this approach to reimagine the clique and independent set problems for classical graphs, by taking the inputs to be circuits of deterministic or noisy channels which implicitly determine confusability graphs. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes $\textsf{NP}$, $\textsf{MA}$, $\textsf{QMA}$, and $\textsf{QMA}(2)$. In this way, we exhibit a classical complexity problem whose natural quantisation is $\textsf{QMA}(2)$, rather than $\textsf{QMA}$, which is commonly assumed. To prove the results in the quantum case, we make use of methods inspired by self-testing. To illustrate the utility of our techniques, we include a new proof of the reduction of $\textsf{QMA}(k)$ to $\textsf{QMA}(2)$ via cliques for quantum graphs. We also study the complexity of a version of the independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case where the clique and independent set problems are equivalent.

Related papers

• 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)
• Quantum Computational Complexity and Symmetry [3.481985817302898]
  Testing the symmetries of quantum states and channels provides a way to assess their usefulness. We prove that various symmetry-testing problems are complete for BQP, QMA, QSZK, QIP(2), QIP_EB(2), and QIP. We also prove the inclusion of two Hamiltonian symmetry-testing problems in QMA and QAM.
  arXiv  Detail & Related papers  (2023-09-18T18:48:44Z)
• Quantum Annealing Learning Search Implementations [0.0]
  This paper presents the details and testing of two implementations of the hybrid quantum-classical algorithm Quantum Annealing Learning Search (QALS) on a D-Wave quantum annealer.
  arXiv  Detail & Related papers  (2022-12-21T15:57: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)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations. To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections. Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
  arXiv  Detail & Related papers  (2022-11-09T21:43:16Z)
• Clique Homology is QMA1-hard [0.0]
  We show that the decision problem of determining homology groups of simplicial complexes is QMA1-hard. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.
  arXiv  Detail & Related papers  (2022-09-23T18:14:16Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• BILP-Q: Quantum Coalition Structure Generation [0.0]
  We propose BILP-Q, the first-ever general quantum approach for solving the Coalition Structure Generation problem (CSGP) We run BILP-Q on medium-size problems using a real quantum annealer (D-Wave)
  arXiv  Detail & Related papers  (2022-04-28T22:19:50Z)
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity [0.0]
  Drawing independent samples from a probability distribution is an important computational problem with applications in Monte Carlo algorithms, machine learning, and statistical physics. The problem can in principle be solved on a quantum computer by preparing a quantum state that encodes the entire probability distribution followed by a projective measurement. We investigate the complexity of adiabatically preparing such quantum states for the Gibbs distributions of various models including the Ising chain, hard-sphere models on different graphs, and a model encoding the unstructured search problem.
  arXiv  Detail & Related papers  (2021-09-07T11:43:45Z)
• 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)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)

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.