質問: ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより時間計算量的に速くなりえますか?
回答: 比較ソートに限定した場合、長さ n の配列に対する量子アルゴリズムの時間計算量は Ω(n log n) になる[1]そうなので、漸近的には古典アルゴリズムの場合と変わらないようです。(今 [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.