Search Results

Documents authored by Hsieh, Min-Hsiu

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 Õ(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}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.TQC.2021
LIPIcs, Volume 197, TQC 2021, Complete Volume

Authors: Min-Hsiu Hsieh

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)

Abstract
LIPIcs, Volume 197, TQC 2021, Complete Volume
Cite as

16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 1-178, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{hsieh:LIPIcs.TQC.2021,
  title =	{{LIPIcs, Volume 197, TQC 2021, Complete Volume}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{1--178},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021},
  URN =		{urn:nbn:de:0030-drops-139940},
  doi =		{10.4230/LIPIcs.TQC.2021},
  annote =	{Keywords: LIPIcs, Volume 197, TQC 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TQC.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Min-Hsiu Hsieh

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hsieh:LIPIcs.TQC.2021.0,
  author =	{Hsieh, Min-Hsiu},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.0},
  URN =		{urn:nbn:de:0030-drops-139958},
  doi =		{10.4230/LIPIcs.TQC.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact