Quantum Computing Algorithms
Abstract
When quantum computing was first being invented, it was hoped that it would be able to solve NP-complete problems just through the parallelism of quantum mechanics. Such a scheme would do a brute force search and would not need to use any of the structure of these problems. These hopes were dashed in 1995 by the BBBV paper, this proved that the best improvement that such an unstructured search scheme could provide was a square-root speedup. Based on this result, it is often said that quantum computing algorithms could not possibly solve NP-complete problems. However, it should be emphasized that this is only true if we look at the NP-complete problem as an exhaustive search problem. NP-complete problems have considerable structure and there well might be other more advantageous ways of looking at them. The science of quantum computation is relatively new and there are several unexplored directions. As described in the interim reports and briefly in this report, we have spent some time exploring novel algorithms that make use of the power of quantum mechanics to take advantage of the structured nature of these problems. This report describes the research that I and my collaborators have conducted at Bell Labs over the last five years. The report is organized as follows:
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 16, 2004
- Accession Number
- ADA425567
Entities
People
- Lov K. Grover