中国物理B ›› 2021, Vol. 30 ›› Issue (2): 20308-0.doi: 10.1088/1674-1056/abd741

所属专题： SPECIAL TOPIC — Quantum computation and quantum simulation

• • 上一篇    下一篇

  

  • 收稿日期:2020-09-09 修回日期:2020-10-29 接受日期:2020-12-30 出版日期:2021-01-18 发布日期:2021-01-26

Quantum algorithm for a set of quantum 2SAT problems

Yanglin Hu(胡杨林)1, Zhelun Zhang(张哲伦)1, and Biao Wu(吴飙)1,2,3,†   

  1. 1 International Center for Quantum Materials, School of Physics, Peking University, Beijing 100871, China; 2 Wilczek Quantum Center, School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240, China; 3 Collaborative Innovation Center of Quantum Matter, Beijing 100871, China
  • Received:2020-09-09 Revised:2020-10-29 Accepted:2020-12-30 Online:2021-01-18 Published:2021-01-26
  • Contact: †Corresponding author. E-mail: wubiao@pku.edu.cn
  • Supported by:
    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).

RichHTML

6

PDF (PC)

183

赞

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(n3.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.

Key words: adiabatic quantum computation, quantum Hamiltonian algorithm, quantum 2SAT problem

中图分类号:  (Quantum algorithms, protocols, and simulations)

  • 03.67.Ac
03.67.Lx (Quantum computation architectures and implementations) 89.70.Eg (Computational complexity)