In this paper, while using a diagonalization argument in Section $5$, the authors write:

Fix some enumeration over all $poly(n)$-size quantum verifiers $M_{1}, M_{2},...$ which we can do because the number of such machines is countably infinite (by the Solovay-Kitaev theorem [15]). Some of these verifiers may try to decide a language by trivially “hardwiring” its outputs; for example, by returning 1 independent of the input. We start by fixing a unary language $L$ such that no machine $M_{i}$ hardwires the language. We can always do this because there are more languages than $poly(n)$-sized machines.

Maybe I am missing something very basic, but:

  1. Why do we care if some of the verifiers have the output hardwired?
  2. How can we find an $L$, like in the description? Why will this $L$ even be decidable? I know there are more languages than there are Turing machines; but those extra languages aren't decidable.

Your Answer

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

Browse other questions tagged or ask your own question.