Quantum sort

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 [cite conference
author = P. Høyer, J. Neerbek, Y. Shi
title = Quantum complexities of ordered searching, sorting, and element distinctness
booktitle = 28th International Colloquium on Automata, Languages, and Programming
pages = 62--73
year = 2001
url = http://www.springerlink.com/content/25gl9elr5rxr3q6a/
[http://arxiv.org/abs/quant-ph/0102078 Also in quant-ph/0102078]
] , which is already achievable by classical algorithms. Thus, for this task, quantum computers are no better than classical ones. Do note, that in space-bounded sorts, quantum algorithms outperform their classical counterparts [cite conference
last = Klauck
first = Hartmut
title = Quantum Time-Space Tradeoffs for Sorting
url=http://portal.acm.org/citation.cfm?id=780553
booktitle=Proceedings of the thirty-fifth annual ACM symposium on Theory of computing
year=2003
] .

References

ee also

* Bogosort, a sorting algorithm with a joke quantum implementation


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Quantum Leap (TV series) — Quantum Leap Format Procedural drama Created by Donald Bellisario …   Wikipedia

  • Quantum evolution (alternative) — Quantum evolution is the hypothesis that genetic mutation can be adaptive, or directed through quantum effects.McFadden, Johnjoe (2000). [http://www.surrey.ac.uk/qe/quantumevolution.htm Quantum Evolution .] HarperCollins. ISBN 0 00 255948 X; ISBN …   Wikipedia

  • Quantum imaging — [ [http://www.iop.org/EJ/abstract/1464 4266/4/3/372 Quantum Imaging] , L A Lugiato et al 2002 J. Opt. B: Quantum Semiclass. Opt. 4 S176 S183.] , [ [http://www.informaworld.com/openurl?genre=issue issn=0950 0340 volume=53 issue=5 Special Issue on… …   Wikipedia

  • Quantum state — In quantum physics, a quantum state is a mathematical object that fully describes a quantum system. One typically imagines some experimental apparatus and procedure which prepares this quantum state; the mathematical object then reflects the… …   Wikipedia

  • Quantum suicide and immortality — In quantum mechanics, quantum suicide was a thought experiment. It was independently proposed in 1987 by Hans Moravec and in 1988 by Bruno Marchal, and further developed by Max Tegmark in 1998, [Tegmark, Max [http://www.arxiv.org/abs/quant… …   Wikipedia

  • Quantum tic tac toe — In physics, the game of Quantum tic tac toe is a quantum generalization of tic tac toe in which the players moves are quantum superposition of plays in the classical game. The game was invented by Allan Goff of Novatia Labs.QuoteQuantum tic tac… …   Wikipedia

  • Quantum Theology — Infobox Book name = Quantum Theology title orig = translator = author = Diarmuid O Murchu cover artist = country = language = series = subject = Spirituality;Religion genre = Non fiction publisher = Crossroad Publishing Company release date =… …   Wikipedia

  • Interpretation of quantum mechanics — An interpretation of quantum mechanics is a statement which attempts to explain how quantum mechanics informs our understanding of nature. Although quantum mechanics has received thorough experimental testing, many of these experiments are open… …   Wikipedia

  • Timeline of quantum computing — Timeline of quantum computers1970s* 1970 Stephen Wiesner invents conjugate coding.* 1973 Alexander Holevo publishes a paper showing that n qubits cannot carry more than n classical bits of information (a result known as Holevo s theorem or Holevo …   Wikipedia

  • Incompleteness of quantum physics — is the assertion that the state of a physical system, as formulated by quantum mechanics, does not give a complete description for the system, assuming the usual philosophical requirements ( reality , nonlocality , etc.). Einstein, Podolsky, and… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”