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) - Promise Clique Homology on weighted graphs is $\text{QMA}_1$-hard and
contained in $\text{QMA}$ [0.0]
We study the complexity of a classic problem in computational topology, the homology problem.
We find that the complexity is characterized by quantum complexity classes.
Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics.
arXiv Detail & Related papers (2023-11-28T21:15:30Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - 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) - 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) - From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions.
For its practicability and wide-applicability, we give a brief review of typical graph learning techniques.
We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
arXiv Detail & Related papers (2022-02-19T02:56:47Z) - Spectral bounds for the quantum chromatic number of quantum graphs [0.0]
We obtain lower bounds for the classical and quantum number of a quantum graph using eigenvalues of the quantum adjacency matrix.
We generalize all the spectral bounds given by Elphick and Wocjan to the quantum graph setting.
Our results are achieved using techniques from linear algebra and a complete definition of quantum graph coloring.
arXiv Detail & Related papers (2021-12-03T05:36:21Z) - Quantum Meets the Minimum Circuit Size Problem [3.199102917243584]
We study the Minimum Circuit Size Problem (MCSP) in the quantum setting.
MCSP is a problem to compute the circuit complexity of Boolean functions.
We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols)
arXiv Detail & Related papers (2021-08-06T15:34:49Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)
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.