質問: ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか?
回答: 比較ソートに限定した場合、長さ n の配列に対する量子アルゴリズムの時間計算量は Ω(n log n) になる[1]ので、漸近的には古典アルゴリズムの場合と変わりません。 「比較ソート以外の場合はどうなのか?」「他に制限を課した場合はどうなるのか?」についてはよく知りません。英語版 Wikipedia の "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. doi:10.1007/3-540-48224-5_29.