Document Open Access Logo

Linear Time Algorithm for Quantum 2SAT

Authors Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2016.15.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Quantum SAT
  • Davis-Putnam Procedure
  • Linear Time Algorithm

Metrics

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

Abstract

A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors Q_{ij} on a system of n qubits, and the task is to decide whether the Hamiltonian H = sum Q_{ij} has a 0-eigenvalue, or it is larger than 1/n^c for some c = O(1). The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin 1/2, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is O(n^4). In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.

Cite As Get BibTex

Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang. Linear Time Algorithm for Quantum 2SAT. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.15

Author Details

Itai Arad
Miklos Santha
Aarthi Sundaram
Shengyu Zhang

References

  1. B. Aspvall, M. Plass, and R. E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8(3):121-123, 1979. Erratum: Information Processing Letters 14(4): 195 (1982). URL: http://dx.doi.org/10.1016/0020-0190(79)90002-4.
  2. S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. In K. Mahdavi, D. Koslover, and L. L. Brown, editors, Contemporary Mathematics, volume 536. American Mathematical Society, 2011. URL: http://arxiv.org/abs/quant-ph/0602108.
  3. J. Chen, X. Chen, R. Duan, Z. Ji, and B. Zeng. No-go theorem for one-way quantum computing on naturally occurring two-level systems. Physical Review A, 83(5):050301, 2011. Google Scholar
  4. S. Cook. The complexity of theorem proving procedures. In Proceedings of the Third Annual ACM Symposium, pages 151-158, New York, 1971. ACM. Google Scholar
  5. M. Davis, G. Logemann, and D. Loveland. A machine program for theorem-proving. Commun. ACM, 5(7):394-397, July 1962. URL: http://dx.doi.org/10.1145/368273.368557.
  6. M. Davis and H. Putnam. A computing procedure for quantification theory. J. ACM, 7(3):201-215, July 1960. URL: http://dx.doi.org/10.1145/321033.321034.
  7. N. de Beaudrap and S. Gharibian. A linear time algorithm for quantum 2-SAT. CoRR, abs/1508.07338, 2015. To appear in 31st Conference on Computational Complexity. URL: http://arxiv.org/abs/1508.07338.
  8. J. Eisert, M. Cramer, and M. Plenio. Area laws for the entanglement entropy - a review. Reviews of Modern Physics, 82(277), 2010. Google Scholar
  9. S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691-703, 1976. URL: http://dx.doi.org/10.1137/0205048.
  10. D. Gosset and D. Nagaj. Quantum 3-sat is qma1-complete. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 0:756-765, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.86.
  11. Z. Ji, Z. Wei, and B. Zeng. Complete characterization of the ground-space structure of two-body frustration-free hamiltonians for qubits. Physical Review A, 84:042338, 2011. Google Scholar
  12. R. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Complexity of Computer Computations, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf.
  13. A. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2-30, 2003. URL: http://dx.doi.org/10.1016/S0003-4916(02)00018-0.
  14. A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation. American Mathematical Society, Boston, MA, USA, 2002. Google Scholar
  15. M. Krom. The decision problem for a class of first-order formulas in which all disjunctions are binary. Mathematical Logic Quarterly, 13(1-2):15-20, 1967. URL: http://dx.doi.org/10.1002/malq.19670130104.
  16. C. Laumann, R. Moessner, A. Scardicchio, and S. Sondhi. Phase transitions and random quantum satisfiability. Quantum Information &Computation, 10(1), 2010. Google Scholar
  17. L. Levin. Universal sequential search problems. Problems of Information Transmission, 9(3):265-266, 1973. Google Scholar
  18. C. Papadimitriou. On selecting a satisfying truth assignment (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 163-169, 1991. URL: http://dx.doi.org/10.1109/SFCS.1991.185365.
  19. S. Sachdev. Quantum phase transitions. Wiley Online Library, 2007. Google Scholar
  20. G. Vidal, J.-I. Latorre, E. Rico, and A. Kitaev. Entanglement in quantum critical phenomena. Phys. Rev. Lett., 90:227902, Jun 2003. URL: http://dx.doi.org/10.1103/PhysRevLett.90.227902.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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