Prospects

• The history of quantum mechanical algorithms is very brief. There are two main approaches that have resulted in descriptions of efficient quantum computational algorithms: the first is estimates of periodicity that resulted in the factorization algorithm, and the second is amplitude amplification that has led to Grover's quantum search and related algorithms.
• Over the past 70 or 80 years, physicists have observed various quantum mechanical phenomena that lead to puzzling and even apparently paradoxical results. Most of these still remain to be investigated from a quantum computing perspective.
• One interesting question is how slight difference in the laws of quantum mechanics might affect these issues. Some interesting work by Abrams et al. shows that if there was even the slightest amount of nonlinearity in quantum mechanics, it would be possible to modify the amplitude amplification scheme of Grover's quantum search algorithm to obtain an efficient algorithm solving the NP-complete satisfiability problem. However, most people believe that such nonlinearity probably does not exist because it would also lead to faster-than-light communication, noncausality, and other violations of fundamental physical principles ...