題目是這樣:
假設有一個box，裡面有很多Ball (n 個). 有一個是正確答案。其他不是。 你要拿幾次球，才可以拿到正確答案?
這問題根本就沒任何辦法，如果要保證中: 要n次 才能中。
就算randomized 的拿，也沒有任何差別。
Go back to the main quantum computing page
這個問題比很多NP complete更難。因為這些問題，還有某種結構: 比方說3 sat, hamiltonian cycle, maximum cut,.........
都可以暴力解，但都要2^n time.不過神奇的事情是
Grover's algorithm 只需要 開根號 n 的 queries. 就可以做到，或是說 開根號 n 的steps.
最後我們可以證明，開根號n 是optimal的最佳解法。
更general approach 可以看
Adversary Method for Quantum lower bound
No comments:
Post a Comment