量子ソート

量子ソートとは、量子コンピュータ上で実行されるソートアルゴリズムのことです。比較ベースの量子ソートアルゴリズムは少なくともステップかかりますが、^[1]これは古典的なアルゴリズムですでに達成可能です。したがって、このタスクでは量子コンピュータは古典的なコンピュータよりも優れているわけではなく、時間計算量に関しては無視する必要があります。ただし、空間制限ソートでは、量子アルゴリズムは古典的なアルゴリズムよりも優れています。^[2] $\Omega (n\log n)$

参考文献

^ Høyer, P.; Neerbek, J.; Shi, Y. (2001). 「順序付き検索、ソート、要素の明確さの量子複雑性」。第 28回国際オートマトン、言語、プログラミング会議。コンピュータサイエンスの講義ノート。第 2076 巻。pp. 62–73。arXiv : quant-ph/0102078。doi : 10.1007 /3-540-48224-5_29。ISBN 978-3-540-42287-7。
^ Klauck, Hartmut (2003). 「ソートのための量子時間空間トレードオフ」。第35回ACMコンピューティング理論シンポジウム議事録。p . 69。arXiv : quant-ph/0211174。doi : 10.1145/ 780542.780553。ISBN 1581136749。

[1] Høyer, P.; Neerbek, J.; Shi, Y. (2001). 「順序付き検索、ソート、要素の明確さの量子複雑性」。第 28回国際オートマトン、言語、プログラミング会議。コンピュータサイエンスの講義ノート。第 2076 巻。pp. 62–73。arXiv : quant-ph/0102078。doi : 10.1007 /3-540-48224-5_29。ISBN 978-3-540-42287-7。

[2] ^ Klauck, Hartmut (2003). 「ソートのための量子時間空間トレードオフ」。第35回ACMコンピューティング理論シンポジウム議事録。p . 69。arXiv : quant-ph/0211174。doi : 10.1145/ 780542.780553。ISBN 1581136749。