DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2024.8

(Quantum) Complexity of Testing Signed Graph Clusterability

Authors: Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh

Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)

Abstract

This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity Õ(N^{1/3}) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Adriaens and Apers, 2023]. Second, we prove an Ω̃(√N) classical query lower bound for testing clusterability, which nearly matches the upper bound from [Adriaens and Apers, 2023]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.

Cite as

Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh. (Quantum) Complexity of Testing Signed Graph Clusterability. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.TQC.2024.8,
  author =	{Chen, Kuo-Chin and Apers, Simon and Hsieh, Min-Hsiu},
  title =	{{(Quantum) Complexity of Testing Signed Graph Clusterability}},
  booktitle =	{19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-328-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{310},
  editor =	{Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.8},
  URN =		{urn:nbn:de:0030-drops-206786},
  doi =		{10.4230/LIPIcs.TQC.2024.8},
  annote =	{Keywords: Quantum Algorithm, classical Query lower Bound, Graph Property testing}
}

Search Results

Documents authored by Chen, Kuo-Chin

(Quantum) Complexity of Testing Signed Graph Clusterability

Abstract

Cite as

Thanks for your feedback!

Could not send message