
\(\mathsf {MP}.\mathsf {Gen}\) : On input \(1^\lambda \) , \(N\)  and \(C\) , the verifier samples a representation of \(N\)  TCF key pairs by computing \((\mathsf {PK}, \mathsf {SK}) \leftarrow \mathsf {Gen}(1^\lambda , N, C)\) , where \(C\)  is circuit computing \(C(i) = h_i\) . The verifier sends \(\mathsf {PK}\)  to the prover.

\(\mathsf {MP}.\mathsf {Commit}\) : Given \(\mathsf {PK}\)  and its input state \({\psi }_{\mathcal {W}}\) , the prover computes public keys \(\mathsf {pk}_i \leftarrow \mathsf {ExtPk}(\mathsf {PK}, i)\)  for \(1\le i\le N\) . From now on, \(P\)  operates directly on \((\mathsf {pk}_i)\)  and ignores \(\mathsf {PK}\) .
The prover coherently (with respect to \({\psi }\) ) computes a “range superposition”
\(\frac{1}{\sqrt{L^N}} \sum _{\begin{array}{c}x_1, \hdots , x_N \in D \\ y_1, \hdots , y_N \in R \\ w \in \lbrace 0,1\rbrace ^N\end{array}} \left( \alpha _{w} \prod _i \sqrt{p_{\mathsf {pk}_i}(w_i, x_i, y_i)} {w}_{\mathcal {W}} {x_1}_{\mathcal {X}_1} \hdots {x_N}_{\mathcal {X}_N} {y_1}_{\mathcal {Y}_1} \hdots {y_N}_{\mathcal {Y}_N}\right)\) 
where each \(\mathcal {X}_i\)  is an \(\ell (\lambda )\) -qubit register (where \(D \subset \lbrace 0,1\rbrace ^{\ell })\) , and each \(\mathcal {Y}_i\)
has basis \(\lbrace {y} \rbrace _{y \in R}\) . Here, \(p_{\mathsf {pk}}(b, x, y)\)  denotes the probability density of \(y\)  in the distribution \(f_{\mathsf {pk}}(b, x)\) , where \(p_{\mathsf {pk}}(b,x,y) 0\)  for \(x \in \lbrace 0,1\rbrace ^{\ell } \setminus D\) . Following [1]} the honest prover algorithm can efficiently prepare this state up to exponentially small trace distance.
After preparing this state, the prover measures \(\mathcal {Y}_1, \hdots , \mathcal {Y}_N\)  in the standard (\(R\) -)basis and sends the outcome \((y_1,\dots ,y_N)\)  to the verifier.

The verifier sends a uniformly random challenge bit \(c\) . After receiving the prover response, the verifier computes each public key \(\mathsf {pk}_i \leftarrow \mathsf {ExtPk}(\mathsf {PK}, i)\)  and secret key \(\mathsf {sk}_i \leftarrow \mathsf {ExtSk}(\mathsf {SK}, i)\)  in order to evaluate either \(\mathsf {MP}.\mathsf {Test}\)  or \(\mathsf {MP}.\mathsf {Out}\) .

\(\mathsf {MP}.\mathsf {Open}\) : On challenge bit \(c\) , the prover operates as follows.

If \(c=0\) , the prover measures \(\mathcal {W}\otimes \mathcal {X}_1 \otimes \hdots \otimes \mathcal {X}_N\)  in the standard basis and sends the outcome \((b_1, \hdots , b_N, x_1, \hdots , x_N)\)  to the verifier.

If \(c=1\) , the prover instead measures \(\mathcal {W}\otimes \mathcal {X}_1\otimes \hdots \otimes \mathcal {X}_N\)  in the Hadamard basis, returning strings \(d_1, \hdots d_N\) .


\(\mathsf {MP}.\mathsf {Test}\) : Given \((b_1, \hdots , b_N, x_1, \hdots , x_N)\) , the verifier computes (for every \(i\) ) \(\mathsf {Check}(\mathsf {pk}_i, b_i, x_i, y_i)\)  and rejects if any of these checks do not pass.

\(\mathsf {MP}.\mathsf {Out}\) : Given \(d_1, \hdots d_N\) , the verifier outputs \(N\)  bits as follows. For each \(i \in [N]\) :

If \(h_i = 0\) , the verifier ignores \(d_i\) , computes \((b_i, x_i) = \mathsf {Invert}(\mathsf {injective},\mathsf {sk}_i, y_i)\) , and outputs \(b_i\) .

If \(h_i=1\) , the verifier computes the two inverses \(\lbrace (0, x_{0,i}), (1, x_{1,i})\rbrace  \leftarrow \mathsf {Invert}(\mathsf {2}\text{-}\mathsf {to}\text{-}\mathsf {1},\mathsf {sk}_i, y_i)\) . For each \(i\) , the verifier checks whether \(d_i\in \mathsf {Good}_{x_{0,i}, x_{1,i}}\)  (corresponding to a valid equation in the \(i\) th slot), and if so, the verifier outputs \(d_i \cdot (1, x_{0,i}\oplus x_{1,i})\) . If \(d_i \notin \mathsf {Good}_{x_{0,i}, x_{1,i}}\) , the verifier samples a uniformly random bit and outputs it.


