Physics – Quantum Physics
Scientific paper
2002-11-26
Physics
Quantum Physics
17 pages, appears in STOC '03
Scientific paper
We investigate the complexity of sorting in the model of sequential quantum circuits. While it is known that in general a quantum algorithm based on comparisons alone cannot outperform classical sorting algorithms by more than a constant factor in time complexity, this is wrong in a space bounded setting. We observe that for all storage bounds n/\log n\ge S\ge \log^3 n, one can devise a quantum algorithm that sorts n numbers (using comparisons only) in time T=O(n^{3/2}\log^{3/2} n/\sqrt S). We then show the following lower bound on the time-space tradeoff for sorting $n$ numbers from a polynomial size range in a general sorting algorithm (not necessarily based on comparisons): TS=\Omega(n^{3/2}). Hence for small values of S the upper bound is almost tight. Classically the time-space tradeoff for sorting is TS=\Theta(n^2).
No associations
LandOfFree
Quantum Time-Space Tradeoffs for Sorting 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 Quantum Time-Space Tradeoffs for Sorting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Time-Space Tradeoffs for Sorting will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-140787