Solution to Satisfiability problem by a complete Grover search with trapped ions
arXiv:0811.2905 · doi:10.1088/0953-4075/42/14/145503
Abstract
The main idea in the original Grover search (Phys. Rev. Lett. 79, 325 (1997)) is to single out a target state containing the solution to a search problem by amplifying the amplitude of the state, following the Oracle's job, i.e., a black box giving us information about the target state. We design quantum circuits to accomplish a complete Grover search involving both the Oracle's job and the amplification of the target state, which are employed to solve Satisfiability (SAT) problems. We explore how to carry out the quantum circuits by currently available ion-trap quantum computing technology.
arXiv comment14 pages, 6 figures
References in corpus (35)
- Quantum Mechanics helps in searching for a needle in a haystack
- Elementary gates for quantum computation
- Scalable multi-particle entanglement of trapped ions
- Quantum computation with ions in thermal motion
- Multi-particle entanglement of hot trapped ions
- Quantum Networks for Elementary Arithmetic Operations
- Quantum computers can search rapidly by using almost any transformation
- Optimal Quantum Circuits for General Two-Qubit Gates
- Quantum computers can search arbitrarily large databases by a single query
- Implementation of Grover's Quantum Search Algorithm in a Scalable System
- Fast quantum gates for cold trapped ions
- Precision Measurement of the Lifetime of the 3d D_{5/2} state in 40Ca+
- Multi-bit gates for quantum computing
- Entanglement of Trapped-Ion Clock States
- Simplified quantum logic with trapped ions
- Speed of ion trap quantum information processors
- Decoherence in ion traps due to laser intensity and phase fluctuations
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Adiabatic Quantum Computing for Random Satisfiability Problems
- Light-shift-induced quantum gates for ions in thermal motion
- Quantum Search with Two-atom Collisions in Cavity QED
- Adiabatic quantum algorithms as quantum phase transitions: first versus second order
- Decoherence and fidelity in ion traps with fluctuating trap parameters
- Grover search with pairs of trapped ions
- Behavior of heuristics and state space structure near SAT/UNSAT transition
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- Optimal quantum circuit synthesis from Controlled-U gates
- Simple scheme for two-qubit Grover search in cavity QED
- Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
- Implementation of three-qubit Grover search in cavity QED
- Experimental Implementation of Hogg's Algorithm on a Three-Quantum-bit NMR Quantum Computer
- Simple implementation of a quantum search with trapped ions
- Comment on 'Grover Search with Pairs of Trapped Ions'
- Implementation of many-qubit Grover search with trapped ultracold ions
- Spanning Trees in Random Satisfiability Problems