Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Frontiers

Atom cavity encoding for NP-complete problems

Meng Ye, Xiaopeng Li

Published Nov 28, 2024• 3 citations
Publisher

Abstract

Abstract We consider an atom-cavity system having long-range atomic interactions mediated by cavity modes. It has been shown that quantum simulations of spin models with this system can naturally be used to solve number partition problems. Here, we present encoding schemes for numerous nondeterministic polynomial-time complete (NP-complete) problems, encompassing the majority of Karp’s 21 NP-complete problems. We find a number of such computation problems can be encoded by the atom-cavity system at a linear cost of atom number. There are still certain problems that cannot be encoded by the atom-cavity as efficiently, such as quadratic unconstrained binary optimization (QUBO), and the Hamiltonian cycle. For these problems, we provide encoding schemes with a quadratic or quartic cost in the atom number. We expect this work to provide important guidance to search for the practical quantum advantage of the atom-cavity system in solving NP-complete problems. Moreover, the encoding schemes we develop here may also be adopted in other optical systems for solving NP-complete problems, where a similar form of Mattis-type spin glass Hamiltonian as in the atom-cavity system can be implemented.

DOI
10.1007/s44214-024-00069-x

Related papers

Atom Cavity Encoding for NP-Complete Problems

Ye, Meng, Xiaopeng Li

We consider an atom-cavity system having long-range atomic interactions mediated by cavity modes. It has been shown that quantum simulations of spin models with this system can naturally be used to solve number partition problems. Here, we present encoding schemes for numerous NP-complete problems, encompassing the majority of Karp's 21 NP-complete problems. We find a number of such computation problems can be encoded by the atom-cavity system at a linear cost of atom number. There are still certain problems that cannot be encoded by the atom-cavity as efficiently, such as quadratic unconstrained binary optimization (QUBO), and the Hamiltonian cycle. For these problems, we provide encoding schemes with a quadratic or quartic cost in the atom number. We expect this work to provide important guidance to search for the practical quantum advantage of the atom-cavity system in solving NP-complete problems. Moreover, the encoding schemes we develop here may also be adopted in other optical systems for solving NP-complete problems, where a similar form of Mattis-type spin glass Hamiltonian as in the atom-cavity system can be implemented.

arXiv:2407.11851•Jul 16, 2024•0 citations

Universal Quantum Optimization with Cold Atoms in an Optical Cavity

Meng Ye, Ye Tian, Jian Hui Lin +6 more

Cold atoms in an optical cavity have been widely used for quantum simulations of many-body physics, where the quantum control capability has been advancing rapidly in recent years. Here, we show the atom cavity system is universal for quantum optimization with arbitrary connectivity. We consider a single-mode cavity and develop a Raman coupling scheme by which the engineered quantum Hamiltonian for atoms directly encodes number partition problems. The programmability is introduced by placing the atoms at different positions in the cavity with optical tweezers. The number partition problem solution is encoded in the ground state of atomic qubits coupled through a photonic cavity mode, which can be reached by adiabatic quantum computing. We construct an explicit mapping for the 3-SAT and vertex cover problems to be efficiently encoded by the cavity system, which costs linear overhead in the number of atomic qubits. The atom cavity encoding is further extended to quadratic unconstrained binary optimization problems. The encoding protocol is optimal in the cost of atom number scaling with the number of binary degrees of freedom of the computation problem. Our theory implies the atom cavity system is a promising quantum optimization platform searching for practical quantum advantage.

arXiv:2306.16943•Physical Review Letters•Sep 5, 2023•18 citations

Adaptive quantum optimization algorithms for programmable atom-cavity systems

Yuchen Luo, Xiaopeng Li, Jian Hui Lin

Developing quantum algorithms adaptive to specific constraints of near-term devices is an essential step towards practical quantum advantage. In a recent work [Phys. Rev. Lett. 131, 103601 (2023)], we show cold atoms in an optical cavity can be built as a universal quantum optimizer with programmable all-to-all interactions, and the effective Hamiltonian for atoms directly encodes number partitioning problems (NPPs). Here, we numerically investigate the performance of quantum annealing (QA) and quantum approximate optimization algorithm (QAOA) to find the solution of NPP that is encoded in the ground state of atomic qubits. We find the success probability of the standard QA decays rapidly with the problem size. The optimized annealing path or inhomogeneous driving fields only lead to mild improvement on the success probability. Similarly, the QAOA always gets trapped in a false local minimum, and there is no significant performance improvement as we increase the depth of the quantum circuit. To overcome the difficulty of solving NPPs, we propose an adaptive variational quantum algorithm (VQA) whose ansatz differs from that of the QAOA by releasing the parameter freedom of the NPP Hamiltonian. Through numerical simulations, we find that our adaptive VQA can achieve rather high success probability within very small circuit depth. It is thus worth paying the extra optimization cost of additional parameters for improving performance compared to the QAOA. Therefore, our adaptive VQA provides a promising choice for programmable atom-cavity systems to demonstrate competitive computational power within its quantum coherence time.

arXiv:2406.07055•Physical Review A•Nov 25, 2025•1 citation

Quantum programming of the satisfiability problem with Rydberg atom graphs

Seokho Jeong, Minhyuk Kim, Minki Hhan +2 more

Finding a quantum computing method to solve nondeterministic polynomial time (NP)-complete problems is currently of paramount importance in quantum information science. Here we propose and experimentally demonstrate a Rydberg atom approach to program the 3-SAT problem, the prototypical NP-complete problem which allows general programming of all NP problems. We use Rydberg atom graphs, each of which consists of Rydberg atom dimers and trimers coupled with quantum wires in the Rydberg blockade interaction regime, to formulate general Boolean expressions, and obtain their many-body ground states to determine the satisfiabilities of the given 3-SAT problem instances quantum mechanically.

arXiv:2302.14369•Physical Review Research•Oct 12, 2023•23 citations

Encoding Binary Comparison Constraints in QUBO for Quantum Annealing

Philippe Codognet

We consider the encoding in Quadratic Unconstrained Binary Optimization (QUBO) of binary comparison constraints, that is, constraints of the form x < y + c, x ≤ y + c, and x = y + c, where x and y are two integer variables and c is an integer constant. For the sake of simplicity, we will consider that x and y are bounded and belong to the same interval {1,..., n}. We will show that such constraints can be encoded without the need of any extra-variable, conversely to the general scheme for linear inequations, which requires between n - 1 and ⌈log2(n - 1)⌉ extra-variables, depending on the encoding chosen for integers. Limiting the number of extra-variables needed in QUBO formulations is important as each Boolean QUBO variable will be implemented as a (logical) qubit on a quantum device and the number of such qubits is limited in quantum annealing systems such as D-Wave machines.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•1 citation

A Dynamically Programmable Quantum Photonic Microprocessor for Graph Computation

Huihui Zhu, Haosen Chen, Shuyi Li +14 more

Abstract Quantum computing has grown extensively, especially in system design and development, and the current research focus has gradually evolved from validating quantum advantage to practical applications. In particular, nondeterministic‐polynomial‐time (NP)‐complete problems are central in numerous important application areas. Still, in practice, it is difficult to solved efficiently with conventional computers, limited by the exponential jump in hardness. Here, a quantum photonic microprocessor based on Gaussian boson sampling (GBS) that offers dynamic programmability to solve various graph‐related NP‐complete problems is demonstrated. The system with optical, electrical, and thermal packaging implements a GBS with 16 modes of single‐mode squeezed vacuum states, a universal programmable 16‐mode interferometer, and a single photon readout on all outputs with high accuracy, generality, and controllability. The developed system is applied to demonstrate applications in solving NP‐complete problems, manifesting the ability of photonic quantum computing to realize practical applications for conventionally intractable computations. The GBS‐based quantum photonic microprocessor is applied to solve task assignment, Boolean satisfiability, graph clique, max cut, and vertex cover. These demonstrations suggest an excellent benchmarking platform, paving the way toward large‐scale combinatorial optimization.

Laser & Photonics Review•Nov 27, 2023•19 citations
Abstract We consider an atom-cavity system having long-range atomic interactions mediated by cavity modes. It has been shown that quantum simulations of spin models with this system can naturally be used to solve number partition problems. Here, we present encoding schemes for numerous nondeterministic polynomial-time complete (NP-complete) problems, encompassing the majority of Karp’s 21 NP-complete problems. We find a number of such computation problems can be encoded by the atom-cavity system at a linear cost of atom number. There are still certain problems that cannot be encoded by the atom-cavity as efficiently, such as quadratic unconstrained binary optimization (QUBO), and the Hamiltonian cycle. For these problems, we provide encoding schemes with a quadratic or quartic cost in the atom number. We expect this work to provide important guidance to search for the practical quantum advantage of the atom-cavity system in solving NP-complete problems. Moreover, the encoding schemes we develop here may also be adopted in other optical systems for solving NP-complete problems, where a similar form of Mattis-type spin glass Hamiltonian as in the atom-cavity system can be implemented.
We consider an atom-cavity system having long-range atomic interactions mediated by cavity modes. It has been shown that quantum simulations of spin models with this system can naturally be used to solve number partition problems. Here, we present encoding schemes for numerous NP-complete problems, encompassing the majority of Karp's 21 NP-complete problems. We find a number of such computation problems can be encoded by the atom-cavity system at a linear cost of atom number. There are still certain problems that cannot be encoded by the atom-cavity as efficiently, such as quadratic unconstrained binary optimization (QUBO), and the Hamiltonian cycle. For these problems, we provide encoding schemes with a quadratic or quartic cost in the atom number. We expect this work to provide important guidance to search for the practical quantum advantage of the atom-cavity system in solving NP-complete problems. Moreover, the encoding schemes we develop here may also be adopted in other optical systems for solving NP-complete problems, where a similar form of Mattis-type spin glass Hamiltonian as in the atom-cavity system can be implemented.
Cold atoms in an optical cavity have been widely used for quantum simulations of many-body physics, where the quantum control capability has been advancing rapidly in recent years. Here, we show the atom cavity system is universal for quantum optimization with arbitrary connectivity. We consider a single-mode cavity and develop a Raman coupling scheme by which the engineered quantum Hamiltonian for atoms directly encodes number partition problems. The programmability is introduced by placing the atoms at different positions in the cavity with optical tweezers. The number partition problem solution is encoded in the ground state of atomic qubits coupled through a photonic cavity mode, which can be reached by adiabatic quantum computing. We construct an explicit mapping for the 3-SAT and vertex cover problems to be efficiently encoded by the cavity system, which costs linear overhead in the number of atomic qubits. The atom cavity encoding is further extended to quadratic unconstrained binary optimization problems. The encoding protocol is optimal in the cost of atom number scaling with the number of binary degrees of freedom of the computation problem. Our theory implies the atom cavity system is a promising quantum optimization platform searching for practical quantum advantage.
Developing quantum algorithms adaptive to specific constraints of near-term devices is an essential step towards practical quantum advantage. In a recent work [Phys. Rev. Lett. 131, 103601 (2023)], we show cold atoms in an optical cavity can be built as a universal quantum optimizer with programmable all-to-all interactions, and the effective Hamiltonian for atoms directly encodes number partitioning problems (NPPs). Here, we numerically investigate the performance of quantum annealing (QA) and quantum approximate optimization algorithm (QAOA) to find the solution of NPP that is encoded in the ground state of atomic qubits. We find the success probability of the standard QA decays rapidly with the problem size. The optimized annealing path or inhomogeneous driving fields only lead to mild improvement on the success probability. Similarly, the QAOA always gets trapped in a false local minimum, and there is no significant performance improvement as we increase the depth of the quantum circuit. To overcome the difficulty of solving NPPs, we propose an adaptive variational quantum algorithm (VQA) whose ansatz differs from that of the QAOA by releasing the parameter freedom of the NPP Hamiltonian. Through numerical simulations, we find that our adaptive VQA can achieve rather high success probability within very small circuit depth. It is thus worth paying the extra optimization cost of additional parameters for improving performance compared to the QAOA. Therefore, our adaptive VQA provides a promising choice for programmable atom-cavity systems to demonstrate competitive computational power within its quantum coherence time.
Finding a quantum computing method to solve nondeterministic polynomial time (NP)-complete problems is currently of paramount importance in quantum information science. Here we propose and experimentally demonstrate a Rydberg atom approach to program the 3-SAT problem, the prototypical NP-complete problem which allows general programming of all NP problems. We use Rydberg atom graphs, each of which consists of Rydberg atom dimers and trimers coupled with quantum wires in the Rydberg blockade interaction regime, to formulate general Boolean expressions, and obtain their many-body ground states to determine the satisfiabilities of the given 3-SAT problem instances quantum mechanically.
We consider the encoding in Quadratic Unconstrained Binary Optimization (QUBO) of binary comparison constraints, that is, constraints of the form x < y + c, x ≤ y + c, and x = y + c, where x and y are two integer variables and c is an integer constant. For the sake of simplicity, we will consider that x and y are bounded and belong to the same interval {1,..., n}. We will show that such constraints can be encoded without the need of any extra-variable, conversely to the general scheme for linear inequations, which requires between n - 1 and ⌈log2(n - 1)⌉ extra-variables, depending on the encoding chosen for integers. Limiting the number of extra-variables needed in QUBO formulations is important as each Boolean QUBO variable will be implemented as a (logical) qubit on a quantum device and the number of such qubits is limited in quantum annealing systems such as D-Wave machines.
Abstract Quantum computing has grown extensively, especially in system design and development, and the current research focus has gradually evolved from validating quantum advantage to practical applications. In particular, nondeterministic‐polynomial‐time (NP)‐complete problems are central in numerous important application areas. Still, in practice, it is difficult to solved efficiently with conventional computers, limited by the exponential jump in hardness. Here, a quantum photonic microprocessor based on Gaussian boson sampling (GBS) that offers dynamic programmability to solve various graph‐related NP‐complete problems is demonstrated. The system with optical, electrical, and thermal packaging implements a GBS with 16 modes of single‐mode squeezed vacuum states, a universal programmable 16‐mode interferometer, and a single photon readout on all outputs with high accuracy, generality, and controllability. The developed system is applied to demonstrate applications in solving NP‐complete problems, manifesting the ability of photonic quantum computing to realize practical applications for conventionally intractable computations. The GBS‐based quantum photonic microprocessor is applied to solve task assignment, Boolean satisfiability, graph clique, max cut, and vertex cover. These demonstrations suggest an excellent benchmarking platform, paving the way toward large‐scale combinatorial optimization.