52620
ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか？
CC BY-SA 4.0
2019-01-23T03:15:01.980
52232
2020-02-07T04:56:55.073
2020-02-07T04:56:55.073
19110
19110
question
アルゴリズム sort 計算量 量子コンピュータ
量子コンピュータによってソートは速くなりますか？
比較ソートに限定した場合、長さ n の配列に対する量子アルゴリズムの時間計算量は Ω(n log n)
になる[1]ので、漸近的には古典アルゴリズムの場合と変わりません。

「比較ソート以外の場合はどうなのか？」「他に制限を課した場合はどうなるのか？」についてはよく知りません。英語版 Wikipedia の ["Quantum
sort"](https://en.wikipedia.org/wiki/Quantum_sort)
によると空間が制限されたときに量子の方が有利になる場合があるようです。

* * *

  1. Høyer, P., Neerbek, J., Shi, Y. (2001). "Quantum complexities of ordered searching, sorting, and element distinctness". 28th International Colloquium on Automata, Languages, and Programming. pp. 62–73. arXiv:[quant-ph/0102078](https://arxiv.org/abs/quant-ph/0102078). doi:[10.1007/3-540-48224-5_29](https://doi.org/10.1007%2F3-540-48224-5_29).
CC BY-SA 4.0
2019-02-07T05:54:54.320
52620
2019-12-10T13:14:51.147
2019-12-10T13:14:51.147
19110
19110
52232
answer