Quantum property testing in sparse directed graphs

• URL: http://arxiv.org/abs/2410.05001v1
• Date: Mon, 7 Oct 2024 13:00:43 GMT
• Title: Quantum property testing in sparse directed graphs
• Authors: Simon Apers, Frédéric Magniez, Sayantan Sen, Dániel Szabó,
• Abstract summary: In the classical unidirectional model the problem of testing $k$-star-freeness, and more generally $k$-source-subgraph-freeness, is almost maximally hard for large $k$. We show that also quantumly it requires a linear number of queries.
• Score: 0.9624643581968987
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model the problem of testing $k$-star-freeness, and more generally $k$-source-subgraph-freeness, is almost maximally hard for large $k$. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we prove that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the $k$-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of $3$-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.

Related papers

• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk. The same technique can be applied to other 1-dimensional hierarchical graphs.
  arXiv  Detail & Related papers  (2024-04-30T11:45:49Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  We propose a new technique for proving lower bounds on the quantum query of unitary property testing. All obtained lower bounds hold for any $mathsfC$-tester with $mathsfC subseteq mathsfQMA(2)/mathsfqpoly$. We show that there exist quantum oracles relative to which $mathsfQMA(2) notsupset mathsfSBQP$ and $mathsfQMA/mathsfqpoly
  arXiv  Detail & Related papers  (2024-01-15T19:00:36Z)
• New Approaches to Complexity via Quantum Graphs [0.0]
  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)$.
  arXiv  Detail & Related papers  (2023-09-22T14:20:14Z)
• 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 analysis of quantum annealers and hybrid solvers using benchmark optimization problems [0.0]
  This paper studies the Hamiltonian Cycle Problem (HCP) and the Traveling Salesman Problem (TSP) on D-Wave's quantum systems.
  arXiv  Detail & Related papers  (2022-02-17T23:46:27Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• 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)
• Graph Coloring with Quantum Annealing [0.0]
  We develop a graph coloring approximation algorithm that uses the D-Wave 2X as an independent set sampler. A randomly generated set of small but hard graph instances serves as our test set. Our performance analysis suggests limited quantum advantage in the hybrid quantum-classical algorithm.
  arXiv  Detail & Related papers  (2020-12-08T15:08:22Z)
• Sample-efficient learning of quantum many-body systems [17.396274240172122]
  We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs state. We give the first sample-efficient algorithm for the quantum Hamiltonian learning problem.
  arXiv  Detail & Related papers  (2020-04-15T18:01:59Z)

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.