Quantum algorithm for a set of quantum 2SAT problems

doi:10.1088/1674-1056/abd741

Abstract We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability (2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain. All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states. The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace. Our numerical results suggest that the time complexity of our algorithm is O(n^3.9) for yielding non-trivial solutions for problems with the number of clauses m=dn(n-1)/2 (\(d\lesssim 0.1\)). We discuss the advantages of our algorithm over the known quantum and classical algorithms.

Keywords: adiabatic quantum computation quantum Hamiltonian algorithm quantum 2SAT problem

Received: 09 September 2020
Revised: 29 October 2020
Accepted manuscript online: 30 December 2020

PACS:	03.67.Ac	(Quantum algorithms, protocols, and simulations)
	03.67.Lx	(Quantum computation architectures and implementations)
	89.70.Eg	(Computational complexity)

Fund: Project supported by the National Key R&D Program of China (Grant Nos. 2017YFA0303302 and 2018YFA0305602), the National Natural Science Foundation of China (Grant No. 11921005), and Shanghai Municipal Science and Technology Major Project, China (Grant No. 2019SHZDZX01).

Corresponding Authors: ^†Corresponding author. E-mail: wubiao@pku.edu.cn

Cite this article:

Yanglin Hu(胡杨林), Zhelun Zhang(张哲伦), and Biao Wu(吴飙) Quantum algorithm for a set of quantum 2SAT problems 2021 Chin. Phys. B 30 020308

1 Nielsen M A and Chuang I L 2010 Quantum Computation and Quantum Information, 10th Anniversary Edition (Cambridge: Cambridge University Press) pp. 216-271
2 Farhi E and Gutmann S 1998 Phys. Rev. A 57 2403
3 Farhi E, Goldstone J, Gutmann S and Sipser M arXiv: quant-ph/0001106v1
4 Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S and Regev O 2007 SIAM J. Comput. 37 166
5 Yu H Y, Huang Y L and Wu B 2018 Chin. Phys. Lett. 35 110303
6 Altshuler B, Krovib H and Roland J 2010 Proc. Natl. Acad. Sci. USA 107 12446
7 Roland J and Cerf N J 2002 Phys. Rev. A 65 042308
8 van Dam W, Mosca M and Vazirani U 2001 Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, October 8-11, 2001, Newport Beach, United States, pp. 279-287
9 Wilczek F, Hu H Y and Wu B 2020 Chin. Phys. Lett. 37 050304
10 Wu B, Yu H Y and Wilczek F 2020 Phys. Rev. A 101 012318
11 de Beaudrap N and Gharibian S 2016 Proceedings of 31st Conference on Computational Complexity, May 29-June 1, 2016, Tokyo, Japan, pp. 21:1-27:21
13 Even S and Itai A and Shamir A 1976 SIAM Journal on Computing 5 691
14 Sergey B arXiv: quant-ph/0602108v1
15 Arad I, Santha M, Sundaram A and Zhang S Y 2018 Theory Comput. 14 1
16 Wilczek F and Zee A 1984 Phys. Rev. Lett. 52 2111
18 Hodgson R P and Parkinson J B 1984 J. Phys. C: Solid State Phys. 17 3223

[1]	Quantum adiabatic algorithms using unitary interpolation Shuo Zhang(张硕), Qian-Heng Duan(段乾恒), Tan Li(李坦), Xiang-Qun Fu(付向群), He-Liang Huang(黄合良), Xiang Wang(汪翔), Wan-Su Bao(鲍皖苏). Chin. Phys. B, 2020, 29(1): 010308.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Quantum algorithm for a set of quantum 2SAT problems

Cite this article:

Online attention