Necessity of Superposition of Macroscopically Distinct States for Quantum Computational Speedup

Abstract

For quantum computation, we investigate the conjecture that the superposition of macroscopically distinct states is necessary for a 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. A69 (2004) 022301], it needs to be generalized for it to be applicable to a large class of algorithms and/or other models such as measurement-based quantum computers. To treat such general cases, we first generalize the indices for the superposition of macroscopically distinct states. We then generalize the conjecture, using the generalized indices, in such a way that it is unambiguously applicable to general models if a quantum algorithm achieves exponential speedup. On the basis of 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. Since Grover's algorithm is a representative algorithm for unstructured problems, the present result further supports the conjecture.

18 pages, 5 figures. Fixed typos throughout the manuscript. This version has been published

References in corpus (10)

• Entanglement versus Correlations in Spin Systems
• Quantum Brachistochrone
• Measurement-based quantum computation beyond the one-way model
• Characterizing the entanglement of symmetric many-particle spin-1/2 systems
• Universality of Entanglement and Quantum Computation Complexity
• Detection of Macroscopic Entanglement by Correlation of Local Observables
• Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
• Macroscopic entanglement of many-magnon states
• Entangled Quantum States Generated by Shor's Factoring Algorithm
• Visualization of superposition of macroscopically distinct states

Cited by in corpus (7)

• Macroscopic quantum states: measures, fragility and implementations
• Does a large quantum Fisher information imply Bell correlations?
• Quantum metrology with generalized cat states
• Is macroscopic entanglement a typical trait of many-particle quantum states?
• Conversion of Thermal Equilibrium States into Superpositions of Macroscopically Distinct States
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Electron dynamics induced by quantum cat-state light