Document Open Access Logo

Applications of the Quantum Algorithm for st-Connectivity

Authors Kai DeLorenzo, Shelby Kimmel, R. Teal Witter

PDF

File

Thumbnail PDF
PDF
LIPIcs.TQC.2019.6.pdf
  • Filesize: 494 kB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum query complexity
  • Theory of computation → Graph algorithms analysis
Keywords
  • graphs
  • algorithms
  • query complexity
  • quantum algorithms
  • span programs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We present quantum algorithms for various problems related to graph connectivity. We give simple and query-optimal algorithms for cycle detection and odd-length cycle detection (bipartiteness) using a reduction to st-connectivity. Furthermore, we show that our algorithm for cycle detection has improved performance under the promise of large circuit rank or a small number of edges. We also provide algorithms for detecting even-length cycles and for estimating the circuit rank of a graph. All of our algorithms have logarithmic space complexity.

Cite As Get BibTex

Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter. Applications of the Quantum Algorithm for st-Connectivity. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.TQC.2019.6

Author Details

Kai DeLorenzo
  • Middlebury College, Computer Science Department, Middlebury, VT, USA
Shelby Kimmel
  • Middlebury College, Computer Science Department, Middlebury, VT, USA
R. Teal Witter
  • Middlebury College, Computer Science Department, Middlebury, VT, USA

Funding

This research was sponsored by the Army Research Office and was accomplished under Grant Number W911NF-18-1-0286. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

Acknowledgements

We thank Chris Cade and Stacey Jeffery for helpful discussions.

References

  1. C. Alvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space. Computational Complexity, 9(2):123-145, 2000. Google Scholar
  2. A. Āriņš. Span-program-based quantum algorithms for graph bipartiteness and connectivity. In International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, pages 35-41. Springer, 2015. Google Scholar
  3. A. Belovs. Span programs for functions with constant-sized 1-certificates. In Proceedings of the 44th Symposium on Theory of Computing (STOC 2012), pages 77-84, 2012. Google Scholar
  4. A. Belovs and B. W. Reichardt. Span programs and quantum algorithms for st-connectivity and claw detection. In Proceedings of the 20th European Symposium on Algorithms (ESA 2012), pages 193-204, 2012. Google Scholar
  5. N. Biggs. Algebraic Potential Theory on Graphs. Bulletin of the London Mathematical Society, 29, 1997. Google Scholar
  6. B. Bollobás. Modern graph theory. Springer Science & Business Media, 2013. Google Scholar
  7. C. Cade, A. Montanaro, and A. Belovs. TIME AND SPACE EFFICIENT QUANTUM ALGORITHMS FOR DETECTING CYCLES AND TESTING BIPARTITENESS. Quantum Information and Computation, 18(1&2):0018-0050, 2018. Google Scholar
  8. A. M. Childs and R. Kothari. Quantum query complexity of minor-closed graph properties. SIAM Journal on Computing, 41(6):1426-1450, 2012. Google Scholar
  9. T. Ito and S. Jeffery. Approximate span programs. Algorithmica, pages 1-38, 2015. Google Scholar
  10. M. Jarret, S. Jeffery, S. Kimmel, and A. Piedrafita. Quantum Algorithms for Connectivity and Related Problems. In 26th Annual European Symposium on Algorithms (ESA 2018), pages 49:1-49:13, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.49.
  11. S. Jeffery and S. Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, August 2017. URL: http://dx.doi.org/10.22331/q-2017-08-17-26.
  12. M. Karchmer and A. Wigderson. On span programs. In Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory, pages 102-111, 1993. Google Scholar
  13. T. J. McCabe. A complexity measure. IEEE Transactions on software Engineering, SE-2(4):308-320, 1976. Google Scholar
  14. N. Nisan and A. Ta-Shma. Symmetric Logspace is Closed Under Complement. In Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing (STOC 1995), pages 140-146. ACM, 1995. URL: http://dx.doi.org/10.1145/225058.225101.
  15. B. W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 544-551. IEEE, 2009. Google Scholar
  16. B. W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pages 560-569, 2011. Google Scholar
  17. R. Yuster and U. Zwick. Finding even cycles even faster. SIAM Journal on Discrete Mathematics, 10(2):209-222, 1997. Google Scholar
  18. A. Zamora. An Algorithm for Finding the Smallest Set of Smallest Rings. Journal of Chemical Information and Computer Sciences, 16(1):40-43, 1976. URL: http://dx.doi.org/10.1021/ci60005a013.
  19. S. Zhang. On the power of Ambainis lower bounds. Theoretical Computer Science, 339(2-3):241-256, 2005. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact