Multi-step quantum algorithm for solving the 3-bit exact cover problem
arXiv:1603.05826
Abstract
We present a multi-step quantum algorithm for solving the -bit exact cover problem, which is one of the NP-complete problems. Unlike the brute force methods have been tried before, in this algorithm, we showed that by applying the clauses of the Boolean formula sequentially and introducing non-unitary operations, the state that satisfies all of the clauses can be projected out from an equal superposition of all computational basis states step by step, and the search space is reduced exponentially. The runtime of the algorithm is proportional to the number of clauses, therefore scales polynomial to the size of the problem. Our results indicate that quantum computers may be able to outperform classical computers in solving NP-complete problems.
arXiv commentA reuse of the intermediate state is required in each iteration of the algorithm, this indicates that the algorithm has to be run from the beginning again once a decay of the probe qubit does not occur in an iteration. This will lead to exponential increase of cost for running the algorithm, and does not provide speedup over classical algorithms
References in corpus (10)
- Quantum Mechanics helps in searching for a needle in a haystack
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum algorithms for algebraic problems
- Purification through Zeno-like Measurements
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Quantum Adiabatic Evolution Algorithms with Different Paths
- A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability
- Quantum algorithm for obtaining the eigenstates of a physical system
- Determine Ramsey numbers on a quantum computer
- A quantum algorithm for obtaining the energy spectrum of a physical system without guessing its eigenstates