Quantum sort

A quantum sort is any sorting algorithm that runs on a quantum computer. Any comparison-based quantum sorting algorithm would take at least $\Omega(n \log n)$ steps,^[1] which is already achievable by classical algorithms. Thus, for this task, quantum computers are no better than classical ones. However, in space-bounded sorts, quantum algorithms outperform their classical counterparts.^[2]

References

↑ P. Høyer, J. Neerbek, Y. Shi (2001). "Quantum complexities of ordered searching, sorting, and element distinctness". 28th International Colloquium on Automata, Languages, and Programming. pp. 62–73. Also in quant-ph/0102078
↑ Klauck, Hartmut (2003). "Quantum Time-Space Tradeoffs for Sorting". Proceedings of the thirty-fifth annual ACM symposium on Theory of computing.

Quantum information science

General

Quantum communication

Quantum algorithms

Quantum complexity theory

Quantum computing models

Decoherence prevention

Physical implementations

Quantum optics	Cavity QED Circuit QED Linear optical quantum computing

Ultracold atoms	Trapped ion quantum computer Optical lattice

Spin-based	Nuclear magnetic resonance QC Kane QC Loss–DiVincenzo QC Nitrogen-vacancy center

Superconducting quantum computing	Charge qubit Flux qubit Phase qubit

Sorting algorithms

Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort

Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Quicksort Stooge sort Bogosort

Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort

Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting

Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort

Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Pigeonhole sort Proxmap sort Radix sort Flashsort

Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network

Hybrid sorts	Block sort Timsort Introsort Spreadsort

Other	Topological sorting Pancake sorting Spaghetti sort

This article is issued from Wikipedia - version of the Wednesday, September 02, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.