I'm searching for a good quantum algorithm to approximate Chaitin's Constant. Any references/resources will do?
Note: This number is uncomputable.
Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.Sign up to join this community
Any quantum algorithm to approximate Chaitin's constant (or any other number) will also yield a classical algorithm to approximate that same number, just by simulating the quantum computer. (It won't be a great classical algorithm, but it's still an algorithm.)
As Chaitin's constant provably doesn't admit such a classical algorithm, it also doesn't admit a quantum algorithm either.