4.6 Article

Number Partitioning With Grover's Algorithm in Central Spin Systems

期刊

PRX QUANTUM
卷 2, 期 2, 页码 -

出版社

AMER PHYSICAL SOC
DOI: 10.1103/PRXQuantum.2.020319

关键词

-

资金

  1. ONR [N00014-17-1-2279]
  2. AFOSR [FA9550-20-1-0059]
  3. ARO [W911NF-16-1-0490]
  4. DOE Office of Science, Office of Basic Energy Sciences [DE-SC0019174]
  5. NSF [PHY-1753021]
  6. NSF GRFP
  7. NDSEG Fellowship

向作者/读者索取更多资源

The research introduces a quantum algorithm using Grover search to solve a class of NP-complete decision problems, providing quantum speedup across a known phase transition in computational complexity. The scheme encodes each problem instance in the couplings of quantum bits to a central spin or boson to realize the oracle without knowledge of the solution, and introduces a scalable recursive algorithm.
Numerous conceptually important quantum algorithms rely on a blackbox device known as an oracle, which is typically difficult to construct without knowing the answer to the problem that the algorithm is intended to solve. A notable example is Grover's search algorithm. Here we propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems, including the special case of number partitioning. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution. The algorithm provides a quantum speedup across a known phase transition in the computational complexity of the partition problem, and we identify signatures of the phase transition in the simulated performance. Whereas the naive implementation of our algorithm requires a spectral resolution that scales exponentially with system size for NP-complete problems, we also present a recursive algorithm that enables scalability. We propose and analyze implementation schemes with cold atoms, including Rydberg-atom and cavity-QED platforms.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.6
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据