Number Partitioning with Grover's Algorithm in Central Spin Systems
| Autor: | Ognjen Markovic, Shankari Rajagopal, Monika Schleier-Smith, Eric S. Cooper, Amir H. Safavi-Naeini, Emily Davis, Victoria Borish, Jacob Hines, Galit Anikeeva, Avikar Periwal |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
Class (set theory) Quantum Physics Statistical Mechanics (cond-mat.stat-mech) Computer science General Engineering FOS: Physical sciences 01 natural sciences 010305 fluids & plasmas Search algorithm Encoding (memory) 0103 physical sciences Grover's algorithm General Earth and Planetary Sciences 010306 general physics Quantum Physics (quant-ph) Condensed Matter - Statistical Mechanics General Environmental Science Spin-½ |
| DOI: | 10.48550/arxiv.2009.05549 |
| Popis: | Numerous conceptually important quantum algorithms rely on a black-box 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. Comment: 23 pages, 13 figures, typos corrected, edits for clarity |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|