0
$\begingroup$

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/why 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.
$\endgroup$

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.