I'm searching for a good quantum algorithm to approximate Chaitin's Constant. Any references/resources will do?

Note: This number is uncomputable.


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.

| improve this answer | |
  • $\begingroup$ I was hoping to compare runtimes. Hence I wanted an explicit algorithm. $\endgroup$ – More Anonymous Nov 25 '19 at 11:06
  • 2
    $\begingroup$ Run times to achieve... what? And to compare against... what? $\endgroup$ – Niel de Beaudrap Nov 25 '19 at 12:15
  • $\begingroup$ You are right. I was hoping for some sort of algorithm which would guess a digit and tell you approximately where it was in the string of digits. Not sure if it is possible though (I was assuming it existed) math.stackexchange.com/a/57116/430082 $\endgroup$ – More Anonymous Nov 25 '19 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.