Physics – Quantum Physics
Scientific paper
2010-09-27
Physics
Quantum Physics
23 pages, 5 figures
Scientific paper
For quantum computation, we investigate the conjecture that superposition of macroscopically distinct states is necessary for large quantum speedup. Although this conjecture was supported for a circuit-based quantum computer performing Shor's factoring algorithm (A. Ukena and A. Shimizu, Phys. Rev. A 69, 022301 (2004)), it needs to be generalized in order to apply to wide classes of algorithms and/or other models (such as measurement-based quantum computers). To treat such general cases, we first generalize the indices for superposition of macroscopically distinct states. We then generalize the conjecture, using the generalized indices, in such a way that it is applicable unambiguously to general models if a quantum algorithm achieves exponential speedup. Based on this generalized conjecture, we further extend the conjecture to Grover's quantum search algorithm, whose speedup is large but quadratic. It is shown that this extended conjecture is also correct for Grover's algorithm. Since Grover's algorithm is a representative algorithm for unstructured problems, the present result further supports the conjecture.
Matsuzaki Yuichiro
Shimizu Akira
Ukena Akihisa
No associations
LandOfFree
Necessity of Superposition of Macroscopically Distinct States for Quantum Computational Speedup does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Necessity of Superposition of Macroscopically Distinct States for Quantum Computational Speedup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Necessity of Superposition of Macroscopically Distinct States for Quantum Computational Speedup will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-517718