Quantum State Obfuscation from Classical Oracles

James<EMAIL_ADDRESS>UC Berkeley Zvika<EMAIL_ADDRESS>Weizmann Institute of Science Vinod<EMAIL_ADDRESS>
A major unresolved question in quantum cryptography is whether it is possible to obfuscate arbitrary quantum computation. Indeed, there is much yet to understand about the feasibility of quantum obfuscation even in the classical oracle model, where one is given for free the ability to obfuscate any classical circuit.

In this work, we develop a new array of techniques that we use to construct a quantum state obfuscator, a powerful notion formalized recently by Coladangelo and Gunn (arXiv:2311.07794) in their pursuit of better software copy-protection schemes. Quantum state obfuscation refers to the task of compiling a quantum program, consisting of a quantum circuit $C$ with a classical description and an auxiliary quantum state $\ket{\psi}$, into a functionally-equivalent obfuscated quantum program that hides as much as possible about $C$ and $\ket{\psi}$. We prove the security of our obfuscator when applied to any pseudo-deterministic quantum program, i.e. one that computes a (nearly) deterministic classical input / classical output functionality. Our security proof is with respect to an efficient classical oracle, which may be heuristically instantiated using quantum-secure indistinguishability obfuscation for classical circuits.

Our result improves upon the recent work of Bartusek, Kitagawa, Nishimaki and Yamakawa (STOC 2023) who also showed how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, but only ones with a completely classical description. Furthermore, our result answers a question of Coladangelo and Gunn, who provide a construction of quantum state indistinguishability obfuscation with respect to a quantum oracle, but leave the existence of a concrete real-world candidate as an open problem. Indeed, our quantum state obfuscator together with Coladangelo-Gunn gives the first candidate realization of a “best-possible” copy-protection scheme for all polynomial-time functionalities.

Our techniques deviate significantly from previous works on quantum obfuscation. We develop several novel technical tools which we expect to be broadly useful in quantum cryptography. These tools include a publicly-verifiable, linearly-homomorphic quantum authentication scheme with classically-decodable ZX measurements (which we build from coset states), and a method for compiling any quantum circuit into a "linear + measurement" ($\LM$) quantum program: an alternating sequence of CNOT operations and partial ZX measurements.

§ INTRODUCTION

Whether white-box access to programs is more powerful than black-box access is a fundamental question in computer science. This question motivates the study of program obfuscation, the task of converting a given program $\mathcal{P}$ into an obfuscated program $\hat{\mathcal{P}}$ that preserves functionality (i.e. the input-output behavior of $\mathcal{P}$), yet hides all other information about $\mathcal{P}$. Indeed, the previous decades have produced exciting research in cryptography solving several foundational questions about program obfuscation, including: which notions of obfuscation are possible and which aren't <cit.>; which ones are useful and to what extent <cit.>; and of course, how to construct secure program obfuscators under well-founded hardness assumptions <cit.>. The study of program obfuscation has given us sophisticated cryptographic primitives such as witness encryption <cit.> and functional encryption <cit.>, and it has shed new light on foundational complexity-theoretic questions <cit.>.

Developments in quantum information, computation, and cryptography <cit.> bring to fore a similarly foundational question:

Is it possible to obfuscate quantum computation, and to what extent?

Despite recent progress, there remains much to understand about the feasibility of quantum obfuscation, even in a world where one has the aid of a classical oracle, equivalently a world where ideal obfuscation of classical circuits comes for free.

The strongest known positive result on obfuscating quantum functionalities is from the recent work of Bartusek, Kitagawa, Nishimaki and Yamakawa <cit.>, who showed how to obfuscate the class of classically described pseudo-deterministic quantum circuits in the classical oracle model, under the learning with errors (LWE) assumption. (For a description of other related work, see Section <ref>.) A deterministic quantum circuit is one that implements a classical, deterministic map $x \to Q(x)$. A pseudo-deterministic circuit is nearly deterministic, i.e. its output on every (classical) input $x$ is some (classical) $y$ with all but negligible probability, e.g. the Shor circuit for factoring. In the classical oracle model, the obfuscated circuit as well as the (possibly adversarial) evaluator have oracle access to an efficiently computable classical function sampled by the obfuscator.[Importantly, the actual description of this function is not necessarily revealed to the evaluator / adversary.]

§.§ Our Results

In this work, we present a new array of techniques that we use to construct a quantum state obfuscation scheme, an efficient compiler that converts a quantum program, consisting of a quantum circuit $C$ as well as an auxiliary quantum input $\ket{\psi}$, into an  obfuscated quantum program that preserves functionality, but hides everything else. In a nutshell, our main result constructs an ideal quantum state obfuscator for pseudo-deterministic functionalities with respect to an efficient classical oracle. The class of circuits we obfuscate is strictly more general than those obfuscated by <cit.>, which have a purely classical description (see <ref> for a more detailed comparison). Moreover, our security is unconditional[Technically, we only achieve unconditional security if we allow our oracles to use a true random oracle as a sub-routine. If we insist on the efficiency of the oracles, and thus instantiate the random oracle with a pseudo-random function, then we must assume the existence of a quantum-secure one-way function.] while <cit.> additionally relied on the LWE assumption (in the classical oracle model).

There exists a quantum state obfuscator for the class of pseudo-deterministic quantum programs achieving the notion of ideal obfuscation (Definition <ref>) in the classical oracle model.

The notion of quantum state obfuscation was recently conceptualized and defined by Coladangelo and Gunn <cit.> in their pursuit of better software copy-protection schemes <cit.>. They show how a quantum state indistinguishability obfuscator can be used to construct a “best-possible” copy-protection scheme, i.e. they show a scheme to copy-protect any classical function that can be copy-protected at all! Their observation is that if there exists some (as yet unknown) copy-protection scheme for a classical (deterministic) function $x \to Q(x)$ that produces an unclonable quantum program $(\ket{\psi},C)$, then a quantum state obfuscation of $Q$ is just as good a copy-protection scheme. Indeed, this follows from the fact that the obfuscation of $Q$ is indistinguishable from an obfuscation of $(\ket{\psi},C)$.

However, they leave the existence of quantum state indistinguishability obfuscation as an open question, only providing a construction with respect to a quantum oracle that has no known (even heuristic) real-world instantiation.

Our main result (Theorem <ref>) answers the open question from <cit.>, providing a construction of quantum state obfuscation with respect  to a classical oracle. The oracle can be heuristically instantiated using a candidate quantum-secure indistinguishability obfuscation for classical circuits (e.g. <cit.>), thus providing the first concrete evidence that quantum state (indistinguishability) obfuscation is achievable. That is, while we don't currently have a proof in the plain model, it is plausible to conjecture the following.

Instantiating our scheme with one of the above candidate quantum-secure indistinguishability obfuscators for classical circuits yields a secure quantum state indistinguishability obfuscator.

Then, following Coladangelo-Gunn, we obtain the first candidate realization of a “best-possible” copy-protection scheme for all polynomial-time programs.

Assuming the above conjecture, there exists a best-possible copy-protection scheme for all polynomial-time classical programs.

We note that the prior work of <cit.> also obtains results on general-purpose copy-protection by working in the classical oracle model, and we describe the advantages of our approach (combined with <cit.>) in <ref>.

Our techniques deviate significantly from previous works on quantum obfuscation. For example, while previous work <cit.> builds from the idea of obfuscating the verifier for a classical verification of quantum computation scheme, we directly perform verifiable computation on an authenticated and encrypted input. Our construction is comfortingly reminiscent of Yao's classical garbled circuits construction <cit.> (in fact, the free-XOR variant <cit.>) which has had a tremendous array of applications in cryptography. We give an overview of our techniques in <ref>, and provide more discussion on how they compare to prior work in <ref>.

On the classical oracle model. Before proceeding, a word is in order about achieving results in the classical oracle model. First, a result in this model can be interpreted as reducing the problem of obfuscating quantum functionalities to classical functionalities. Indeed, instantiating the (efficiently implementable) oracle by its indistinguishability obfuscation (iO) gives us a heuristically secure construction in the plain model. Furthermore, by the “best-possible” security guarantee of iO, if there exists a secure implementation of the oracle in the plain model, iO is one such.

Secondly, results in the classical oracle model have historically been important harbingers of subsequent research that showed analogous results without the aid of an oracle. For example, quantum money <cit.> was first achieved in a classical oracle model before it was de-oracle-ized <cit.>; and copy-protection for unlearnable programs was first achieved in a quantum oracle model <cit.> before it was achieved in a classical oracle model <cit.> and later without oracles, for certain classes of functionalities (e.g. <cit.>).

§.§ Related Work

Alagic and Fefferman <cit.> presented definitions for obfuscating quantum circuits (and obfuscating classical circuits using quantum states). Their results, as well as those of Alagic, Brakerski, Dulek and Schaffner <cit.> are negative. The latter, for example, shows that virtual black-box (VBB) obfuscation of classical circuits, even with the aid of quantum information, is impossible.

Broadbent and Kazmi <cit.> showed how to obfuscate quantum circuits that have only a few non-Clifford gates. In their construction, the size of the obfuscated circuit blows up exponentially with the number of $T$ gates.
Bartusek and Malavolta <cit.> showed how to achieve indistinguishability obfuscation of null quantum circuits and, most related to our work, Bartusek, Kitagawa, Nishimaki and Yamakawa <cit.> showed how to obfuscate general pseudo-deterministic quantum circuits (with a classical description) in the classical oracle model.  Finally, Coladangelo and Gunn <cit.>, in a concurrent work, define the notion of quantum state (indistinguishability) obfuscation, show applications of this notion to software copy-protection, and construct a quantum state indistinguishability obfuscator in the quantum oracle model. We summarize these results, along with our contribution, in <ref>.

Work     Obfuscator
input     Obfuscator
output     Program
input     Program
output     Program class     Assumption/
model     Result

<cit.>     Classical     Quantum*     Quantum     Quantum     Unitaries w/ logarithmically
many non-Clifford gates     iO for classical
circuits     iO

<cit.>     Classical     Classical     Quantum*     Classical     Null circuits     Classical oracle
model + LWE     iO

<cit.>     Classical     Quantum     Classical     Classical     (Pseudo)-Deterministic
circuits     Classical oracle
model + LWE     VBB

<cit.>     Quantum     Quantum     Classical     Classical     Deterministic circuits     Quantum oracle
model     iO

This work     Quantum     Quantum     Classical     Classical     (Pseudo)-Deterministic
circuits      Classical oracle
model     Ideal

Summary of work on quantum obfuscation. In <cit.>, the obfuscator outputs a quantum state that can only be used to evaluate the program on one input, and then is potentially destroyed. In <cit.>, the obfuscated program can be run on quantum inputs, but requires multiple copies of the quantum input. The last column refers to the definition of obfuscation that is actually achieved in each work: iO is indistinguishability obfuscation, and VBB is virtual black-box obfuscation. We note that VBB and the stronger notion of ideal obfuscation are morally very similar, and <cit.> could also likely be shown to be an ideal obfuscator. Finally, we note that while achieving the notion of VBB/ideal obfuscation is only possible in the oracle model, the results that are in the classical oracle model yield heuristic candidates for iO in the plain model.

§ TECHNICAL OVERVIEW

During this overview, we'll slowly build up to our construction of quantum state obfuscation, highlighting the main ideas along the way. But first, it may be useful to convey a high level feel for the construction. To obfuscate a quantum program $(\ket{\psi},C)$ that implements the computation $x \to Q(x)$, we first encode the state
$$\ket*{\widetilde{\psi}} \gets \Enc_k\left(\ket{\psi}\right)$$

using a novel quantum authentication scheme (QAS) that we design with particular properties in mind. Next, we compile $C$ into what we call a "linear + measurement", or $\LM$, quantum program.  Such programs consist solely of operations that can be performed on data authenticated with our QAS. Finally, we prepare a sequence of classical oracles $\sF_1,\dots,\sF_t,\sG$, where $t$ is the number of "measurement layers" in the $\LM$ quantum program. The oracles $\sF_1,\dots,\sF_t$ are designed to help the evaluator implement an encrypted sequence of adaptive measurements. They output random labels encoding the measurement results, which are then fed into downstream oracles. The oracle $\sG$ is designed to return the output $Q(x)$ if the evaluation was performed honestly. The final obfuscation then consists of the state $\ket*{\widetilde{\psi}}$ and the oracles $\sF_1,\dots,\sF_t,\sG$. We will describe each of these pieces and how they fit together in more detail.

We begin this technical overview by presenting our quantum authentication scheme (<ref>). Next, we discuss the notion of $\LM$ quantum programs, and describe a compiler that writes any quantum program as an $\LM$ quantum program (<ref>). Next, we show how to use these building blocks to construct a garbling scheme and then a full-fledged obfuscation scheme for quantum computation (<ref>), and mention a couple of key ideas behind proving security. We defer a more detailed proof overview to <ref>. We conclude with a discussion and open problems (<ref>).

§.§ Quantum Authentication from Random Subspaces

Encode-encrypt authentication. Our starting point is the notion of an “encode-encrypt” authentication scheme, as defined by Broadbent, Gutoski and Stebila <cit.>. Such schemes are parameterized by a family of CSS codes $\mathscr{C}$, and operate as follows. To encode a qubit $\ket{\psi}$, sample a random code $C \gets \mathscr{C}$ from the family, sample a quantum one-time pad key $(x,z)$, and output the “encoded-and-encrypted” state $X^x Z^x C\ket{\psi}$. As discussed by <cit.>, various choices of the code family give rise to popular quantum authentication schemes (QAS), e.g., the polynomial scheme used for multi-party quantum computation <cit.> and verifiable delegation <cit.>, and the trap code used for quantum one-time programs <cit.> and zero-knowledge proofs for QMA <cit.>.

Our instantiation. A crucial aspect of obfuscation that does not arise in these other settings is the need to preserve security when we allow the adversary to access the verifier of the authentication scheme an a-priori unbounded number of times. Indeed, the oracles released as part of our obfuscation scheme include subroutines that perform checks on authenticated data, and hence implicitly give the adversary reusable access to the verifier. This requirement of “public-verifiability” is not always satisfied by encode-encrypt schemes: for example, the trap code is completely insecure in this setting, as it is possible to learn the location of the traps via repeated queries to the verifier.

While certain flavors of public-verifiability have been considered previously in the quantum authentication literature (e.g. <cit.>), we find that a particularly simple instantiation of the encode-encrypt framework suffices for us: sample a random subspace $S$, a random shift $\Delta$, and use the CSS code defined by the isometry $E_{S,\Delta}$ that maps $\ket{0} \to \ket{S}, \ket{1} \to \ket{S+\Delta}$.[Here, we use the standard subspace state notation: for an (affine) subspace $S$, $\ket{S} \propto \sum_{s \in S}\ket{s}$.] That is, to encode an $n$-qubit state $\ket{\psi}$, sample a key $k=(S,\Delta,x,z)$ where $S$ is a $\secp$-dimensional subspace of $\bbF_2^{2\secp+1}$, $\Delta \in \bbF_2^{2\secp+1} \setminus S$, and $x,z \in \{0,1\}^{n \cdot (2\secp+1)}$, and output
\[\ket*{\widetilde{\psi}} = X^x Z^z E_{S,\Delta}^{\otimes n}\ket{\psi} \coloneqq \Enc_k(\ket{\psi}).\]

Beyond satisfying a natural notion of public-verifiability (which will be discussed below), the resulting QAS satisfies the following desirable properties: (i) linear-homomorphism, and (ii) classically-decodable standard and Hadamard basis measurements (that is, a classical machine can decode the results of standard and Hadamard basis measurements performed on authenticated data).  We note that these latter properties are in fact endemic to encode-encrypt schemes (see discussion in <cit.>), but we confirm them here for completeness.

Useful properties. First, since $S$ is a subspace, one can confirm that CNOTs are transversal for this scheme as long as the same $(S,\Delta)$ is used to encode each qubit. That is, applying $2\secp+1$ CNOT gates qubit-wise to an encoding of $b_1$ and $b_2$ yields

\[X^{x_1,x_2}Z^{z_1,z_2}\ket{S+ b_1 \cdot \Delta}\ket{S + b_2 \cdot \Delta} \to X^{x_1,x_1 \oplus x_2}Z^{z_1 \oplus z_2,z_2}\ket{S + b_1 \cdot \Delta}\ket{S + (b_1 \oplus b_2) \cdot \Delta}~,\]

which is indeed an encoding of the output of the CNOT operation using quantum one-time pad keys $(x_1,z_1\oplus z_2)$ and $(x_1 \oplus x_2, z_2)$. Thus, an evaluator can apply any sequence of CNOT gates, which we refer to as a "linear"[Of course, all quantum gates are linear with respect to the ambient Hilbert space of exponential dimension. Here, linearity specifically refers to the fact that any sequence of CNOT gates applies a linear function over $\bbF_2$ to each standard basis vector.] function, to authenticated data, as long as the decoder performs the analogous updates to their one-time pad keys.

Next, we note that standard basis measurements of an encoded qubit $X^xZ^z(\alpha\ket{S} + \beta\ket{S+\Delta})$ can be decoded classically. Indeed, any vector in $S+x$ can be interpreted as a 0, while any vector in $S+\Delta+x$ can be interpreted as a 1.

Finally, we check that the results of a Hadamard basis measurement can also be decoded classically. To do so, we'll define the "primal" codespace $S_\Delta \coloneqq S \cup (S+\Delta)$, and define the "dual" codespace to consist of  $\widehat{S} \coloneqq S_\Delta^\bot$ and  $\widehat{S} + \widehat{\Delta}$, where $\widehat{\Delta}$ is such that
$$\widehat{S}_{\widehat{\Delta}} \coloneqq \widehat{S} \cup (\widehat{S} + \widehat{\Delta}) = S^\bot~.$$

Then, it is not hard to check and confirm that
\[H^{\otimes (2\secp+1)}X^xZ^z\left(\alpha\ket{S} + \beta\ket{S+\Delta}\right) = X^z Z^x\left(\frac{\alpha+\beta}{\sqrt{2}}\ket*{\widehat{S}} + \frac{\alpha-\beta}{\sqrt{2}}\ket*{\widehat{S}+\widehat{\Delta}}\right).\]
Thus, any vector in $\widehat{S} + z$ can be interpreted as a 0 measurement result in the Hadamard basis, and any vector in $\widehat{S} + \widehat{\Delta}+z$ can be interpreted as a 1 measurement result in the Hadamard basis.

Reusable security. Now we turn to the security of our scheme. Intuitively, we want to capture the fact that no adversary can successfully tamper with authenticated data, even given the ability to verify authenticated data. In more detail, given an authentication key $k = (S,\Delta,x,z)$, where $x = (x_1,\dots,x_n), z= (z_1,\dots,z_n)$, we define the following classical functionalities, which are parameterized by the key $k$ and a choice of bases $\theta \in \{0,1\}^n$.

* $\Dec_{k,\theta}(\widetilde{v})$: On input a tuple of vectors $\widetilde{v}$ parsed as $(\widetilde{v}_1,\dots,\widetilde{v}_n)$, the decoding algorithm defines $v \in \{0,1\}^n$ as follows. For each $i \in [n]$:

\[\text{if } \theta_i = 0: v_i = \begin{cases}0 \text{ if } \widetilde{v}_i \in S + x_i \\ 1 \text{ if } \widetilde{v}_i \in S + \Delta+ x_i \\ \bot \text{ otherwise}\end{cases} ~~~~~ \text{if } \theta_i = 1: v_i = \begin{cases}0 \text{ if } \widetilde{v}_i \in \widehat{S}+ z_i \\ 1 \text{ if } \widetilde{v}_i \in \widehat{S} + \widehat{\Delta}+ z_i \\ \bot \text{ otherwise}\end{cases}.\]
If $v_i = \bot$ for some $i$, then output $\bot$, and otherwise output $v$.

* $\Ver_{k,\theta}(\widetilde{v})$: On input a tuple of vectors $\widetilde{v}$ parsed as $(\widetilde{v}_1,\dots,\widetilde{v}_n)$, the verification algorithm defines $v \in \{\top,\bot\}^n$ as follows.

\[\text{if } \theta_i = 0: v_i = \begin{cases}\top \text{ if } \widetilde{v}_i \in S_\Delta + x_i \\ \bot \text{ otherwise}\end{cases} ~~~~~ \text{if } \theta_i = 1: v_i = \begin{cases}\top \text{ if } \widetilde{v}_i \in \widehat{S}_{\widehat{\Delta}} + z_i \\ \bot \text{ otherwise}\end{cases}.\]
If $v_i = \bot$ for some $i$, then output $\bot$, and otherwise output $\top$.

That is, the verification algorithm just checks whether its inputs lie in the primal (resp. dual) codespace, while the decoding algorithm additionally computes the logical bits encoded by its inputs. We show that for any state $\ket{\psi}$, sequence of measurement bases $\theta \in \{0,1\}^n$, and adversarial measurement $\mathsf{Adv}$ that samples

\[\widetilde{v} \gets \Adv^{\Ver_{k,\cdot}(\cdot)}\left(X^x Z^z E_{S,\Delta}^{\otimes n}\ket{\psi}\right),\]
the decoded value $v \gets \Dec_{k,\theta}(\widetilde{v})$ is either $\bot$, or its distribution is very close in total variation distance to the distribution that results from directly measuring $\ket{\psi}$ in the bases $\theta$.

In fact, we also consider the possibility that the adversary is supposed to homomorphically apply some  sequence of CNOT gates (that is, a linear function $L$) to the authenticated data before measuring. Thus, in full generality we also parameterize the decoding $\Dec_{k,\theta,L}$ and verification $\Ver_{k,\theta,L}$ algorithms by a linear function $L$, which determines an updated sequence of one-time pad keys $(x_{L,1},\dots,x_{L,n}), (z_{L,1},\dots,z_{L,n})$ to be used in the decoding and verification.

A word on the proof of security. Our proof combines two useful tricks from the literature: superspace sampling (<cit.>) and the Pauli twirl <cit.>. Briefly, our first step is to sample random (say, $(3\secp/2 +1)$-dimensional) superspaces $R \supset S_\Delta$, $\widehat{R} \supset \widehat{S}_{\widehat{\Delta}}$ and use $(R,\widehat{R})$ in lieu of $(S_\Delta,\widehat{S}_{\widehat{\Delta}})$ in the definition of the oracle $\Ver_{k,\cdot,\cdot}(\cdot)$. Since $R$ and $\widehat{R}$ are random and small enough compared to the ambient space, the adversary cannot notice this change except with negligible probability. Next, we imagine sampling each one-time pad vector in two parts: for $x_i$ we sample an $x_{i,R} \gets R$ and an $x_{i,\co(R)} \gets \co(R)$, where $\co(R)$ is a set of coset representatives of $R$, and define $x_i = x_{i,R} + x_{i,\co(R)}$, and for $z_i$ we sample a $z_{i,\widehat{R}} \gets \widehat{R}$ and a $z_{i,\co(\widehat{R})} \gets \co(\widehat{R})$, and define $z_i = z_{i,\widehat{R}} + z_{i,\co(\widehat{R})}$. Finally, we consider the following experiment:

* Sample $R,\widehat{R},\{x_{i,\co(R)},z_{i,\co(\widehat{R})}\}_{i \in [n]}$ and give this information to the adversary in the clear. Note that this is now sufficient to implement the oracle $\Ver_{k,\cdot,\cdot}(\cdot)$.

* Sample random $S,\Delta$ such that $\widehat{R}^\bot \subset S \subset S_\Delta \subset R$ and $\{x_{i,R},z_{i,\widehat{R}}\}_{i \in [n]}$ to complete the description of the authentication key $(S,\Delta,x,z)$. Send $X^xZ^zE_{S,\Delta}^{\otimes n}\ket{\psi}$ to the adversary, who mounts its attack.

At this point, we use the Pauli twirl over the space in between $\widehat{R}^\bot$ and $R$ to show that any adversarial operation can be decomposed into a fixed linear combination of Pauli attacks. To conclude, we use the randomness of $S,\Delta$ to show that any fixed Pauli attack will either be rejected with overwhelming probability or act as the identity on the encoded qubit, which completes the proof. See <ref> for the full details of our definitions, construction, and security proofs.

§.§ Linear + Measurement Quantum Programs

Next, we discuss our quantum program compiler. We start with any quantum circuit written using the $\{\CNOT,H,T\}$ universal gate set, where $H$ is the Hadamard gate, and $T$ applies a phase of $e^{i\pi/4}$. With the help of magic states, we compile the circuit into an alternating sequence of layers of CNOT gates (i.e. linear functions) and partial standard and Hadamard basis measurements, which we refer to as "ZX measurements".[Here, ZX is not meant to denote the composition of the Z and X operators, rather, it is meant as a shorthand for “standard + Hadamard basis”.] We refer to the resulting program as a linear + measurement ($\LM$) quantum program. We note that the measurements are in fact partial in two aspects: (i) they may only operate on a subset of the qubits, and (ii) the measurement operators are projectors with rank potentially greater than 1. Furthermore, we allow the measurements to be adaptive, that is, their description may depend on previous measurement results (and the classical input to the computation).

More specifically, our goal will be to write each of the $H$ and $T$ gates as a sequence of CNOT gates, ZX measurements, and Pauli corrections derived from these measurement results. Then, the Pauli corrections can be commuted past future CNOT gates using the update rule $(x_1,z_1),(x_2,z_2) \to (x_1,z_1 \oplus z_2),(x_1 \oplus x_2,z_2)$, and incorporated into the description of future ZX measurements.

Handling the $H$ gate. Following <cit.>, we prepare the two-qubit magic state
$$\ket{\phi_H} \propto \ket{00} + \ket{01} + \ket{10} - \ket{11},$$
and perform the Hadamard gate as shown in <ref> (fig:H), using one CNOT gate and Pauli corrections derived from a standard basis and a Hadamard basis measurement. As remarked in <cit.>, it might seem strange at first that we are replacing a Hadamard gate with a circuit that nonetheless performs a Hadamard basis measurement. However, in our setting this does represent real progress: our authentication scheme does not support applying Hadamard gates directly to authenticated data,[At least, while preserving its linear-homomorphism. Applying a Hadamard gate transversally to authenticated data would result in an encoding with respect to the dual subspace, which would no longer support transversal CNOTs with data encoded using the primal subspace.] but does support the decoding of Hadamard basis measurements.

Handling the $T$ gate. As we show on the bottom left of <ref> (fig:T), the $T$ gate can be implemented using the two magic states
$$ \ket{\phi_T} \propto \ket{0} + e^{i\pi /4} \ket{1} \hspace{.2in} \mbox{and} \hspace{.2in} \ket{\phi_{PX}} \propto i\ket{0} + \ket{1}, $$
a CNOT gate, a classically controlled CNOT gate, and Pauli corrections.

Unfortunately, controlled CNOT is a "multi-linear" operation that we don't know how to directly implement on data authenticated with our authentication scheme. Therefore, taking inspiration from the "encrypted CNOT" operation introduced in <cit.>,[Those familiar with <cit.>'s encrypted CNOT may notice the parallels: in <cit.>'s setting, these two measurements correspond to the two types of “claws” generated by the lattice-based encryption of $c$.] we replace the controlled CNOT operation with a projective measurement $\Gamma_c$ controlled on the classical control bit $c$, where

* $\Gamma_0 = \{\ketbra{00}{00} + \ketbra{10}{10}, \ketbra{01}{01} + \ketbra{11}{11}\}$. That is, it measures its second input in the standard basis and has no effect on its first input.

* $\Gamma_1 = \{\ketbra{00}{00} + \ketbra{11}{11}, \ketbra{01}{01} + \ketbra{10}{10}\}$. That is, it measures the XOR of its two inputs, partially collapsing both.

Note that $\Gamma_1$ can roughly be seen as applying CNOT “out of place”, writing the result to a third register, and then measuring it. We also remark that both of these measurements are diagonal in the standard basis, and thus can be performed on our authenticated data.

In the implementation of the $T$ gate shown on the bottom left of <ref>, the $c$-CNOT operation is applied to the two magic states, followed by a measurement of the second magic state wire in the standard basis, and finally a $Z$ correction to the first magic state wire conditioned on both $c$ and the measurement outcome. One can show that the result of these operations is identical to what is shown on the bottom right of <ref>: measure $\Gamma_c$ on the two magic state wires, then measure the second magic state wire in the Hadamard basis, and finally apply a $Z$ correction to the first magic state wire conditioned on both $c$ and the XOR of the two measurement results. We make this precise in the proof of <ref>, showing that our $\Gamma_c$-based implementation of the $T$ gate works as expected.

Formalizing $\LM$ quantum programs. By combining these observations, we are able to specify any quantum program with $t$ many $T$ gates using an $n$-qubit state $\ket{\psi}$ (which in particular includes all of the necessary magic state) along with a sequence
\[L_1,M_{\theta_1,f_1^{(\cdot)}},\dots,L_t,M_{\theta_t,f_t^{(\cdot)}},L_{t+1},M_{\theta_{t+1},g^{(\cdot)}}\]

* Each $L_i$ is a sequence of CNOT gates.

* Each $M_{\theta_i,f_i^{(\cdot)}}$  (and $M_{\theta_i,g^{(\cdot)}}$) describes a partial ZX measurement in the following way:

* $\theta_i \in \{0,1,\bot\}^n$ defines a partial set of measurement bases. We define $\MS_{i,0} \coloneqq \{j : \theta_{i,j} = 0\}$ to be the set of registers measured in the standard basis and $\MS_{i,1} \coloneqq \{j : \theta_{i,j} = 1\}$ to be the set of registers measured in the Hadamard basis, and define $\MS_i \coloneqq (\MS_{i,0},\MS_{i,1})$ to be the total set of registers on which the $i$'th measurement is performed.

* Each $f_i^{(\cdot)}$ is a function that assigns measurement outcomes to basis states. The superscript indicates that its description may depend on previously generated information, i.e. the classical input $x$ to the computation and previous measurement results.

* To be precise, $M_{\theta_i,f_i^{(\cdot)}}$ can be described by the following measurement operators:

\[\left\{H^{\MS_{i,1}}\left(\sum_{m : f_i^{(\cdot)}\left(m_{\MS_i}\right) = y}\ketbra{m}{m}\right)H^{\MS_{i,1}}\right\}_y,\]
where $H^{\MS_{i,1}}$ applies a Hadamard gate to each qubit in the set $\MS_{i,1}$, and $m_{\MS_i}$ is the substring of $m$ consisting of the indices in $\MS_i$.

Thus, we have written our quantum program as an alternating sequence of linear operations and partial ZX measurements. We formalize this notion of an "$\LM$ quantum program" in <ref>, and provide an example diagram of an $\LM$ quantum program in <ref>.

However, looking ahead, it will be convenient to apply our obfuscator not to a completely arbitrary $\LM$ quantum program, but rather to an $\LM$ quantum program that satisfies a particular structural property. This property is described in <ref>, and satisfied by $\LM$ quantum programs output by our compiler described above. In order to formalize such programs (and our obfuscator), it will be necessary to introduce some further notation. For the purpose of this technical overview, we will introduce the notation and show how it is applied to the concrete compiler described above, but defer further details and a formalization of the property given by <ref> to the body.

It may be helpful to refer to <ref> (our implementation of the $T$ gate) and <ref> (the example $\LM$ quantum program) while reading what follows. We begin by specifying (disjoint) sets $V_1,\dots,V_{t+1}$ and (disjoint) sets $W_1,\dots,W_t$ with the following properties.

* $\MS_1 = (V_1,W_1), \MS_2 = (V_1,V_2,W_2), \dots, \MS_t = (V_1,\dots,V_t,W_t), \MS_{t+1} = (V_1,\dots,V_{t+1}) = [n].$

* $V_i$ are the set of registers that are fully collapsed in the standard or Hadamard basis by the $i$'th measurement. Concretely, $V_i$ consists of the 3rd wire of the $(i-1)$'th $T$-gate circuit (<ref>), 1st and 2nd wires of any $H$-gate circuit (<ref>) in the $i$'th layer, and 1st wire of the $i$'th $T$-gate circuit (<ref>).

* $W_i$ are the set of registers that are partially collapsed by the $i$'th measurement. Concretely, $W_i$ consists of the two magic state wires used for the $i$'th $T$ gate circuit. Indeed, the $i$'th measurement applies the controlled measurement $\Gamma_{c_i}$ to these wires, which only partially collapses them.

Then, we are able to specify further details about the $f_i^{(\cdot)}$ and $g^{(\cdot)}$ measurements.

* Each $f_i^{(\cdot)}$ takes as input some sequence $(v_1,\dots,v_i,w_i)$ and outputs $v_i$ (fully collapsing the $V_i$ registers) along with a bit $r_i$ (partially collapsing the $W_i$ registers).

* In order to compute the bit $r_i$, the function $f_i^{(\cdot)}$ first needs to compute the $i$'th control bit $c_i$, which may depend on the input $x$ and all previous measurement results $(v_1,\dots,v_{i},r_1,\dots,r_{i-1})$. While we are able to provide $f_i^{(\cdot)}$ with the values $v_1,\dots,v_{i-1}$ on registers $V_1,\dots,V_{i-1}$ (which have been collapsed by previous measurements), this is not the case for the bits $r_1,\dots,r_{i-1}$, since the $W_1,\dots,W_{i-1}$ registers may have been computed on since previous measurements. To handle this, we remember the previous results $r_1,\dots,r_{i-1}$, and paramaterize $f_i^{x,r_1,\dots,r_{i-1}}$ by the input $x$ and previously generated bits $r_1,\dots,r_{i-1}$. Thus, the actual measurements are specified adaptively using the previously generated bits $r_1,\dots,r_{i-1}$.

* In a similar manner, the function $g^{x,r_1,\dots,r_t}$ is parameterized by the input $x$ and previously generated bits $r_1,\dots,r_t$. It takes as input some sequence $(v_1,\dots,v_{t+1})$ and instead of performing an intermediate measurement, it computes the final output $y = Q(x)$.

Finally, we have set up enough notation to start discussing our actual obfuscation construction, which follows.

§.§ Obfuscation Construction

So far, we have discussed a method for authenticating quantum states $\ket*{\widetilde{\psi}} = \Enc_k(\ket{\psi})$ using key $k = (S,\Delta,x,z)$, and a method for writing any quantum program as

\[\ket{\psi},L_1,M_{\theta_1,f_1^{(\cdot)}},\dots,L_t,M_{\theta_t,f_t^{(\cdot)}},L_{t+1},M_{\theta_{t+1},g^{(\cdot)}}\]
where $\ket{\psi}$ consists of a quantum state that was part of the description of the original program, as well as some magic states.

Garbling via encrypted measurements. We will build up to our full obfuscation construction by first describing how to garble quantum circuits using our approach. That is, we'll suppose that the evaluator is only interested in computing the output on a particular input $x$, and show how to design oracles $\sF_1[x],\dots,\sF_t[x],\sG[x]$ that, along with the authenticated state $\ket*{\widetilde{\psi}} = \Enc_k(\ket{\psi})$, allow the evaluator to perform the entire computation on top of authenticated data, and eventually obtain $Q(x)$ without learning anything else about the program's implementation.

The basic idea is to implement the measurement $M_{\theta_i,f_i^{(x,\cdot)}}$ on authenticated data using an oracle $\sF_i[x]$, that, instead of outputting the results $(v_i,r_i)$ in the clear, outputs the encoded version $\widetilde{v}_i$ of $v_i$ (that is, $\widetilde{v}_i$ is in the support of the authenticated state that encodes the logical string $v_i$) along with a random label $\ell_i$ representing the bit $r_i$. We will always denote vectors that result from measuring authenticated states (but not decoding) with a tilde (e.g. $\widetilde{v}_i$).

Roughly $\sF_i[x]$ will be implemented as follows. It takes as input vectors $\widetilde{v}_1,\dots,\widetilde{v}_i,\widetilde{w}_i$ from the support of authenticated states (obtained from authenticated wires $V_1,\dots,V_i,W_i$), as well as labels $\ell_1,\dots,\ell_{i-1}$ that encode the results $r_1,\dots,r_{i-1}$ of previous measurements. It first decodes its inputs, and then uses the decoded values to compute the next measurement results $(v_i,r_i)$. Finally, it outputs the encodings $(\widetilde{v}_i,\ell_i)$ where $\ell_i$ is a label for $r_i$ computed via a random oracle $H$.

We will implement $\sG[x]$ in exactly the same way, except that it directly outputs the result $y$. Sketches of these oracles follow.

* $(v_1,\dots,v_i,w_i) \gets \Dec_{k,\theta_i,L_i\dots L_1}(\widetilde{v}_1,\dots,\widetilde{v}_i,\widetilde{w}_i)$.[Recall the description of the decoding oracle $\Dec$ from <ref>. We additionally parameterize the oracle with a concatenation of the linear functions $L_i \dots L_1$, which determines the sequence of Pauli one-time-pad keys to be used during the decoding. ] Abort if the output is $\bot$.

* For each $\iota \in [i-1]$, let
\[\ell_{\iota,0} = H(\widetilde{v}_1,\dots,\widetilde{v}_{\iota},\ell_1,\dots,\ell_{\iota-1},0), ~~~ \ell_{\iota,1} = H(\widetilde{v}_1,\dots,\widetilde{v}_{\iota},\ell_1,\dots,\ell_{\iota-1},1),\]
and let $r_\iota$ be the bit such that $\ell_\iota = \ell_{\iota,r_\iota}$, or abort if there is no such bit.

* Compute $(v_i,r_i) = f_i^{x,r_1,\dots,r_{i-1}}(v_1,\dots,v_i,w_i)$.

* Set $\ell_i \coloneqq H(\widetilde{v}_1,\dots,\widetilde{v}_i,\ell_1,\dots,\ell_{i-1},r_i),$ and output $(\widetilde{v}_i,\ell_i)$.

* $(v_1,\dots,v_{t+1}) \gets \Dec_{k,\theta_i,L_{t+1}\dots L_1}(\widetilde{v}_1,\dots,\widetilde{v}_{t+1})$. Abort if the output is $\bot$.

* For each $\iota \in [t]$, let
\[\ell_{\iota,0} = H(\widetilde{v}_1,\dots,\widetilde{v}_{\iota},\ell_1,\dots,\ell_{\iota-1},0), ~~~ \ell_{\iota,1} = H(\widetilde{v}_1,\dots,\widetilde{v}_{\iota},\ell_1,\dots,\ell_{\iota-1},1),\]
and let $r_\iota$ be the bit such that $\ell_\iota = \ell_{\iota,r_\iota}$, or abort if there is no such bit.

* Compute and output $y = g^{x,r_1,\dots,r_t}(v_1,\dots,v_{t+1})$.

Proving the security of this garbled program consists of two main steps: (1) a “soundness” argument establishing that no adversary, given $\ket*{\widetilde{\psi}}$ and oracle access to $\sF_1[x],\dots,\sF_t[x]$ should be able to output classical strings $(\widetilde{v}_1,\dots,\widetilde{v}_{t+1},\ell_1,\dots,\ell_t)$ such that $\sG[x](\widetilde{v}_1,\dots,\widetilde{v}_{t+1},\ell_1,\dots,\ell_t) \notin \{Q(x),\bot\}$, and (2) a “simulation” argument establishing that the $\sF_1[x],\dots,\sF_t[x]$ oracles can be simulated using a verification oracle $\Ver_{k,\cdot,\cdot}(\cdot)$ for the authentication scheme instead of the decoding functionality $\Dec_{k,\cdot,\cdot}(\cdot)$. Indeed, a common theme throughout our proof strategy is understanding how we can replace $\Dec_{k,\cdot,\cdot}(\cdot)$ with $\Ver_{k,\cdot,\cdot}(\cdot)$ so that we can then appeal to the security of the authentication scheme. Further discussion on these two steps can be found in our proof intuition section, <ref>. Here, we just mention that the main idea for the soundness argument is an inductive strategy, where we perform the first measurement and appeal to soundness of a garbled program with one fewer measurement layer.

From garbling to obfuscation via signature tokens. To complete our construction of full-fledged obfuscation, it remains to show how to grant the evaluator the ability to execute the circuit on any input $x$ of its choice, without risking any other leakage on the description of the program. A natural idea is to re-define $\sF_1,\dots,\sF_t,\sG$ so that they additionally take $x$ as input, and include $x$ in the hashes $H(x,\widetilde{v}_1,\dots,\widetilde{v}_i,\ell_1,\dots,\ell_{i-1},r_i)$ that define the output labels. We intuitively want to sample different output labels for each $x$ so that the resulting obfuscation scheme can roughly be seen as a “concatenation” of independently sampled garbling schemes for each $x$ (that share the same initial authenticated state). However, it turns out that this is not yet enough to ensure security.

Indeed, nothing is preventing the adversary from applying a type of “mixed input” attack, where they evaluate honestly on an input $x$, but at some point insert a measurement implemented by the oracle $\sF_i(x',\cdot)$ on some input $x' \neq x$. That is, at layer $i$, the adversary would first implement $\sF_i(x',\cdot)$ (and ignore the output labels) to collapse the state in some way before continuing with their honest evaluation procedure using $\sF_i(x,\cdot)$. Unfortunately, this rogue call to $\sF_i(x',\cdot)$ wouldn't destroy the current state enough to cause the remaining oracle calls to $\sF_i(x,\cdot),\dots,\sF_t(x,\cdot),\sG(x,\cdot)$ to abort, but might collapse the state in a manner inconsistent with an honest evaluation on input $x$, eventually allowing the adversary to break the “soundness” of the scheme by finding an input to $\sG(x,\cdot)$ that results in an output $y \neq Q(x)$.

Taking inspiration from <cit.> who faced a similar issue, we solve our problem via the use of signature tokens <cit.>. This quantum cryptographic primitive consists of a quantum signing key $\ket{\sk}$ that may be used to produce a classical signature $\sigma_x$ on any single message $x$ but never two signatures $\sigma_x,\sigma_{x'}$ on two different messages $x,x'$ simultaneously. We include a quantum signing key $\ket{\sk}$ as part of our obfuscation construction, and re-define the oracles $\sF_1,\dots,\sF_t,\sG$ to take $x$ and a signature $\sigma_x$ as input, abort if the signature is invalid, and otherwise include both in the hashes $H(x,\sigma_x,\widetilde{v}_1,\dots,\widetilde{v}_i,\ell_1,\dots,\ell_{i-1},r_i)$ that define the output labels.

Intuitively, this prevents the above attack. Once the adversary has begun an honest evaluation on some input $x$, it must “know” some valid signature $\sigma_x$, preventing it from querying the oracles on any input that starts with $(x',\sigma_{x'})$. That is, if it actually want to evaluate on $x'$, it must uncompute everything it has computed so far to return to $\ket{\sk}$ before it can produce a signature $\sigma_{x'}$ and begin evaluating on $x'$.

We provide more details about this approach in the proof intuition section, <ref>. Of note is the fact that we crucially use a purified random oracle <cit.> in order to extract a signature token on $x$ from any adversary who has begun evaluating the obfuscated program on $x$. Formalizing this approach is one of trickier aspects of the proof, and we describe a toy problem in <ref> that may provide some intuition for the actual proof.

§.§ Discussion and Open Problems

Comparison with <cit.>. In <ref>, we described an application of our construction to “best-possible” copy-protection, a notion recently introduced by <cit.>. However, it has already been shown by <cit.> that copy-protection for all unlearnable functions exists in the classical oracle model. So what is the advantage of our approach?

The catch with <cit.> is that it is also known that copy-protection for all unlearnable functions is unachievable in the plain model <cit.>. Thus, one cannot expect to instantiate <cit.>'s construction in the plain model with, say, an indistinguishably obfuscator, and conjecture that their notion of security still holds. Moreover, it is unclear (to us) how one would prove that <cit.> or any other approach is a “best-possible” copy-protector without going through the intermediate notion of quantum state indistinguishability obfuscation.

On the other hand, there is no known impossibility for quantum state indistinguishability obfuscation in the plain model. Thus, one can conjecture that our approach (or some variant of it) will eventually yield a quantum state indistinguishability obfuscator in the plain model, which, by the results of <cit.>, would immediately yield best-possible copy-protection for any functionality. Hence, we view our results (combined with <cit.>) as marking significant progress towards the long-standing goal of achieving general-purpose copy-protection from concrete cryptographic assumptions.

Comparison with <cit.>. As mentioned in <ref>, our techniques differ significantly from prior work on quantum obfuscation. To be more concrete, let's take the example of <cit.>, who constructed obfuscation for classically-described pseudo-deterministic quantum functionalities.

At a high level, their approach was to encrypt the description of the circuit $Q \to \Enc(Q)$ using a blind quantum computation protocol (e.g. <cit.>) and prepare a classical oracle that is able to verify the result of computing $\Enc(Q) \to \Enc(Q(x))$, and decrypt the result if verification passes. But if the program $\ket{Q}$ is described quantumly, this approach completely breaks down, since the classical oracle cannot even interpret the quantum statement $\Enc(\ket{Q}) \to \Enc(Q(x))$ to be verified.

Our approach is to not only encrypt $\ket{Q}$ but to authenticate it as well. Then, we design oracles that are able to verify the blind computation along the way, as opposed to all at once at the end of the computation. That is, while both approaches make fundamental use of both blind and verifiable quantum computation, they differ significantly in execution.

Finally, it is worth mentioning that the <cit.> approach may prove to be advantageous in the case where we are only interested in obfuscating quantum circuits with a classical description, and desire to produce an obfuscated program that also has a classical description. Given the fact that quantum state obfuscation is a best-possible copy-protector, it is actually inherent that our obfuscated program includes (unclonable) quantum states, even when applied to a circuit with classical description. On the other hand, while the <cit.> approach as currently implemented also produces obfuscated programs with a quantum description, it is reasonable to hope that it could be de-quantized. Indeed, the only reason that <cit.>'s construction includes a quantum state is that two of their building blocks - signature tokens and Pauli functional commitments - are constructed using quantum keys. However, it is plausible that both of these building blocks could be instantiated with a classical key (e.g. using the ideas of <cit.>, though proving security may be difficult). We leave further exploration of these ideas to future work.

Open problems. We conclude this overview by mentioning a couple of natural open problems that are motivated by this work. Perhaps most obviously, can we obtain provable security in the plain model from quantum-secure indistinguishability obfuscation (or a different concrete and plausible assumption on classical obfuscators)? Besides representing major progress in our understanding of quantum obfuscation, answering this question would have significant implications for general-purpose software copy-protection (due to <cit.>), another area where positive results are difficult to come by.

Next, can we generalize beyond pseudo-deterministic programs? As a first step, can we obfuscate sampling circuits, i.e. those with classical inputs that produce a distribution over classical outputs? Interestingly, while <cit.>'s construction does not even satisfy correctness for (even classically-described) sampling circuits, our approach can plausibly be applied to sampling circuits, although it remains open to obtain any provable guarantees. Finally, the feasibility of obfuscating general-purpose circuits with quantum inputs and/or quantum outputs is still wide open, and remains a fascinating direction for future exploration, with potential applications beyond cryptography, e.g. to quantum complexity theory.

§ PRELIMINARIES

Let $\secp$ denote the security parameter. We write $\negl(\cdot)$ to denote any negligible function, which is a function $f$ such that for every constant $c \in \mathbb{N}$ there exists $N \in \mathbb{N}$ such that for all $n > N$, $f(n) < n^{-c}$. We write $\nonnegl(\cdot)$ to denote any function $f$ that is not negligible. That is, there exists a constant $c$ such that for infinitely many $n$, $f(n) \geq n^{-c}$. Finally, we write $\poly(\cdot)$ to denote any polynomial function $f$. That is, there exists a constant $c$ such that for all $n \in \bbN$, $f(n) \leq n^{-c}$. For two probability distributions $D_0,D_1$ with classical support $S$, let
\[\mathsf{TV}\left(D_0,D_1\right) \coloneqq \sum_{x \in S}|D_0(x) - D_1(x)|\]
denote the total variation distance. For a set $S$, we let $x \gets S$ denote sampling a uniformly random element $x$ from $S$. If $D$ is a distribution, we let $x \gets D$ denote sampling from $D$, and let
\[\left\{x : x \gets D_0\right\} \approx_\epsilon \left\{x : x \gets D_1\right\}\]
denote that $\TV(D_0,D_1) \leq \epsilon$. Finally, we denote a linear combination of distributions by

\[(1-\delta)\{x : x \gets D_0\} + \delta \{x : x \gets D_1\},\]
meaning that with probability $1-\delta$, sample from $D_0$ and with probability $\delta$, sample from $D_1$.

§.§ Quantum Background

An $n$-qubit register $\regX$ is a named Hilbert space $\bbC^{2^n}$. A pure quantum state on register $\regX$ is a unit vector $\ket{\psi}^{\regX} \in \bbC^{2^n}$. A mixed state on register $\regX$ is described by a density matrix $\rho^{\regX} \in \bbC^{2^n \times 2^n}$, which is a positive semi-definite Hermitian operator with trace 1.

A quantum operation $F$ is a completely-positive trace-preserving (CPTP) map from a register $\regX$ to a register $\regY$, which in general may have different dimensions. That is, on input a density matrix $\rho^{\regX}$, the operation $F$ produces $F(\rho^{\regX}) = \tau^{\regY}$ a mixed state on register $\regY$. A unitary $U: \regX \to \regX$ is a special case of a quantum operation that satisfies $U^\dagger U = U U^\dagger = \cI^{\regX}$, where $\cI^{\regX}$ is the identity matrix on register $\regX$. A projector $\Pi$ is a Hermitian operator such that $\Pi^2 = \Pi$, and a projective measurement is a collection of projectors $\{\Pi_i\}_i$ such that $\sum_i \Pi_i = \cI$. Throughout this work, we will often write an expression like $\Pi\ket{\psi}$, where $\ket{\psi}$ has been defined on some multiple registers, say $\regX$, $\regY$, and $\regZ$, and $\Pi$ has only been defined on a subset of these registers, say $\regY$. In this case, we technically mean $(\cI^\regX \otimes \Pi \otimes \cI^\regZ)\ket{\psi}$, but we drop the identity matrices to reduce notational clutter.

A family of quantum circuits is in general a sequence of quantum operations $\{C_\secp\}_{\secp \in \bbN}$, parameterized by the security parameter $\secp$. We say that the family is quantum polynomial time (QPT) if $C_\secp$ can be implemented with a $\poly(\secp)$-size quantum circuit. A family of oracle-aided quantum circuits $\{C^\sF_\secp\}_{\secp \in \bbN}$ has access to an oracle $\sF: \{0,1\}^* \to \{0,1\}^*$ that implements some deterministic classical map. That is, $C_\secp$ can apply a unitary that maps $\ket{x}\ket{y} \to \ket{x}\ket{y \oplus \sF(x)}$. We say that the family is quantum polynomial query (QPQ) if $C_\secp$ only makes $\poly(\secp)$-many queries to $\sF$, but is otherwise computationally unbounded.

Let $\Tr$ denote the trace operator. For registers $\regX,\regY$, the partial trace $\Tr^{\regY}$ is the unique operation from $\regX,\regY$ to $\regX$ such that for all $(\rho,\tau)^{\regX,\regY}$, $\Tr^{\regY}(\rho,\tau) = \Tr(\tau)\rho$. The trace distance between states $\rho,\tau$, denoted $\TD(\rho,\tau)$ is defined as
\[\TD(\rho,\tau) \coloneqq \frac{1}{2}\Tr\left(\sqrt{(\rho-\tau)^\dagger(\rho-\tau)}\right).\]
The trace distance between two states $\rho$ and $\tau$ is an upper bound on the probability that any (unbounded) algorithm can distinguish $\rho$ and $\tau$.

For any set $S$, we define $O[S]$ to be the boolean function that checks for membership in $S$ and define the projector
$$\Pi[S] = \sum_{s \in S}\ketbra{s}{s}.$$

A quantum implementation of a functionality with classical inputs and outputs, or, a quantum program, is a pair $(\ket{\psi},C)$, where $\ket{\psi}$ is a state and $C$ is the classical description of a quantum circuit. For any classical input $x \in \{0,1\}^{m}$, we write $y \gets C(\ket{x}\ket{\psi})$ to denote the result of running $C$ and then measuring a dedicated $m'$-qubit output register in the standard basis to obtain $y$.

* We say that the program is deterministic if for all $x$, there exists $y \in \{0,1\}^{m'}$ such that
\[\Pr[C(\ket{x}\ket{\psi}) = y] = 1.\]

* We say that a family of quantum programs $\{(\ket{\psi_\secp},C_\secp)\}_{\secp \in \bbN}$ is $\epsilon-$pseudo-deterministic for some $\epsilon = \epsilon(\secp)$ if for all sequences of inputs $\{x_\secp\}_{\secp \in \bbN}$, there exists a sequence of outputs $\{y_\secp\}_{\secp \in \bbN}$ such that
\[\Pr[C_\secp(\ket{x_\secp}\ket{\psi_\secp}) \to y_\secp] \geq 1-\epsilon(\secp).\]

We will often leave the dependence on $\secp$ implicit, and just refer to (pseudo)-deterministic programs $(\ket{\psi},C)$. We will denote by $Q(x)$ the string $y$ such that $\Pr[C(\ket{x}\ket{\psi}) \to y] \geq 1-\epsilon(\secp)$, and refer to $Q$ as the map induced by $(\ket{\psi},C)$.

§.§ Useful Lemmas

Let $\rho$ be a quantum state and let $(\Pi,\cI-\Pi)$ be a projective measurement such that $\Tr(\Pi\rho) \geq 1-\delta$. Let
\[\rho' = \frac{\Pi\rho\Pi}{\Tr(\Pi\rho)}\]
be the state after applying $(\Pi,\cI-\Pi)$ to $\rho$ and post-selecting on obtaining the first outcome. Then, $\TD(\rho,\rho') \leq 2\sqrt{\delta}$.

Let $R,\widehat{R} \subseteq \bbF_2^n$ be subspaces of $\bbF_2^n$, and let $(x_0,z_0,x_1,z_1)$ be such that either $x_0 \oplus x_1 \notin \widehat{R}^\bot$ or $z_0 \oplus z_1 \notin R^\bot$. Then for any $\Delta \notin R, \widehat{\Delta} \notin \widehat{R}$ and density matrix $\rho$ on $m \geq n$ qubits,

\[\sum_{x \in R + \Delta, z \in \widehat{R} + \widehat{\Delta}}(Z^z X^x)(X^{x_0}Z^{z_0})(X^xZ^z)\rho(Z^z X^x)(Z^{z_1}X^{x_1})(X^x Z^z) = 0.\]

Using the fact that $X^x Z^z = (-1)^{x \cdot z} Z^z X^x$, we write

\begin{align*}
&\sum_{x \in R + \Delta, z \in \widehat{R} + \widehat{\Delta}}(Z^z X^x)(X^{x_0}Z^{z_0})(X^xZ^z)\rho(Z^z X^x)(Z^{z_1}X^{x_1})(X^x Z^z) \\
&= \sum_{x \in R + \Delta, z \in \widehat{R}+ \widehat{\Delta}} (-1)^{x \cdot z_0 + z \cdot x_0 + x \cdot z_1 + z \cdot x_1}(X^{x_0}Z^{z_0})\rho(Z^{z_1} X^{x_1})\\
&= \left(\sum_{z \in \widehat{R} + \widehat{\Delta}}(-1)^{z \cdot (x_0 \oplus x_1)}\right)\left(\sum_{x \in R + \Delta}(-1)^{x \cdot (z_0 \oplus z_1)}\right)(x^{x_0}Z^{z_0})\rho(Z^{z_1} X^{x_1})\\
&= \left(\sum_{z \in \widehat{R}}(-1)^{z \cdot (x_0 \oplus x_1)}\right)\left(\sum_{x \in R}(-1)^{x \cdot (z_0 \oplus z_1)}\right)(-1)^{\widehat{\Delta} \cdot (x_0 \oplus x_1)}(-1)^{\Delta \cdot (z_0 \oplus z_1)}(x^{x_0}Z^{z_0})\rho(Z^{z_1} X^{x_1})\\
&= 0,
\end{align*}

where the last equality follows because either $x_0 \oplus x_1 \notin \widehat{R}^\bot$ or $z_0 \oplus z_1 \notin R^\bot$.

The following two lemmas are applications of Cauchy-Schwarz. The first is adapted from <cit.>.

Let $\cK$ be a set of keys, $N$ an integer, and $\{\ket{\psi_k},\{\Pi_{k,i}\}_{i \in [N]},O_k\}_{k \in \cK}$ be a set of states $\ket{\psi_k}$, projective submeasurements $\{\Pi_{k,i}\}_{i \in [N]}$, and classical functions $O_k$ such that $\ket{\psi_k} \in \mathsf{Im}(\sum_i \Pi_{k,i})$ for each $k$. Then for any distinguisher $D$, which we take to be an oracle-aided binary outcome projector, it holds that

\[\E_{k \gets \cK}\left[\|D^{O_k}\ket{\psi_k}\|^2\right] - \sum_i\E_{k \gets \cK}\|D^{O_k}\Pi_{k,i}\ket{\psi_k}\|^2 \leq N \cdot \left[\sum_{i \neq j}\E_{k \gets \cK}\|\Pi_{k,j}D^{O_k}\Pi_{k,i}\ket{\psi_k}\|^2\right]^{1/2}.\]

\begin{align*}
&\E_{k \gets \cK}\left[\bigg\| D^{O_k}\ket{\psi_k}\big\|^2\right] \\
&=\E_{k \gets \cK}\left[\bigg| \bra{\psi_k}\left(\sum_i \Pi_{k,i}\right)D^{O_k}\left(\sum_i \Pi_{k,i}\right)\ket{\psi_k}\bigg|\right]\\
&=\E_{k \gets \cK}\left[\bigg| \sum_i \bra{\psi_k}\Pi_{k,i}D^{O_k}\Pi_{k,i}\ket{\psi_k} + \sum_{i \neq j}\bra{\psi_k}\Pi_{k,j}D^{O_k}\Pi_{k,i}\ket{\psi_k}\bigg|\right]\\
&\leq \sum_i \E_{k \gets \cK}\big\| D^{O_k}\Pi_{k,i}\ket{\psi_k}\big\|^2 + \E_{k \gets \cK}\left[\sum_{i \neq j}\bigg| \bra{\psi_k}\Pi_{k,j}D^{O_k}\Pi_{k,i}\ket{\psi_k}\bigg|\right] \\
&\leq \sum_i \E_{k \gets \cK}\big\| D^{O_k}\Pi_{k,i}\ket{\psi_k}\big\|^2  + \E_{k \gets \cK}\left[\sum_{i \neq j}\sqrt{\bra{\psi_k}\Pi_{k,i}D^{O_k}\Pi_{k,j}D^{O_k}\Pi_{k,i}\ket{\psi_k}}\right] \\
&\leq \sum_i \E_{k \gets \cK}\big\| D^{O_k}\Pi_{k,i}\ket{\psi_k}\big\|^2  + N \cdot \E_{k \gets \cK}\left[\left(\sum_{i \neq j}\|\Pi_{k,j}D^{O_k}\Pi_{k,i}\ket{\psi_k}\|^2\right)^{1/2}\right] \\
&\leq \sum_i \E_{k \gets \cK}\big\| D^{O_k}\Pi_{k,i}\ket{\psi_k}\big\|^2  + N \cdot \left[\sum_{i \neq j}\E_{k \gets \cK}\|\Pi_{k,j}D^{O_k}\Pi_{k,i}\ket{\psi_k}\|^2\right]^{1/2},
\end{align*}

where the first inequality is the triangle inequality, the second follows from Cauchy-Schwarz applied to vectors $\ket{\psi_k}$ and $\Pi_{k,j}D^{O_k}\Pi_{k,i}\ket{\psi}$, the third follows from Cauchy-Shwarz applied to the length $N^2$ vector $(1,\dots,1)$ and the vector with $(i,j)$'th entry equal to
\[\sqrt{\bra{\psi_k}\Pi_{k,i}D^{O_k}\Pi_{k,j}D^{O_k}\Pi_{k,i}\ket{\psi_k}},\]
and the fourth is Jensen's inequality.

Let $\cK$ be a set of keys, $N$ an integer, and $\{\ket{\psi_k},\{\Pi_{k,i}\}_{i \in [N]},O_k,\Gamma_k\}_{k \in \cK}$ be a set of states $\ket{\psi_k}$, projective submeasurements $\{\Pi_{k,i}\}_{i \in [N]}$, classical function $O_k$, and projective measurements $\Gamma_k$ such that $\ket{\psi_k} \in \mathsf{Im}(\sum_i \Pi_{k,i})$ for each $k$. Then for any oracle-aided unitary $U$, it holds that

\[\E_{k \gets \cK}[\|\Gamma_k U^{O_k}\ket{\psi_k}\|^2] \leq N \cdot \sum_i\E_{k \gets \cK}\|\Gamma_k U^{O_k}\Pi_{k,i}\ket{\psi_k}\|^2.\]

\begin{align*}
&\E_{k \gets \cK}[\|\Gamma_k U^{O_k}\ket{\psi_k}\|^2]\\
&\leq \E_{k \gets \cK}\left[\left(\sum_i\|\Gamma_k U^{O_k}\Pi_{k,i}\ket{\psi_k}\|\right)^2\right]\\
&\leq \E_{k \gets \cK}\left[\left(\sqrt{N}\sqrt{\sum_i\|\Gamma_k U^{O_k}\Pi_{k,i}\ket{\psi_k}\|^2}\right)^2\right]\\
&=N \cdot \sum_i\E_{k \gets \cK}\|\Gamma_k U^{O_k}\Pi_{k,i}\ket{\psi_k}\|^2,
\end{align*}

where the first inequality is the triangle inequality, and the second follows from Cauchy-Shwarz applied to the length $N$ vector $(1,\dots,1)$ and the vector with $i$'th entry equal to $\|\Gamma_k U^{O_k}\Pi_{k,i}\ket{\psi_k}\|$.

We will frequently invoke the following lemma in order to switch between two oracles that differ on hard-to-find inputs. The proof is a standard oracle hybrid argument.

For each $\secp \in \bbN$, let $\cK_\secp$ be a set of keys, and $\{\ket{\psi_k},O_k^0,O_k^1,S_k\}_{k \in \cK_\secp}$ be a set of states $\ket{\psi_k}$, classical functions $O_k^0,O_k^1$, and sets of inputs $S_k$. Suppose that the following properties holds.

* The oracles $O_k^0$ and $O_k^1$ are identical on inputs outside of $S_k$.

* For any oracle-aided unitary $U$ with $q = q(\secp)$ queries, there is some $\epsilon = \epsilon(\secp)$ such that

\[\E_{k \gets \cK}\left[\big\| \Pi[S_k]U^{O_k^0}\ket{\psi_k}\big\|^2\right] \leq \epsilon.\]

Then, for any oracle-aided unitary $U$ with $q(\secp)$ queries and distinguisher $D$,
\[\bigg| \Pr_{k \gets \cK}\left[D\left(k,U^{O_k^0}\ket{\psi_k}\right) = 0\right] - \Pr_{k \gets \cK}\left[D\left(k,U^{O_k^1}\ket{\psi_k}\right) = 0\right]\bigg| \leq 4q\sqrt{\epsilon}.\]

For each $i \in [0,\dots,q]$, define hybrid $\cH_i$ to sample $k \gets \cK$ and output $(k,U^{(\cdot)}\ket{\psi_k})$, where $U$'s first $q - i$ oracle queries are answered with $O_k^0$ and $U$'s final $i$ oracle queries are answered with $O_k^1$. For each $i \in [0,\dots,q-1]$, define hybrid $\cH_i'$ to be identical to $\cH_i$ except that we apply the measurement $\{\Pi[S_k],\cI-\Pi[S_k]\}$ to $U$'s state right before the $q-i$'th oracle query, and post-select on obtaining the second outcome. Then for any $i \in [0,\dots,q-1]$,

* By condition 2 of the lemma statement and <ref>, it holds that $\TD(\cH_i,\cH_i') \leq 2\sqrt{\epsilon}$.

* By conditions 1 and 2 of the lemma statement and <ref>, it holds that $\TD(\cH_i'
,\cH_{i+1}) \leq 2\sqrt{\epsilon}$.

Thus, the lemma follows by summing over the $2q$ hybrid switches.

§.§ Signature Tokens

A signature token scheme consists of algorithms $(\TokGen,\TokSign,\TokVer)$ with the following syntax.

* $\TokGen(1^\secp) \to (\vk,\ket{\sk})$: The $\TokGen$ algorithm takes as input the security parameter $1^\secp$ and outputs a classical verification key $\vk$ and a quantum signing key $\ket{\sk}$.

* $\TokSign(b,\ket{\sk}) \to \sigma$: The $\TokSign$ algorithm takes as input a bit $b \in \{0,1\}$ and the signing key $\ket{\sk}$, and outputs a classical signature $\sigma$.

* $\TokVer(\vk,b,\sigma) \to \{\top,\bot\}$: The $\TokVer$ algorithm takes as input a verification key $\vk$, a bit $b$, and a signature $\sigma$, and outputs $\top$ or $\bot$.

A signature token should satisfy the following definition of correctness.

A signature token scheme $(\TokGen,\TokSign,\TokVer)$ is correct if for any $b \in \{0,1\}$,

\[\Pr\left[\TokVer(\vk,b,\sigma) = \top : \begin{array}{r}(\vk,\ket{\sk}) \gets \Gen(1^\secp) \\ \sigma \gets \Sign(b,\ket{\sk})\end{array}\right] = 1.\]

A signature token should satisfy the following definition of security. Note that we give the adversary oracle access to the verification functionality, and ask for exponential security.

A signature token scheme $(\TokGen,\TokSign,\TokVer)$ satisfies unforgeability if for any QPQ adversary $\{\sA_\secp\}_{\secp \in \bbN}$,

\[\Pr\left[\begin{array}{l} \TokVer(\vk,0,\sigma_0) = \top ~~ \wedge \\ \TokVer(\vk,1,\sigma_1) = \top\end{array} : \begin{array}{r} (\vk,\ket{\sk}) \gets \Gen(1^\secp) \\ (\sigma_0,\sigma_1) \gets \sA_\secp^{\TokVer[\vk]}(\ket{\sk}) \end{array}\right] = 2^{-\Omega(\secp)},\]
where $\TokVer[\vk]$ is the functionality $\TokVer(\vk,\cdot,\cdot)$.

There exists a signature token scheme that satisfies <ref> and <ref>.

§ AUTHENTICATION SCHEME

In this section, we introduce the notion of a “publicly-verifiable linearly-homomorphic QAS (Quantum Authentication Scheme) with classically-decodable ZX measurements.” We then provide a construction and security proof.

§.§ Definitions

The following notation will be heavily referenced both throughout this section, and throughout the remainder of the paper.

Partial ZX measurements. Given a string $\theta \in \{0,1,\bot\}^n$, define sets
\[\MS_\theta \coloneqq \{i : \theta_i \neq \bot\}, \ \ \MS_{\theta,0} = \{i : \theta_i = 0\}, \ \ \MS_{\theta,1} = \{i : \theta_i = 1\}, \ \ \MS_{\theta,\bot} \coloneqq \{i : \theta_i = \bot\}.\]
We will often write $\MS,\MS_0,\MS_1,\MS_\bot$ instead of $\MS_\theta,\MS_{\theta,0},\MS_{\theta,1},\MS_{\theta,\bot}$ when the choice of $\theta$ is clear from context. The string $\theta$ will be used to denote the basis of a partial measurement on $n$ qubits, where the 0 indices are measured in the standard basis and the 1 indices are measured in the Hadamard basis. We will also need the following notation.

* Given a string $m \in \{0,1\}^n$ and a set $\MS \subseteq [n]$, let $m_\MS$ denote the substring of $m$ consisting of bits $\{m_i\}_{i \in \MS}$.

* Given $\theta \in \{0,1,\bot\}^n$ and a set $\MS \subseteq [n]$, define $\theta[\MS]$ to be equal to $\theta$ on indices in $V$ and $\bot$ everywhere else.

* Given a register $\regM$, an operation $U$ on $\regM$, and a subset $\MS \subseteq [n]$, let $U^\MS$ be the operation on $\regM^{\otimes n}$ that applies $U$ to the $i$'th copy of $\regM$ for each $i \in \MS$.

For any $\theta \in \{0,1,\bot\}^n$ and classical function $f : \{0,1\}^{|\MS|} \to \{0,1\}^*$, let $M_{\theta,f}$ be the projective measurement on $n$ qubits defined by the operators
\[\left\{H^{\MS_1}\left(\sum_{m : f\left(m_\MS\right) = y}\ketbra{m}{m}\right)H^{\MS_1}\right\}_{y}.\]
For any $n$-qubit register $\regM$, we write
\[M_{\theta,f}(\regM) \to \regM,y\]
to refer to the operation that measures $\regM$ according to $M_{\theta,f}$ and then writes the classical result $y$ to a new register. Sometime we will write $M_{\theta,f}(\regM) \to y$ to denote just the classical measurement result $y$.

Linear operations. We will use $L$ to denote a sequence of CNOT gates on $n$ qubits, which we refer to as a linear operation. While all quantum gates are linear with respect to the ambient Hilbert space of exponential dimension, here linearity specifically refers to the fact that any sequence of CNOT gates applies a linear function over $\bbF_2$ to each standard basis vector. In an abuse of notation, $L$ will either refer to the classical description of a series of CNOT gates or to the actual unitary operation that applies these gates. Which case should be clear from context.

Syntax. A publicly-verifiable, linearly-homomorphic quantum authentiation scheme (QAS) with classically-decodable ZX measurements has the following syntax. Let $p = p(\secp)$ be a polynomial.

* $\mathsf{Gen}(1^\secp,n) \rightarrow k$: The key generation algorithm takes as input a security parameter $1^\secp$ and number of qubits $n = \poly(\secp)$, and outputs an authentication key $k$.

* $\mathsf{Enc}_k(\regM)\to\regC$: The encoding algorithm is an isometry parameterized by an authentication key $k$ that maps a state on an $n$-qubit register $\regM \coloneqq \regM_1 \otimes \dots \otimes \regM_n$ to a state on an $np$-qubit register $\regC \coloneqq \regC_1 \otimes \dots \otimes \regC_n$, where each $\regC_i$ is an $p$-qubit register.

* $\LinEval_L(\regC) \to \regC$: The linearly-homomorphic evaluation procedure is a unitary parameterized by a linear operation $L$ that operates on register $\regC$.

* $\mathsf{Dec}_{k,L,\theta}\left(c\right) \rightarrow m \cup \{\bot\}$: The classical decoding algorithm is parameterized by an authentication key $k$, a linear operation $L$, and a choice of bases $\theta \in \{0,1,\bot\}^{n}$. It takes as input a string $c \in \{0,1\}^{|\MS| \cdot p}$ and outputs either a classical string $m \in \{0,1\}^{|\MS|}$ or $\bot$.

* $\Ver_{k,L,\theta}(c) \to \{\top,\bot\}$: The classical verification algorithm is identical to $\Dec$ except that whenever $\Dec$ outputs an $m \neq \bot$, $\Ver$ outputs $\top$.

Partial ZX measurements on authenticated states. First, given the parameter $p$, define
\[\widetilde{\MS} \coloneqq \bigcup_{i \in \MS} \{(i-1)p +1, \dots, ip\} \subseteq [np].\]
That is, $\widetilde{\MS}$ contains the $i$'th chunk of $p$ indices for each $i \in \MS$. Define $\widetilde{\MS}_0, \widetilde{\MS}_1, \widetilde{\MS}_\bot$ analogously. For any $\theta \in \{0,1,\bot\}^n$, classical function $f : \{0,1\}^{|\MS|} \to \{0,1\}^*$, authentication key $k$, and linear operation $L$, let $\widetilde{M}_{\theta,f,k,L}$ be the projective measurement on $np$ qubits defined by the operators
\[\left\{H^{\widetilde{\MS}_1} \left(\sum_{c : f\left(\Dec_{k,L,\theta}\left(c_{\widetilde{\MS}}\right)\right) = y}\ketbra{c}{c}\right)H^{\widetilde{\MS}_1}\right\}_{y} \cup \left\{H^{\widetilde{\MS}_1}\left(\sum_{c:\Dec_{k,L,\theta}\left(c_{\widetilde{\MS}}\right) = \bot}\ketbra{c}{c}\right)H^{\widetilde{\MS}_1}\right\}.\]
For any $np$-qubit register $\regC$, we write
\[\widetilde{M}_{\theta,f,k,L}(\regC) \to \regC,y\]
to refer to the operation that measures $\regC$ according to $M_{\theta,f,k,L}$ and then writes the classical result $y$ to a new register. Sometimes we will write $\widetilde{M}_{\theta,f,k,L}(\regC) \to y$ to denote just the classical measurement result $y$.

Correctness. Our definition of correctness roughly states that encoding, applying a linear homomorphism, and then applying a partial measurement to the encoded state is equivalent to first applying the linear operation, applying the partial measurement, and then encoding. This definition supports composition of multiple partial measurements on encoded data, which will be necessary for our application to obfuscation.

A publicly-verifiable linearly-homomorphic QAS with classically-decodable ZX measurements is correct if the following holds. For any linear operation $L$, bases $\theta \in \{0,1,\bot\}^{n}$, $f: \{0,1\}^{|\MS|} \to \{0,1\}^*$, and $k \in \Gen(1^\secp,n)$,

\begin{align*}
&\LinEval_{L}^\dagger \circ \widetilde{M}_{\theta,f,k,L} \circ \LinEval_L \circ \Enc_k  = \Enc_k \circ L^\dagger \circ M_{\theta,f} \circ L.
\end{align*}

Note that both sequences of operations above map $\regM \to (\regC,y)$, where $\regM$ is an $n$-qubit register, $\regC$ is an $np$-qubit register, and $y$ is a classical measurement outcome.

Security Next, we formalize two security properties. The first roughly states that no adversary with access to the verification oracle can change the distribution resulting from a partial measurement on the encoded state.

A publicly-verifiable linearly-homomorphic QAS with classically-decodable ZX measurements is secure if the following holds. For any linear operation $L$, bases $\theta \in \{0,1,\bot\}^n$, $f : \{0,1\}^{|\MS|} \to \{0,1\}^*$, and oracle-aided adversary $A : \regC \to \regC$, there exists an $\epsilon(\secp) \in [0,1]$ such that for any $n$-qubit state $\ket{\psi}$,

\[\left\{y : \begin{array}{r} k \gets \Gen(1^\secp,n) \\ y \gets \widetilde{M}_{\theta,f,k,L} \circ A^{\Ver_{k,\cdot,\cdot}(\cdot)} \circ \Enc_k(\regM)\end{array}\right\} \approx_{2^{-\Omega(\secp)}} (1-\epsilon(\secp))\left\{y : y \gets M_{\theta,f} \circ L(\regM)\right\} + \epsilon(\secp)\{\bot\}.\]

Although the adversary $A$ is defined as a (oracle-aided) general quantum map from $\regC \to \regC$, we can without loss of generality take it to be a (oracle-aided) unitary that additionally operates on some workspace register $\regA$ initialized to $\ket{0}$. We leave the workspace register $\regA$ implicit when writing $y \gets \widetilde{M}_{\theta,f,k,L} \circ A^{\Ver_{k,\cdot,\cdot}(\cdot)} \circ \Enc_k(\regM)$, and note that $ \widetilde{M}_{\theta,f,k,L}$ only operates on $\regC$.

Next, we describe a weaker security property that is immediately implied by <ref>, but will be convenient to use in our application to obfuscation.

For any linear operation $L$, bases $\theta \in \{0,1,\bot\}^n$, $f : \{0,1\}^{|\MS|} \to \{0,1\}^*$, $n$-qubit state $\ket{\psi}$, and set $B \subset \{0,1\}^*$ such that
\[\Pr[y \in B : y \gets M_{\theta,f} \circ L (\ket{\psi})] = 0,\]
it holds that for any oracle-aided adversary $A : \regC \to \regC$,
\[\Pr\left[y \in B : \begin{array}{r} k \gets \Gen(1^\secp,1^n) \\ y \gets \widetilde{M}_{\theta,f,k,L} \circ A^{\Ver_{k,\cdot,\cdot}(\cdot)} \circ \Enc_k (\ket{\psi})\end{array}\right] = 2^{-\Omega(\secp)}.\]

Finally, we define a notion of privacy, which states that any two encoded states are indistinguishable, even given the verification oracle.

For any $n$-qubit states $\ket{\psi_0},\ket{\psi_1
}$ and oracle-aided binary outcome projector $D$,

\[\bigg|\Pr_{k \gets \Gen(1^\secp,n)}\left[1 \gets D^{\Ver_{k,\cdot,\cdot}(\cdot)} \circ \Enc_k(\ket{\psi_0})\right] - \Pr_{k \gets \Gen(1^\secp,n)}\left[1 \gets D^{\Ver_{k,\cdot,\cdot}(\cdot)} \circ \Enc_k(\ket{\psi_1})\right]\bigg| = 2^{-\Omega(\secp)}.\]

§.§ Construction

Paulis and updates. We specify several notational conventions regarding sets $\{x_i\}_{i \in [n]}, \{z_i\}_{i \in [n]}$ that describe Pauli corrections on $n$ registers.

* As $n$ will be clear from context, let $x \coloneqq (x_1,\dots,x_n)$ and $z \coloneqq (z_1,\dots,z_n)$.

* Given a linear operation $L$ on $n$ qubits, let $L(x,z) \coloneqq (x_L,z_L)$ be the result of starting with $(x,z)$, and, for each  CNOT gate in $L$, sequentially applying the CNOT update rule $(x_i,z_i),(x_j,z_j) \to (x_i, z_i \oplus z_j), (x_i \oplus x_j, z_j)$. Note that this is yet another interpretation for $L$, which in another context could refer to the unitary that applies the sequence of CNOT gates.

* Let $L^{-1}$ be the inverse of $L$, and note that $L^{-1}(x_L,z_L) = (x,z)$.

* Given $x = (x_1,\dots,x_n)$ or $x_L = (x_{L,1},\dots,x_{L,n})$ and a subset $\MS \subseteq [n]$, let $x_\MS \coloneqq \{x_i\}_{i \in \MS}$ and $x_{L,\MS} \coloneqq \{x_{L,i}\}_{i \in \MS}$. Given disjoint sets $\MS_0,\MS_1 \subset [n]$, we let $x_{\MS_0},x_{\MS_1}$ refer to the union $\{x_i\}_{i \in \MS_0} \cup \{x_i\}_{i \in \MS_1}$.

Given a $\secp$-dimensional subspace $S \subset \bbF_2^{2\secp+1}$ and a vector $\Delta \in \bbF_2^{2\secp+1} \setminus S$, define the $(\secp+1)$-dimensional subspace
$$S_\Delta \coloneqq S \cup (S+\Delta).$$

Let the dual subspace of $S_{\Delta}$ be $\widehat{S} \coloneqq S_\Delta^\bot$; note that

* $\widehat{S}$ is $\secp$-dimensional; and

* since $S_{\Delta} \supset S$, its dual subspace $\widehat{S} := S_{\Delta}^\perp \subset S^\perp$.

Let $\widehat{\Delta}$ be an arbitrary choice of a vector such that $S^\bot = \widehat{S} \cup (\widehat{S} + \widehat{\Delta})$, and define
$$\widehat{S}_{\widehat{\Delta}} \coloneqq S^\bot = \widehat{S} \cup (\widehat{S} + \widehat{\Delta})~.$$

Given a subspace $S$, define the state
\[\ket{S} \coloneqq \frac{1}{\sqrt{|S|}}\sum_{s \in S}\ket{s},\]
and note that
\[H^{\otimes 2\secp+1}\ket{S} = \ket*{S^\bot}.\]

Next, given any $\secp$-dimensional subspace $S$ and $\Delta \notin S$, define the isometry $E_{S,\Delta}$ from 1 qubit to $2\secp+1$ qubits that maps $\ket{0} \to \ket{S}$ and $\ket{1} \to \ket{S+\Delta}$.

Publicly-verifiable linearly-homomorphic QAS with classically-decodable ZX measurementsOur construction of a publicly-verifiable linearly-homomorphic QAS with classically-decodable ZX measurements.fig:authscheme

* $\Gen(1^\secp,n)$: Sample a uniformly random $\secp$-dimensional subspace $S \subset \bbF_2^{2\secp+1}$, vector $\Delta \gets \bbF_2^{2\secp+1} \setminus S$, and $x_i,z_i \gets \bbF_2^{2\secp+1}$ for each $i \in [n]$. Output $k \coloneqq (S,\Delta,x,z)$.

* $\Enc_k = X^x Z^z E_{S,\Delta}^{\otimes n}.$

* $\LinEval_L(\regC)$: Parse register $\regC = \regC_1 \otimes \dots \otimes \regC_n$, where each $\regC_i$ is a $(2\secp+1)$-qubit register. For each CNOT in $L$ from qubit $i$ to $j$, apply $\mathsf{CNOT}^{\otimes 2\secp+1}$ from register $\regC_i$ to $\regC_j$.

* $\Dec_{k,L,\theta}(c)$: Parse $c = \{c_i\}_{i \in \MS}$. Define $\{m_i\}_{i \in \MS}$ as follows.
\[\forall i \in \MS_0: m_i = \begin{cases}0 \text{ if } c_i \in S + x_{L,i} \\ 1 \text{ if } c_i \in S + \Delta+ x_{L,i} \\ \bot \text{ otherwise}\end{cases} ~~~~~ \forall i \in \MS_1: m_i = \begin{cases}0 \text{ if } c_i \in \widehat{S} + z_{L,i} \\ 1 \text{ if } c_i \in \widehat{S} + \widehat{\Delta}+ z_{L,i} \\ \bot \text{ otherwise}\end{cases}\]
If any $m_i = \bot$, then output $\bot$, and otherwise output $m = \{m_i\}_{i \in \MS}$.

* $\Ver_{k,L,\theta}(c)$:[This procedure is already determined by $\Dec_{k,L,\theta}(c)$, but we write it explicitly for clarity in the proof.]  Parse $c = \{c_i\}_{i \in \MS}$. For each $i \in \MS_0$, output $\bot$ if $c_i \notin S_\Delta + x_{L,i}$. For each $i \in \MS_1$, output $\bot$ if $c_i \notin \widehat{S}_{\widehat{\Delta}} + z_{L,i}$. Otherwise, output $\top$.

The QAS described in fig:authscheme satisfies correctness (<ref>).

First, we show two key claims.

For any $S$ and $\Delta$, it holds that $H^{\otimes 2\secp+1}E_{\widehat{S},\widehat{\Delta}} = E_{S,\Delta}H$.

We show that the maps are equivalent by checking their behavior on the basis $\{\ket{+},\ket{-}\}$. First,

\begin{align*}
H^{\otimes 2\secp+1}E_{\widehat{S},\widehat{\Delta}}\ket{+} = H^{\otimes 2\secp+1}\ket*{\widehat{S}_{\widehat{\Delta}}} = \ket{S} = E_{S,\Delta}\ket{0} = E_{S,\Delta}H\ket{+}.
\end{align*}

\begin{align*}
H^{\otimes 2\secp+1}E_{\widehat{S},\widehat{\Delta}}\ket{-} = H^{\otimes 2\secp+1}\left(\ket*{\widehat{S}} - \ket*{\widehat{S} + \widehat{\Delta}}\right)= H^{\otimes 2\secp + 1}Z^{\Delta}\ket*{\widehat{S}_{\widehat{\Delta}}} = \ket*{S+\Delta} = E_{S,\Delta}\ket{1} = E_{S,\Delta}H\ket{-}.
\end{align*}

For any $S,\Delta$, and $L$, $\LinEval_LE_{S,\Delta}^{\otimes n} = E_{S,\Delta}^{\otimes n}L$

We show this for the case where $L$ contains a single CNOT gate, and the full proof follows by applying the argument sequentially. We show that the maps are equivalent by checking their behavior on the basis $\{\ket{b_1,b_2}\}_{b_1,b_2 \in \{0,1\}}$.

\begin{align*}
&\mathsf{CNOT}^{\otimes 2\secp+1}E_{S,\Delta}^{\otimes 2}\ket{b_1,b_2}\\
&= \mathsf{CNOT}^{\otimes 2\secp+1}\ket{S+b_1 \cdot \Delta}\ket{S + b_2 \cdot \Delta}\\
&= \frac{1}{2^{\secp}}\mathsf{CNOT}^{\otimes 2\secp+1} \sum_{s_1 \in S}\ket{s_1 + b_1 \cdot \Delta}\sum_{s_2 \in S}\ket{s_2 + b_2 \cdot \Delta}\\
&= \frac{1}{2^{\secp}} \sum_{s_1 \in S}\ket{s_1 + b_1 \cdot \Delta}\sum_{s_2 \in S}\ket{(s_1 + s_2) + (b_1 + b_2) \cdot \Delta}\\
&= \ket{S+b_1 \cdot \Delta}\ket{S + (b_1 + b_2) \cdot \Delta}\\
&= E_{S,\Delta}^{\otimes 2}\mathsf{CNOT}\ket{b_1,b_2}.
\end{align*}

Now, define measurements $M'_{\theta,f},\widetilde{M}'_{\theta,f,k,L}$ so that
\[M_{\theta,f} = H^{\MS_1}M'_{\theta,f}H^{\MS_1}, ~~ \text{ and } ~~ \widetilde{M}_{\theta,f,k,L} = H^{\widetilde{\MS}_1}X^{x_{L,\MS_0},z_{L,\MS_1}}\widetilde{M}'_{\theta,f,k,L}X^{x_{L,\MS_0},z_{L,\MS_1}}H^{\widetilde{\MS}_1}.\]

To be concrete,

\[M'_{\theta,f} \coloneqq \left\{\sum_{m : f(m_\MS) = y}\ketbra{m}{m}\right\}_{y},\]
\[\widetilde{M}'_{\theta,f,k,L} \coloneqq \left\{\sum_{m : f(m_\MS) = y}\left(\sum_{\substack{c : \{c_i \in S+m_i \cdot \Delta\}_{i \in \MS_0},\\ \{c_i \in \widehat{S}+m_i \cdot \widehat{\Delta}\}_{i \in \MS_1}}}\ketbra{c}{c}\right)\right\}_{y} \cup \left\{\sum_{\substack{c: \exists i \in \MS_0 \text{ s.t. } c_i \notin S_\Delta\\ \ \ \vee \exists i \in \MS_1 \text{ s.t. }c_i \notin \widehat{S}_{\widehat{\Delta}}}}\ketbra{c}{c}\right\}.\]

Observe that

\[\widetilde{M}'_{\theta,f,k,L}\left(E_{S,\Delta}^{\otimes |\MS_\bot \cup \MS_0|} \otimes E_{\widehat{S},\widehat{\Delta}}^{\otimes |\MS_1|}\right) = \left(E_{S,\Delta}^{\otimes |\MS_\bot \cup \MS_0|} \otimes E_{\widehat{S},\widehat{\Delta}}^{\otimes |\MS_1|}\right)M'_{\theta,f}.\]

\begin{align*}
&=\LinEval_L^\dagger\widetilde{M}_{\theta,f,k,L}\LinEval_L X^xZ^zE_{S,\Delta}^{\otimes n}  \\
&=\LinEval_L^\dagger\widetilde{M}_{\theta,f,k,L}X^{x_L}Z^{z_L} \LinEval_LE_{S,\Delta}^{\otimes n}\\
&=\LinEval_L^\dagger\widetilde{M}_{\theta,f,k,L}X^{x_L}Z^{z_L}E^{\otimes n}_{S,\Delta}L \tag{\cref{claim:linear}}\\
&=\LinEval_L^\dagger H^{\widetilde{\MS}_1}X^{x_{L,\MS_0}z_{L,\MS_1}}\widetilde{M}'_{\theta,f,k,L}X^{x_{L,\MS_0},z_{L,\MS_1}}H^{\widetilde{\MS}_1}X^{x_L}Z^{z_L}E^{\otimes n}_{S,\Delta}L\\
&=\LinEval_L^\dagger H^{\widetilde{\MS}_1}X^{x_{L,\MS_0}z_{L,\MS_1}}\widetilde{M}'_{\theta,f,k,L}X^{x_{L,\MS_\bot}}Z^{z_{L,\MS_\bot},z_{L,\MS_0},x_{L,\MS_1}}H^{\widetilde{\MS}_1}E^{\otimes n}_{S,\Delta}L\\
&=\LinEval_L^\dagger H^{\widetilde{\MS}_1}X^{x_{L,\MS_\bot},x_{L,\MS_0},z_{L,\MS_1}}Z^{z_{L,\MS_\bot},z_{L,\MS_0},x_{L,\MS_1}}\widetilde{M}'_{\theta,f,k,L}H^{\widetilde{\MS}_1}E^{\otimes n}_{S,\Delta}L\\
&=\LinEval_L^\dagger X^{x_L}Z^{z_L}H^{\widetilde{\MS}_1}\widetilde{M}'_{\theta,f,k,L}H^{\widetilde{\MS}_1}E^{\otimes n}_{S,\Delta}L\\
&=\LinEval_L^\dagger X^{x_L}Z^{z_L}H^{\widetilde{\MS}_1}\widetilde{M}'_{\theta,f,k,L}\left(E_{S,\Delta}^{\otimes |\MS_\bot \cup \MS_0|} \otimes E_{\widehat{S},\widehat{\Delta}}^{\otimes |\MS_1|}\right)H^{\MS_1}L \tag{\cref{claim:Hadamard}}\\
&=\LinEval_L^\dagger X^{x_L}Z^{z_L}H^{\widetilde{\MS}_1}\left(E_{S,\Delta}^{\otimes |\MS_\bot \cup \MS_0|} \otimes E_{\widehat{S},\widehat{\Delta}}^{\otimes |\MS_1|}\right)M'_{\theta,f}H^{\MS_1}L \\
&=\LinEval_L^\dagger X^{x_L}Z^{z_L}E^{\otimes n}_{S,\Delta}H^{\MS_1}M'_{\theta,f}H^{\MS_1}L \\
&=X^xZ^z\LinEval_L^\dagger E^{\otimes n}_{S,\Delta}M_{\theta,f}L\\
&=X^xZ^z E^{\otimes n}_{S,\Delta}L^\dagger M_{\theta,f}L\\
&=\Enc_{k}L^\dagger M_{\theta,f}L.
\end{align*}

§.§ Security

The QAS described in fig:authscheme satisfies security (<ref>).

We begin by modifying the $\Gen$ procedure and $\Ver_{k,\cdot,\cdot}(\cdot)$ oracle, and arguing that the output of the experiment remains (almost) unaffected. In particular, we will "expand" the verification oracle with random superspaces $R \supset S_\Delta$ and $\widehat{R} \supset \widehat{S}_{\widehat{\Delta}}$. Consider the following procedures.

* $\Gen'(1^\secp,n)$: Sample a uniformly random $\secp$-dimensional subspace $S \subset \bbF_2^{2\secp+1}$, vector $\Delta \gets \bbF_2^{2\secp+1} \setminus S$, and $x_i,z_i \gets \bbF_2^{2\secp+1}$ for each $i \in [n]$. Sample uniformly random $(3\secp/2 + 1)$-dimensional subspaces $R,\widehat{R} \subset \bbF_2^{2\secp+1}$ conditioned on $S_\Delta \subset R$ and $\widehat{S}_{\widehat{\Delta}} \subset \widehat{R}$. Output $k \coloneqq (S,\Delta,x,z)$ along with $(R,\widehat{R})$.

* $\Ver_{k,R,\widehat{R},L,\theta}'(c)$: Parse $c = \{c_i\}_{i \in \MS}$. For each $i \in \MS_0$, output $\bot$ if $c_i \notin R + x_{L,i}$. For each $i \in \MS_1$, output $\bot$ if $c_i \notin \widehat{R} + z_{L,i}$. Otherwise, output $\top$.

For any $L,\theta,f,A$, and $\ket{\psi}$, it holds that

\begin{align*}
\left\{y : \begin{array} {r} k \gets \Gen(1^\secp,n) \\ y \gets \widetilde{M}_{\theta,f,k,L} \circ A^{\Ver_{k,\cdot,\cdot}(\cdot)} \circ \Enc_k(\ket{\psi})\end{array}\right\} \approx_{2^{-\Omega(\secp)}} \left\{y : \begin{array} {r} (k,R,\widehat{R}) \gets \Gen'(1^\secp,n) \\ y \gets \widetilde{M}_{\theta,f,k,L} \circ A^{\Ver'_{k,R,\widehat{R},\cdot,\cdot}(\cdot)} \circ \Enc_k(\ket{\psi})\end{array}\right\}.
\end{align*}

Note that these distributions can be sampled by a reduction given oracle access to either $(O[S_\Delta],O[\widehat{S}_{\widehat{\Delta}}])$ or $(O[R],O[\widehat{R}])$. Now, for any fixed $(\secp+1)$-dimensional subspaces $S_\Delta, \widehat{S}_\Delta$ and any vector $v$,
\[\Pr_{R,\widehat{R}}[v \in R \setminus S_\Delta \cup \widehat{R} \setminus \widehat{S}_{\widehat{\Delta}}] \leq \frac{|R \setminus S_\Delta|}{|\bbF_2^{2\secp+1} \setminus S_\Delta |} + \frac{|\widehat{R} \setminus \widehat{S}_{\widehat{\Delta}}|}{|\bbF_2^{2\secp+1} \setminus \widehat{S}_{\widehat{\Delta}} |} = 2 \cdot \frac{2^{3\secp/2+1} - 2^{\secp+1}}{2^{2\secp+1} - 2^{\secp+1}} = 2^{-\Omega(\secp)},\]
where the probability is over sampling random $(3\secp/2+1)$-dimensional subspaces $R,\widehat{R}$ conditioned on $S_\Delta \subset R$ and $\widehat{S}_{\widehat{\Delta}} \subset \widehat{R}$. Then the claim follows by noting that $(O[S_\Delta],O[\widehat{S}_{\widehat{\Delta}}])$ and $(O[R],O[\widehat{R}])$ are identical outside of $R \setminus S_\Delta$ and $\widehat{R} \setminus \widehat{S}_\Delta$, and applying <ref> (a standard oracle hybrid argument).

Now, fix any $(3\secp/2+1)$-dimensional subspaces $R,\widehat{R}$ such that $\widehat{R}^\bot \subset R$, and consider the following procedure.

* $\Gen'_{R,\widehat{R}}(1^\secp,n)$: Sample a uniformly random subspace $S \subset \bbF_2^{2\secp+1}$ conditioned on $\widehat{R}^\bot \subset S \subset R$, sample a uniformly random vector $\Delta \gets R \setminus S$, and sample uniformly random $x_i^R,z_i^{\widehat{R}} \gets (R,\widehat{R})$ for each $i \in [n]$. Set $x^R = (x_1^R,\dots,x_n^R), z^{\widehat{R}} = (z_1^{\widehat{R}},\dots,z_n^{\widehat{R}})$ and output $(S,\Delta,x^R,z^{\widehat{R}})$.

Next, let $\co(R)$ be an arbitrary set of coset representatives of $R$, let $\co(\widehat{R})$ be an arbitrary set of coset representatives of $\widehat{R}$, and fix any

\[x^{\co(R)} = \left(x_1^{\co(R)},\dots,x_n^{\co(R)}\right), ~~~ z^{\co(\widehat{R})} = \left(z_1^{\co(\widehat{R})},\dots,z_n^{\co(\widehat{R})}\right),\]
where each $x_i^{\co(R)} \in \co(R)$ and $z_i^{\co(\widehat{R})} \in \co(\widehat{R})$. Then the proof of the theorem follows by combining <ref> with the following claim. Notice that the adversary $A$ in the following claim no longer requires access to the "expanded" oracle $\Ver'_{k,R,\widehat{R},\cdot,\cdot}(\cdot)$, since $A$ is allowed to depend on $\left(R,\widehat{R},x^{\co(R)},z^{\co(\widehat{R})}\right)$, which suffice to implement $\Ver'_{k,R,\widehat{R},\cdot,\cdot}(\cdot)$.

Fix any $R,\widehat{R},x^{\co(R)},z^{\co(\widehat{R})}$. Then for any $L,\theta,f$, and unitary $A$,[As noted in <ref>, by introducing a sufficiently large workspace register $\regA$ initialized to $\ket{0}$, we can assume without loss of generality that the adversary $A$ is unitary. This additional workspace register $\regA$ is left implicit in the description of the claim and proof.] there exists an $\epsilon = \epsilon(\secp) \in [0,1]$ such that for any $\ket{\psi}$,

\begin{align*}
\left\{y : \begin{array}{r} \left(S,\Delta,x^{R},z^{\widehat{R}}\right) \gets \Gen'_{R,\widehat{R}}(1^\secp,n) \\  x \coloneqq x^{R} + x^{\co(R)}, z \coloneqq z^{\widehat{R}} + z^{\co(\widehat{R})} \\ k \coloneqq (S,\Delta,x,z)\\ y \gets \widetilde{M}_{\theta,f,k,L} \circ A \circ \Enc_k(\ket{\psi})\end{array}\right\} \approx_{2^{-\Omega(\secp)}} (1-\epsilon)\left\{y: y \gets M_{\theta,f} \circ L(\ket{\psi})\right\} + \epsilon \left\{\bot\right\}.
\end{align*}

Let $\cD$ be the distribution described by the LHS of the statement in the claim. Next, define $x^{\co(R)}_L,z^{\co(\widehat{R})}_L \coloneqq L(x^{\co(R)},z^{\co(\widehat{R})})$, and define the distribution $\cK_L$ as follows.

\[\cK_L \coloneqq \left\{(S,\Delta,x_L,z_L) : \begin{array}{r} \left(S,\Delta,x^{R},z^{\widehat{R}}\right) \gets \Gen'_{R,\widehat{R}}(1^\secp,n) \\ x^R_L,z^{\widehat{R}}_L \coloneqq L(x^R,z^{\widehat{R}})  \\ x_L \coloneqq x^R_L + x^{\co(R)}_L, z_L \coloneqq z^{\widehat{R}}_L + z^{\co(\widehat{R})}_L\end{array}\right\}.\]

Observe that the distribution over $k = (S,\Delta,x,z)$ as sampled by $\cD$ is equivalent to the distribution that results from sampling  $(S,\Delta,x_L,z_L) \gets \cK_L$ and setting $(x,z) = L^{-1}(x_L,z_L)$. Thus, we can write $\cD$ equivalently as

\[\cD = \left\{y : \begin{array}{r} \left(S,\Delta,x_L,z_L\right) \gets \cK_L \\ (x,z) \coloneqq L^{-1}(x_L,z_L) \\ k \coloneqq \left(S,\Delta,x,z\right) \\ y \gets \widetilde{M}_{\theta,f,k,L} \circ A \circ \Enc_k(\ket{\psi})\end{array}\right\}.\]

Moreover, the vectors $(x_L,z_L)$ obtained by sampling $(S,\Delta,x_L,z_L) \gets \cK_L$ are such that $x_L$ and $z_L$ are uniformly random over an affine subspaces, namely,
\[x_L \gets R^{\oplus n} + x^{\co(R)}_L, \ \ \ \text{and } \ \ \ z_L \gets \widehat{R}^{\oplus n} + z^{\co(\widehat{R})}_L.\]

This follows because $L$ is full rank, and the vectors $x^R,z^{\widehat{R}} = (x_1^R,\dots,x_n^R),(z_1^{\widehat{R}},\dots,z_n^{\widehat{R}})$ obtained by sampling
\[\left(S,\Delta,x^{R},z^{\widehat{R}}\right) \gets \Gen'_{R,\widehat{R}}(1^\secp,n)\]
are such that each $x_i^R$ is uniformly random over $R$ and each $z_i^{\widehat{R}}$ is uniformly random over $\widehat{R}$. The fact that $x_L$ and $z_L$ are uniform over affine subspaces will be used later in the proof when we apply the Pauli twirl over affine subspaces (<ref>).

Next, we introduce some more notation.

* For each $y \in \mathsf{range}(f)$, define
\[V_y \coloneqq \bigcup_{m: f\left(m_\MS\right)=y}  \left(\bigotimes_{i \in \MS_0} \left(S + m_i \cdot \Delta\right) \bigotimes_{i \in \MS_1} \left(\widehat{S} + m_i \cdot \widehat{\Delta}\right)\right),\]
and define

\[V_\bot \coloneqq  \{0,1\}^{(2\secp + 1)n} \setminus \bigcup_{y \in \mathsf{range}(f)}V_y.\]
For $y \in \mathsf{range}(f) \cup \{\bot\}$, define $\ket{V_y} \coloneqq \sum_{v \in V_y}\ket{v}$.

* Define the unitary $B \coloneqq A \circ \LinEval_L^\dagger$. Note that the "honest" $A$ operation just applies $\LinEval_L$, so in this case $B$ is the identity.

* For any pure state $\ket{\phi}$, define $\Mx[\ket{\phi}] \coloneqq \ketbra{\phi}{\phi}.$

Now, given any $(S,\Delta,x_L,z_L) \in \cK_L$, which defines $(x,z) = L^{-1}(x_L,z_L)$, and any $y \in \mathsf{range}(f) \cup \{\bot\}$, we can write the probability that $\cD$ outputs $y$ as

\begin{align*}
&\left\| \Pi[V_y]X^{x_{L,\MS_0},z_{L,\MS_1}}H^{\widetilde{\MS}_1}A\Enc_{(S,\Delta,x,z)}\ket{\psi}\right\|^2 \\
&= \left\| \Pi[V_y]X^{x_{L,\MS_0},z_{L,\MS_1}}H^{\widetilde{\MS}_1}B\LinEval_L X^x Z^z E_{S,\Delta}^{\otimes n}\ket{\psi}\right\|^2 \\
&= \left\| \Pi[V_y]H^{\widetilde{\MS}_1}X^{x_{L,\MS_0}}Z^{z_{L,\MS_1}}B X^{x_L} Z^{z_L} E_{S,\Delta}^{\otimes n}L\ket{\psi}\right\|^2 \\
&= \left\| \Pi[V_y]H^{\widetilde{\MS}_1}X^{x_L}Z^{z_L}B X^{x_L} Z^{z_L} E_{S,\Delta}^{\otimes n}L\ket{\psi}\right\|^2,
\end{align*}

where in the last line, we have inserted Pauli $X$ operations on registers that are either measured in the Hadamard basis or not measured at all and Pauli $Z$ operations on registers that are either measured in the standard basis or not measured at all. Doing this has no effect on the outcome. Thus, we can write the distribution $\cD$ concisely as

\begin{align*}
\cD = \sum_{y \in \mathsf{range}(f) \cup \{\bot\}} \ketbra{y}{y} \frac{1}{|\cK_L|}\sum_{\left(S,\Delta,x_L,z_L\right) \in \cK_L}\bra{V_y}\Mx\left[H^{\widetilde{\MS}_1} Z^{z_{L}}X^{x_{L}} BX^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi}\right]\ket{V_y}.
\end{align*}

To complete the proof, we will decompose $B$ as a sum of Paulis, and factor out terms that will cause $\cD$ to output $\bot$ (with high probability). Eventually, we'll be left with terms that do not affect the outcome of directly measuring $L\ket{\psi}$. To begin with, let

\[\cP \coloneqq \left\{X^xZ^z : x = (x_1,\dots,x_n),z=(z_1,\dots,z_n) \in \{0,1\}^{(2\secp+1)n}\right\},\]
and define the subsets

\[\cP_\bot \coloneqq \left\{X^xZ^z : \exists i \in \MS_0 \text{ s.t. } x_i \notin R \text{ or } \exists i \in \MS_1 \text{ s.t. } z_i \notin \widehat{R}\right\}, ~~~~~~ \cP_\top = \cP \setminus \cP_\bot.\]

Then we can write $B$ as
\[B = \sum_{P \in \cP_\top} \alpha_P P  + \sum_{P \in \cP_\bot}\alpha_P P \coloneqq B_\top + B_\bot,\]
for some coefficients $\alpha_P$.

Note that for any $y \in \mathsf{range}(f)$, $\left(S,\Delta,x_L,z_L\right) \in \cK_L$, and $P \in P_\bot$,

\[\bra{V_y}H^{\widetilde{\MS}_1} Z^{z_L}X^{x_L}P X^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi} = 0,\]
which follows by definition of $V_y$, since $S_\Delta \subset R$ and $\widehat{S}_{\widehat{\Delta}} \subset \widehat{R}$. Thus there exists an $\epsilon_\bot$ such that

\[\cD = \sum_{y \in \mathsf{range}(f) \cup \{\bot\}} \ketbra{y}{y} \frac{1}{|\cK_L|}\sum_{\left(S,\Delta,x_L,z_L\right)}\bra{V_y}\Mx\left[H^{\widetilde{\MS}_1} Z^{z_{L}}X^{x_{L}} B_\top X^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi}\right]\ket{V_y} + \epsilon_\bot \ketbra{\bot}{\bot}.\]

Next, we define the following.

* Let $C \simeq R / \widehat{R}^\bot$ be a subspace of coset representatives of $\widehat{R}^\bot$ in $R$.

* Let $\widehat{C} \simeq \widehat{R} / R^\bot$ be a subspace of coset representatives of $R^\bot$ in $\widehat{R}$.

* Define the set of Paulis

\begin{align*}&\cP_{C,\widehat{C}} \coloneqq \left\{X^x Z^z : \begin{array}{c}\left\{x_i \in C, z_i = 0^{2\secp+1}\right\}_{i \in \MS_0}, \left\{x_i = 0^{2\secp+1}, z_i \in \widehat{C}\right\}_{i \in \MS_1}, \\ \left\{x_i = 0^{2\secp+1}, z_i = 0^{2\secp+1}\right\}_{i \in \MS_\bot}\end{array}\right\}.
\end{align*}

Now, for any $(x,z) = (x_1,\dots,x_n,z_1,\dots,z_n)$ such that $P  = X^xZ^z \in \cP_\top$, define $(x',z') = (x_1',\dots,x_n',z_1',\dots,z_n')$ such that $X^{x'}Z^{z'} \in \cP_{C,\widehat{C}}$ as follows.

* For $i \in \MS_0$, let $x_i' \in C$ be the representative of $x_i$'s coset (recall that $x_i \in R$ by definition of $\cP_\top$), and let $z_i' = 0^{2\secp+1}$.

* For $i \in \MS_1$, let $z_i' \in \widehat{C}$ be the representative of $z_i$'s coset (recall that $z_i \in \widehat{R}$ by definition of $\cP_\top$), and let $x_i' = 0^{2\secp+1}$.

* For $i \in \MS_\bot$, let $x'_i = 0^{2\secp+1}, z_i' = 0^{2\secp+1}$.

Then note that for all $y \in \mathsf{range}(f) \cup \{\bot\}$ and $\left(S,\Delta,x_L,z_L\right) \in \cK_L$, it holds that

\[\bra{V_y}H^{\widetilde{\MS}_1} Z^{z_L}X^{x_L}X^{x}Z^z X^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi} = \bra{V_y}H^{\widetilde{\MS}_1} Z^{z_L}X^{x_L}X^{x'}Z^{z'} X^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi},\]

which follows by definition of $V_y$ and the fact that $S,\widehat{S}$ are always sampled so that $\widehat{R}^\bot \subset S$ and $R^\bot \subset \widehat{S}$.

That is, we have identified for any $P \in \cP_\top$ a canonical $P' \in \cP_{C,\widehat{C}}$ for which $P'$ will have the same behavior as $P$ over all $\left(S,\Delta,x_L,z_L\right) \in \cK_L$. Thus, we can replace $B_\top$ in the expression for $\cD$ with
\[\sum_{P \in \cP_{C,\widehat{C}}}\alpha_P P\]
for some coefficients $\alpha_P$, and write $\cD$ as

\begin{align*}
&\sum_{y \in \mathsf{range}(f) \cup \{\bot\}} \ketbra{y}{y} \frac{1}{|\cK_L|}\sum_{\left(S,\Delta,x_L,z_L\right)}\bra{V_y}\Mx\left[H^{\widetilde{\MS}_1} Z^{z_{L}}X^{x_{L}} \left(\sum_{P \in \cP_{C,\widehat{C}}}\alpha_P P\right) X^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi}\right]\ket{V_y} \\ & ~~~~~~~ + \epsilon_\bot \ketbra{\bot}{\bot} \\
= &\sum_{y \in \mathsf{range}(f) \cup \{\bot\}} \ketbra{y}{y} \sum_{P_0,P_1 \in \cP_{C,\widehat{C}}}\alpha_{P_0}\alpha_{P_1}^*\frac{1}{|\cK_L|}\\&\hspace{2cm}\left(\sum_{\left(S,\Delta,x_L,z_L\right)}\bra{V_y}H^{\widetilde{\MS}_1} Z^{z_{L}}X^{x_{L}} P_0 X^{x_L}Z^{z_L}\Mx\left[E_{S,\Delta}^{\otimes n}L\ket{\psi}\right] Z^{z_L}X^{x_L} P_1^\dagger X^{x_{L}}Z^{z_{L}}H^{\widetilde{\MS}_1}\ket{V_y}\right)\\ & ~~~~~~~ + \epsilon_\bot \ketbra{\bot}{\bot}
\end{align*}

Now, we are finally ready to apply the the Pauli twirl over affine subspaces (<ref>). To do so, we make the following observations.

* As noted above, $x_L \gets R^{\oplus n} + x^{\co(R)}_L$, and $z_L \gets \widehat{R}^{\oplus n} + z^{\co(\widehat{R})}_L$ are uniformly random over affine subspaces of $R^{\oplus n}$ and $\widehat{R}^{\oplus n}$ respectively.

* Consider any $X^{x_0}Z^{z_0} \neq X^{x_1}Z^{z_1} \in \cP_{C,\widehat{C}}$. If $x_0 \neq x_1$, then there exists some index $i \in [n]$ such that $x_{0,i} \oplus x_{1,i} \notin \widehat{R}^\bot$ and thus, $x_0 \oplus x_1 \notin (\widehat{R}^{\oplus n})^\bot$. Otherwise, $z_0 \neq z_1$, and there exists some index $i \in [n]$ such that $z_{0,i} \oplus z_{1,i} \notin R^\bot$ and thus, $z_0 \oplus z_1 \notin (R^{\oplus n})^\bot$.

Then by <ref>, all the cross-terms $P_0 \neq P_1$ are killed in the above expression for $\cD$, which we can now write as

\begin{align*}
&\sum_{y \in \mathsf{range}(f) \cup \{\bot\}} \ketbra{y}{y} \sum_{P \in \cP_{C,\widehat{C}}}\alpha_P\alpha_P^*\frac{1}{|\cK_L|}\left(\sum_{\left(S,\Delta,x_L,z_L\right)}\bra{V_y}\Mx\left[H^{\widetilde{\MS}_1} Z^{z_{L}}X^{x_{L}} PX^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi}\right]\ket{V_y}\right)\\ & ~~~~~~~ + \epsilon_\bot \ketbra{\bot}{\bot},
\end{align*}

Finally, since $S,\Delta$ are chosen uniformly at random conditioned on $\widehat{R}^\bot \subset S_\Delta \subset R$, we have that for any fixed $P \in \cP_{C,\widehat{C}} \setminus \cI$,

\begin{align*}
&\sum_{y \in \mathsf{range}(f) \cup \{\bot\}} \frac{1}{|\cK_L|}\sum_{\left(S,\Delta,x_L,z_L\right)}\bra{V_y}\Mx\left[H^{\widetilde{\MS}_1} Z^{z_{L}}X^{x_{L}} PX^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi}\right]\ket{V_y}\\ &~~~~~ \leq \frac{|S_\Delta \setminus \widehat{R}_\bot|}{|R \setminus \widehat{R}_\bot|} + \frac{|\widehat{S}_{\widehat{\Delta}} \setminus R_\bot|}{|\widehat{R} \setminus R_\bot|} = 2 \cdot \frac{2^{\secp+1} - 2^\secp}{2^{3\secp/2+1} - 2^\secp} = 2^{-\Omega(\secp)}.
\end{align*}

Thus, $\cD$ is within $2^{-\Omega(\secp)}$ total variation distance of

\begin{align*}
&(1-\epsilon_\bot)\sum_y \ketbra{y}{y}\frac{1}{|\cK_L|}\sum_{\left(S,\Delta,x_L,z_L\right)}\bra{V_y}\Mx\left[H^{\widetilde{\MS}_1} Z^{z_{L}}X^{x_{L}} \cI X^{x_L}Z^{z_L}E_{S,\Delta}^{\otimes n}L\ket{\psi}\right]\ket{V_y} + \epsilon_\bot \ketbra{\bot}{\bot}\\
&= (1-\epsilon_\bot)\sum_y \ketbra{y}{y}\frac{1}{|\cK_L|}\sum_{\left(S,\Delta,x_L,z_L\right)}\bra{V_y}\Mx\left[H^{\widetilde{\MS}_1}E_{S,\Delta}^{\otimes n}L\ket{\psi}\right]\ket{V_y} + \epsilon_\bot \ketbra{\bot}{\bot} \\
&= (1-\epsilon_\bot)\sum_y \ketbra{y}{y}\left(\sum_{m : f(m) = y}\bra{m}\right)\Mx\left[H^{\MS_1}L\ket{\psi}\right]\left(\sum_{m : f(m) = y}\ket{m}\right) + \epsilon_\bot \ketbra{\bot}{\bot} \\
&= (1-\epsilon_\bot)\{y : y \gets M_{\theta,f} \circ L(\ket{\psi})\} + \epsilon_\bot\{\bot\},
\end{align*}

which completes the proof.

The QAS described in fig:authscheme satisfies privacy (<ref>).

First, recalling the definitions of $\Gen',\Ver'$ in the proof of <ref>, and applying the oracle indistinguishability argued during the proof of <ref>, it suffices to show that

\[\bigg|\Pr_{k,R,\widehat{R} \gets \Gen'(1^\secp,n)}\left[1 \gets A^{\Ver'_{k,R,\widehat{R},\cdot,\cdot}(\cdot)} \circ \Enc_k(\ket{\psi_0})\right] - \Pr_{k,R,\widehat{R} \gets \Gen'(1^\secp,n)}\left[1 \gets A^{\Ver'_{k,R,\widehat{R},\cdot,\cdot}(\cdot)} \circ \Enc_k(\ket{\psi_1})\right]\bigg| = 0.\]

To see this, we'll show that we can give enough information to $A$ for it to implement $\Ver'_{k,R,\widehat{R},\cdot,\cdot}(\cdot)$ while preserving sufficient randomness to one-time pad the input state.

Consider the following equivalent description of $\Gen'(1^\secp,n)$.

* Sample a uniformly random $\secp$-dimensional subspace $S \subset \bbF_2^{2\secp+1}$, vector $\Delta \gets \bbF_2^{2\secp+1} \setminus S$, and uniformly random $(3\secp/2 + 1)$-dimensional subspaces $R,\widehat{R} \subset \bbF_2^{2\secp+1}$ conditioned on $S_\Delta \subset R$ and $\widehat{S}_{\widehat{\Delta}} \subset \widehat{R}$.

* Let $H_\Delta$ be the $2\secp$-dimensional subspace perpendicular to $\Delta$ and $H_{\widehat{\Delta}}$ be the $2\secp$-dimensional subspace perpendicular to $\widehat{\Delta}$. For each $i \in [n]$, sample $x_{i,\Delta} \gets H_\Delta, b_i \gets \{0,1\}, z_{i,\widehat{\Delta}} \gets H_{\widehat{\Delta}}, c_i \gets \{0,1\}$, and define $x_i = x_{i,\Delta} + b_i \cdot \Delta$ and $z_i = z_{i,\widehat{\Delta}} + c_i \cdot \widehat{\Delta}$.

* Output $(S,\Delta,x,z),R,\widehat{R}$.

Now, fix any choice of $S,\Delta,R,\widehat{R},x_\Delta,z_{\widehat{\Delta}}$ sampled during the procedure $\Gen'(1^\secp,n)$, where $x_\Delta \coloneqq \left(x_{1,\Delta},\cdots,x_{n,\Delta}\right)$ and $z_{\widehat{\Delta}} \coloneqq \left(z_{1,\widehat{\Delta}},\cdots,z_{n,\widehat{\Delta}}\right)$, and consider the following procedure that completes the sampling of the key.

* For each $i \in [n]$, sample $b_i,c_i \gets \{0,1\}$, and define $x_i = x_{i,\Delta} + b_i \cdot \Delta$ and $z_i = z_{i,\widehat{\Delta}} + c_i \cdot \widehat{\Delta}$.

* Output $(S,\Delta,x,z)$.

Since the oracle $\Ver'_{k,R,\widehat{R},\cdot,\cdot}(\cdot)$ can be implemented given just the fixed information $S,\Delta,R,\widehat{R},x_\Delta,z_{\widehat{\Delta}}$, it suffices to show that for any $S,\Delta,R,\widehat{R},x_\Delta,z_{\widehat{\Delta}}$ and any adversary $A$ (whose description may depend on this information), it holds that

\[\bigg|\Pr_{k}\left[1 \gets A (\Enc_k(\ket{\psi_0}))\right] - \Pr_{k}\left[1 \gets A(\Enc_k(\ket{\psi_1}))\right]\bigg| = 0,\]

where the probability is over $k \gets \Gen'_{S,\Delta,R,\widehat{R},x_\Delta,z_{\widehat{\Delta}}}(1^\secp,n)$. Since

\[\Enc_k = X^x Z^z E^{\otimes n}_{S,\Delta} = X^{x_\Delta}Z^{z_{\widehat{\Delta}}}X^{b_1 \cdot \Delta \dots b_n \cdot \Delta}Z^{c_1 \cdots \widehat{\Delta} \dots c_n \cdot \widehat{\Delta}} E^{\otimes n}_{S,\Delta} = X^{x_\Delta}Z^{z_{\widehat{\Delta}}} E^{\otimes n}_{S,\Delta} X^{b_1 \dots b_n}Z^{c_1 \dots c_n},\]
this follows from the quantum one-time pad <cit.>. That is, we use the fact that

\[\sum_{b_1,\dots,b_n,c_1,\dots,c_n}\Mx\left[X^{b_1,\dots,b_n}Z^{c_1,\dots,c_n}\ket{\psi_0}\right] = \sum_{b_1,\dots,b_n,c_1,\dots,c_n}\Mx\left[X^{b_1,\dots,b_n}Z^{c_1,\dots,c_n}\ket{\psi_1}\right].\]

§ LINEAR + MEASUREMENT QUANTUM PROGRAMS

In this section, we show that any quantum program with classical input and output (<ref>) can be implemented using a "linear + measurement" ($\LM$) quantum program.

In slightly more detail, we make use of magic states in order to write any quantum circuit as an alternating sequence of linear operations $L_i$ (by which we mean a sequence of CNOT gates) and partial ZX measurements $M_{\theta_i,f_i}$, where the description of each $f_i$ may depend on the classical input $x$ as well as previous measurement results. We encourage the reader to review our notation for partial ZX measurements $M_{\theta_i,f_i}$ described at the beginning of <ref>. We remark here that these measurements are "partial" in two aspects: (i) they may only operate on a subset of the qubits, and (ii) each measurement outcome may be associated with multiple basis vectors, meaning that the input qubits are not necessarily fully collapsed. We also remark that for the purpose of this paper, we restrict attention to circuits with classical inputs and outputs, but note that one could consider circuits with quantum inputs and outputs as well.

We first formally define $\LM$ quantum programs, and accompany this with a diagram in <ref>.

An $\LM$ quantum program with classical input and output is described by:

* A quantum state $\ket{\psi}$ on $n$ qubits.

* Linear operations $L_1,\dots,L_{t+1}$, where each $L_i$ is a sequence of CNOT gates.

* Partial ZX measurements $M_{\theta_1,f_1^{(\cdot)}},M_{\theta_2,f_2^{(\cdot)}},\dots,M_{\theta_t,f_t^{(\cdot)}}$,$M_{\theta_{t+1},g^{(\cdot)}}$ defined by sets of bases $\{\theta_i\}_{i \in [t+1]}$ and classical functions $\{f_i^{(\cdot)}\}_{i \in [t]},g^{(\cdot)}$, which will be parameterized by the input $x$ as well as previous measurement results. In line with the notation introduced in <ref>, for each $i \in [t+1]$, we define $\MS_i \subseteq [n]$ be the set of wires such that $\theta_i \neq \bot$. That is, $\MS_i$ is the set of wires on which the $i$'th partial measurement operates.

Now, we will find it useful to introduce further notation drawing attention to which wires are simply measured in either the standard or Hamadard basis by the $i$'th partial ZX measurement, and which are not fully collapsed. In particular, we define disjoint sets $V_1,\dots,V_{t+1}$ and sets $W_1,\dots,W_t$ with the following properties.

* $\MS_1 = (V_1,W_1), \MS_2 = (V_1,V_2,W_2), \dots, \MS_t = (V_1,\dots,V_t,W_t), \MS_{t+1} = (V_1,\dots,V_{t+1}) = [n]$.

* The $i$'th measurement takes previously collapsed wires $V_1,\dots,V_{i-1}$ as input, "fully" collapses wires $V_i$, and "partially" collapses wires $W_i$. This will be made precise by the evaluation procedure defined below, where the $v_i$ are inputs from the $V_i$ wires and $w_i$ are inputs from the $W_i$ wires.

* Each $L_i$ does not operate on $\{V_j\}_{j < i}$. That is, fully collapsed registers are no longer computed on.

Finally, given an input $x \in \{0,1\}^m$, let $\LMEval\left(x,\ket{\psi},\{L_i\}_{i \in [t+1]},\{\theta_i\}_{i \in [t+1]},\{f_i\}_{i \in [t]},g\right) \to y$ be the formal evaluation procedure, defined as follows:

* Initialize an $n$-qubit register $\regM$ with $\ket{\psi}$.

* Compute $((v_1,r_1),\regM) \gets M_{\theta_1,f_1^x} \circ L_1(\regM)$, where $f_1^x(v_1,w_1) = (v_1,r_1)$.

* Compute $((v_2,r_2),\regM) \gets M_{\theta_2,f_2^{x,r_1}} \circ L_2 (\regM)$, where $f_2^{x,r_1}(v_1,v_2,w_2) = (v_2,r_2)$.

* …
* Compute $((v_t,r_t),\regM) \gets M_{\theta_t,f_t^{x,r_1,\dots,r_{t-1}}} \circ L_t(\regM)$, where $f^{x,r_1,\dots,r_{t-1}}_t(v_1,\dots,v_t,w_t) = (v_t,r_t)$.

* Compute output $y \gets M_{\theta_{t+1},g^{x,r_1,\dots,r_t}} \circ L_{t+1}(\regM)$, where $g^{x,r_1,\dots,r_t}(v_1,\dots,v_{t+1}) = y$.

[8]$\ket{\psi}$     [8]L_1         [6]L_2         [4]L_3    [8,nwires=5,6,7,8]M_θ_3,g^x,r_1,r_2[4]$V_3$     [4]$y$

[4]M_θ_1,f_1^x[wires=2]$W_1$          [wires=2]$V_2$     [2]$v_2$    [wires=2]$V_2$

[wires=2]$V_1$     [2]$v_1$      [wires=2]$V_1$      [2]$v_1$     [wires=2]$V_1$

1         1

$r_1$        $r_2$

Diagram of an $\LM$ quantum program. We use some non-standard quantum circuit notation, so we provide some explanation. Each partial ZX measurement $M_{\theta_1,f_1^{(\cdot)}}, M_{\theta_2,f_2^{(\cdot)}}, M_{\theta_3,g^{(\cdot)}}$ is applied to the wires coming from the left of the corresponding box, some of which may be classical. Some wires (namely, $V_1$, $V_2$, and $V_3$) are fully collapsed by the measurement, producing classical output wires coming from the right. Other wires (namely, $W_1$ and $W_2$) are only partially collapsed, so their corresponding output wires are still quantum. Additional classical outputs (namely, $r_1$ and $r_2$) are produced by these measurements, which are denoted by classical wires coming out of the bottom. Note that the description of later measurements depend on $r_1,r_2$. Finally, we remark that one could instead introduce explicit ancillary wires for the input $x$ and intermediate measurement results $r_1,r_2$, but writing the circuit in the manner above is visually suggestive of the structure of our eventual obfuscation scheme.

Observe that any alternating sequence of linear operations and partial ZX measurements may be written in the form introduced in the above definition, by simply defining each of the sets $V_i$ to be empty, and writing each function as $f_i^{x,r_1,\dots,r_{i-1}}(w_i) \to r_i$ (that is, we can always choose not to treat any of the wires as fully collapsed in the above formalism). So, why did we bother explicitly defining the $V_i$ and $W_i$ sets? The reason is that we will actually be interested in a “subclass” of $\LM$ quantum programs whose partially collapsed wires (the $W_i$ wires) have a particularly simple structure. The diagram shown in <ref> is indeed an example of such an $\LM$ quantum program.

An $\LM$ quantum program has standard-basis-collapsible $W$ wires if:

* $W_1,\dots,W_n$ consist of only standard basis indices, that is, $\theta_{i,j} = 0$ for $i \in [t]$ and $j \in W_i$.

* For $i \in [t]$, $W_i$ is disjoint from $\MS_1 \cup \dots \cup \MS_{i-1}$, and the operations $L_1,\dots,L_{i-1}$ are either classically controlled on or do not operate on $W_i$. In particular, for each $i \in [t]$, the entire operation of the $\LM$ program up to and including the $i$'th measurement is diagonal in the standard basis on the wires $W_i$.

This standard-basis-collapsible $W$ wires property ensures that if one were to measure ("collapse") the $W_1,\dots,\allowbreak W_n$ wires in the standard basis before executing the program, the $W_i$ wires would remain completely unaffected throughout the execution of the program up to and including the $i$'th measurement (though they could be affected after the $i$'th measurement). Note that this is not a correctness property, indeed, collapsing the $W_1,\dots,W_n$ wires at the beginning of the computation would likely completely change the desired functionality. However, it turns out that this property will be crucial for arguing the security of our obfuscation scheme in the following sections (in particular, refer to the "Collapsing the $\sF$ oracles" discussion in the proof intuition section, <ref>).

Any quantum program $(\ket{\psi},C)$ (<ref>) can be compiled into an equivalent $\LM$ quantum program $(\ket{\psi'},\{L_i\}_{i \in [t+1]},\{\theta_i\}_{i \in [t+1]},\{f_i\}_{i \in [t]},g)$ with standard-basis-collapsible $W$ wires, where $\{L_i\}_{i \in [t+1]},\allowbreak\{\theta_i\}_{i \in [t+1]},\allowbreak\{f_i\}_{i \in [t]},\allowbreak g$ only depend on the description of $C$ (and not $\ket{\psi}$). Moreover, the compiler runs in polynomial time in the size of its input $(\ket{\psi},C)$.

We will use a circuit representation very similar to that described in <cit.>, except for a key difference in how we implement the $T$ gate, inspired by the encrypted CNOT operation introduced in <cit.>. We write the quantum circuit $C$ using the $\{\CNOT,H,T\}$ universal gate set, where $T$ is the gate that applies a phase of $e^{i\pi/4}$. Given magic states, we'll show how to implement $H$ and $T$ gates using only CNOT gates and Pauli ($X$ and $Z$) gates controlled on the results of partial ZX measurements. Then, we will observe that the Pauli gates can be subsumed into the description of the measurements, leaving only layers of CNOT gates and partial ZX measurements.

First, we'll describe our implementations of the $H$ and $T$ gates and prove that they are correct. Then, we'll complete the proof with an inductive argument, showing how to build an $\LM$ quantum program one gate at a time.

$\ket{\psi}$     1     H       2

[2]$\ket{\phi_H}$          1

Z     X     $H\ket{\psi}$

Implementation of the $H$ gate with the $H$-magic state $\ket{\phi_H} \propto \ket{00} + \ket{01} + \ket{10} - \ket{11}$.

Implementing the $H$ gate. Following <cit.>, we use a two-qubit magic state
$$\ket{\phi_H} \propto \ket{00} + \ket{01} + \ket{10} - \ket{11}$$
to implement the Hadamard gate, via the circuit in Figure <ref>. For completeness, we show that the circuit indeed implements the Hadamard gate.

The circuit in Figure <ref> implements the Hadamard gate.

Write $\ket{\psi} = \alpha\ket{0} + \beta\ket{1}$. After the CNOT gate, the joint state of all three qubits can be written as

\begin{align*} \alpha \ket{000} + &\alpha\ket{001} + \alpha\ket{010} - \alpha \ket{011} + \beta\ket{100} - \beta\ket{101} + \beta\ket{110} + \beta \ket{111} \\
= & \Big((\alpha+\beta) \ket{+}\ket{00} + (\alpha-\beta)\ket{+}\ket{01}\Big) + \Big((\alpha+\beta)\ket{+}\ket{10} - (\alpha-\beta) \ket{+}\ket{11}\Big) \\
+ & \Big((\alpha-\beta) \ket{-}\ket{00} + (\alpha + \beta)\ket{-}\ket{01}\Big) + \Big(\alpha-\beta)\ket{-}\ket{10} - (\alpha+\beta)\ket{-}\ket{11}\Big)
\end{align*}

After the Hadamard basis measurement on the first wire resulting in a bit $x$ and the standard basis measurement on the second wire resulting in a bit $z$, the resulting state on the third wire is

\begin{align*}
(\alpha+\beta) \ket{0} + (\alpha-\beta)\ket{1} & = H\ket{\psi} & \hspace{.3in} \mbox{if $x=0$ and $z=0$} \\
(\alpha+\beta)\ket{0} - (\alpha-\beta) \ket{1} & = ZH\ket{\psi} & \hspace{.3in} \mbox{if $x=0$ and $z=1$}  \\
(\alpha-\beta) \ket{0} + (\alpha + \beta)\ket{1} & = XH\ket{\psi} & \hspace{.3in} \mbox{if $x=1$ and $z=0$} \\
(\alpha-\beta)\ket{0} - (\alpha+\beta)\ket{1}  & = ZXH\ket{\psi} & \hspace{.3in} \mbox{if $x=1$ and $z=1$}
\end{align*}

Applying the $Z$ and $X$ corrections now gives the state $H\ket{\psi}$.

$\ket{\psi}$           1

$\ket{\phi_T}$     -1     PX      $T\ket{\psi}$

$\ket{\psi}$     1      Z     X     $PX\ket{\psi}$

$\ket{\phi_{PX}}$           -1

$\ket{\psi}$           1     1     1

$\ket{\phi_T}$     -1     1[wires=2,steps=3,style=dashed, rounded corners,label style=yshift=-3 cm]$PX$     Z1     X    $T\ket{\psi}$

$\ket{\psi}$          [wires=4,style=dashed, rounded corners,label style=yshift=-5 cm]"$\sM$" layer 1         1     1

$\ket{\phi_T}$     -1     [wires=3,nwires=2][3]Γ_c         Z1     X    $T\ket{\psi}$

$\ket{\phi_{PX}}$         H     -1

Implementation of the $T$ gate. First, we combine an implementation of the $T$ gate using the $T$-magic state $\ket{\phi_T} \propto \ket{0} + e^{i\pi/4}\ket{1}$ (upper left) with an implementation of the $PX$ gate using the $PX$-magic state $\ket{\phi_{PX}} \propto i\ket{0} + \ket{1}$ (upper right) to obtain the circuit on the bottom left. This circuit includes a classically controlled CNOT gate, which is not supported by $\LM$ quantum programs. We replace the classically controlled CNOT with a classically controlled projective measurement to arrive at the circuit on the bottom right. Here, $\Gamma_c$ represents a measurement controlled on the bit $c$ from the first wire to be applied to the second and third wires. These wires are only partially collapsed by this measurement, so they remain quantum wires. However, $\Gamma_c$ also produces a measurement result $r$, which is carried on the classical wire coming from the right. The final $Z$ gate is controlled on the bit $c \cdot (r \oplus h)$, where $h$ is the result of measuring the third wire in the Hadamard basis. The dashed box will eventually become a measurement layer in our implementation of an $\LM$ circuit (though we remark that the input for this measurement will also include wires from previous $H$-gate and $T$-gate circuits).

Implementing the $T$ gate. We will use two magic states

$$ \ket{\phi_T} \propto \ket{0} + e^{i\pi /4} \ket{1} \hspace{.2in} \mbox{and} \hspace{.2in} \ket{\phi_{PX}} \propto i\ket{0} + \ket{1}

and the circuit on the bottom right of Figure <ref>. First, we clarify notation in the figure. $\Gamma_c$ is a projective measurement controlled on the bit $c$ from the first wire, and is defined as follows.

* $\Gamma_0 = \{\ketbra{00}{00} + \ketbra{10}{10}, \ketbra{01}{01} + \ketbra{11}{11}\}$. That is, it measures its second input in the standard basis.

* $\Gamma_1 = \{\ketbra{00}{00} + \ketbra{11}{11}, \ketbra{01}{01} + \ketbra{10}{10}\}$. That is, it measures the XOR of its two inputs.

The measurement $\Gamma_c$ is applied to the second and third wires, which remain quantum wires, and produces a classical bit $r$ indicating which of the two measurement results was observed. In this figure, this bit $r$ is carried on the classical wire coming from the right of $\Gamma_c$. In an abuse of notation, we will also use $\Gamma_c$ as a function to define measurement outcomes:

\begin{align*}\Gamma_0(00) & = \Gamma_0(10) = 0, \ \ \ \Gamma_0(01) = \Gamma_0(11) = 1, \\
\Gamma_1(00) & = \Gamma_1(11) = 0, \ \ \ \Gamma_1(01) = \Gamma_1(10) = 1
\end{align*}

The control logic for the $Z$ gate is $c \cdot (r \oplus h)$, where $c$ is the result of measuring the first wire, $r$ is the result of measuring $\Gamma_c$, and $h$ is the result of measuring the third wire in the Hadamard basis. We will now confirm this representation of the $T$ gate works as expected.

The bottom right circuit in Figure <ref> implements the $T$ gate.

Write $\ket{\psi} = \alpha\ket{0}+\beta\ket{1}$. Applying the first CNOT yields

\begin{align*}&\alpha\ket{00} + e^{i\pi/4}\beta\ket{01} + \beta\ket{10} + e^{i\pi/4}\alpha\ket{11}\\ &= \ket{0}(\alpha\ket{0} + e^{i\pi/4}\beta\ket{1}) + \ket{1}(\beta\ket{0} + e^{i\pi/4}\alpha\ket{1}).
\end{align*}

If the result of measuring the first wire is $c = 0$, the state on the second wire is already
\[\alpha\ket{0} + e^{i\pi/4}\beta\ket{1} = T\ket{\psi}.\]
In this case, we measure $\Gamma_0$, which only collapses the third wire, and neither the $Z$ nor $X$ corrections is applied to the second wire, which remains in the state $T\ket{\psi}$.

If the result of measuring the first wire is $c=1$, then the second wire is in the state
\[\beta\ket{0} + e^{i\pi/4}\alpha\ket{1}.\]

In this case, we measure $\Gamma_1$ on
\[(\beta\ket{0} + e^{i\pi/4}\alpha\ket{1})(i\ket{0}+\ket{1}).\]

If the result is $r=0$, the state has collapsed to

\begin{align*}
&i\beta\ket{00} + e^{i\pi/4}\alpha\ket{11} \\
&=e^{i\pi/4} \beta\ket{00} + \alpha\ket{11}\\
&=\left(e^{i\pi/4}\beta\ket{0} + \alpha\ket{1}\right)\ket{+} + \left(e^{i\pi/4}\beta\ket{0} - \alpha\ket{1}\right)\ket{-}\\
&=XT\ket{\psi}\ket{+} + ZXT\ket{\psi}\ket{-},
\end{align*}

so applying the $Z$ correction controlled on $c \cdot(r \oplus h) = h$ followed by the $X$ correction results in  $T\ket{\psi}$. If the result is $r=1$, the state has collapsed to

\begin{align*}
&\beta\ket{01} + ie^{i\pi/4}\alpha\ket{10} \\
&= e^{i\pi/4}\beta\ket{01} -\alpha\ket{10} \\
&= \left(e^{i\pi/4}\ket{0} - \alpha\ket{1}\right)\ket{+} - \left(e^{i\pi/4}\beta\ket{0} + \alpha\ket{1}\right)\ket{-}\\
&= ZXT\ket{\psi}\ket{+} - ZT\ket{\psi}\ket{-},
\end{align*}

so applying the $Z$ correction controlled on $c \cdot(r \oplus h) = 1\oplus h$ followed by the $X$ correction results in $T\ket{\psi}$.

Inductive argument. In order to carry out an inductive argument, we will first generalize the notion of an $\LM$ quantum program to support quantum output. We will actually allow the output to be correct up to some Pauli errors that can be computed by measuring some ancillary registers in the standard or Hadamard basis and applying a classical function to the measurement results.

First, we fix some notation. Throughout the proof, we'll keep track of disjoint sets of wires $V_1,\dots,V_t,V^*_{t+1},O$, where $V_1 \cup \dots \cup V_t \cup V^*_{t+1} \cup O = [n]$. We will also keep track of strings $v,\widehat{x},\widehat{z} \in \{0,1,\bot\}^n$, where $v$ denotes a subset of measurement results (from wires $V_1 \cup \dots \cup V_t \cup V^*_{t+1}$), and $\widehat{x},\widehat{z}$ denote Pauli corrections to be applied to the wires in $O$. For any set $V$, we let $v^{(V)}$ (resp. $\widehat{x}^{(V)},\widehat{z}^{(V)}$) be the string restricted to indices in the set $V$. In particular, for an index $i \in [n]$, $v^{(i)}$ is just the $i$'th entry of $v$. Finally, for each $i \in [t]$, we define $v_i \coloneqq v^{(V_i)}$, and we define $v^*_{t+1} \coloneqq v^{(V^*_{t+1})}$.

An $\LM$ quantum program with Pauli-encoded quantum output is defined like a standard $\LM$ quantum program (<ref>), except for the following differences.

* There is no final measurement $M_{\theta_{t+1},g^{(\cdot)}}$, and thus $\theta_{t+1}$ and $g^{(\cdot)}$ are undefined.

* The set $[n] \setminus (V_1 \cup \dots \cup V_t)$ consists of disjoint sets  $V^*_{t+1}$ and $O$, where $O$ contains the Pauli-encoded output. We will refer to $O$ as the "active" set of wires.

* There is a string $\theta^*_{t+1} \in \{0,1,\bot\}^n$ that is 0 or 1 on $V^*_{t+1}$ (determining whether these registers are measured in the standard or Hadamard basis) and $\bot$ everywhere else.

* There is a classical function $h(x,v_1,\dots,v_t,v^*_{t+1},r_1,\dots,r_t) \to \{0,1\}^{2|O|}$ that operates on the program input $x$ and previous measurement results, and outputs Pauli corrections $\widehat{x}^{(O)},\widehat{z}^{(O)} \in \{0,1\}^{|O|}$ to be applied to the $O$ registers.

Note that the program is defined by a state $\ket{\psi}$ along with $\{L_i\}_{i \in [t+1]},\{\theta_i\}_{i \in [t]},\{f_i^{(\cdot)}\}_{i \in [t]},\theta^*_{t+1},h$.

First, the following claim will confirm that it suffices to compile the quantum program $(\ket{\psi},C)$ into an $\LM$ quantum program with Pauli-encoded quantum output.

Consider any $\LM$ quantum program with Pauli-encoded quantum output that computes a classical output functionality. That is, the (Pauli encoding of the) output we are interested in is determined by measuring the $O$ registers in the standard basis. Then, this program can be written as a standard $\LM$ quantum program (<ref>).

It suffices to define the final measurement $M_{\theta_{t+1},g^{(\cdot)}}$. Set $\theta_{t+1} \in \{0,1\}^n$ to be equal to $\theta_t$ on the sets $V_1,\dots,V_t$, equal to $\theta^*_{t+1}$ on the set $V^*_{t+1}$ and equal to 0 on the set $O$. Let $g^{x,r_1,\dots,r_t}(v_1,\dots,v_{t+1})$ be defined as follows. Parse $v_{t+1}$ as $(v^*_{t+1},y')$, compute $h(x,v_1,\dots,v_t,v^*_{t+1},r_1,\dots,r_t) = (\widehat{x}^{(O)},\widehat{z}^{(O)})$, and output $y = y' \oplus \widehat{x}^{(O)}$.

Now, we show how to compile any quantum program $(\ket{\psi},C)$ into an $\LM$ quantum program with Pauli-encoded quantum output. We proceed by induction over the number of gates $\ell$ in $C$.

Base case. Suppose that $C$ contains 0 gates. That is, there is no state $\ket{\psi}$ and the functionality is just the identity applied to input $x$. In this case, $n = |x|$, $t=0$, $L_1$ is empty, $\theta^*_1 = \bot^n$, and the $\LM$ quantum program is defined by $(\ket{0^n},h)$, where $h(x) = (x,0^n)$.

Inductive step. Consider a quantum program $(\ket{\psi},C)$ with $\ell+1$ gates, and begin by writing $C$ as $(C_\ell,G)$, where $C_\ell$ contains the first $\ell$ gates, and $G \in \{\mathsf{CNOT},H,T\}$ is the final gate. By the inductive hypothesis, we know that $(\ket{\psi},C_\ell)$ can be written as an $\LM$ quantum program with Pauli-encoded quantum output: $\ket{\psi'},\{L_i\}_{i \in [t+1]},\{\theta_i\}_{i \in [t]},\{f_i^{(\cdot)}\}_{i \in [t]},\theta^*_{t+1},h$, where $t$ is the number of $T$ gates in $C_\ell$. Now, we consider three cases corresponding to the gate $G$, which by definition will be applied to one (or two) wire(s) in the "active" set $O$. In each case, we describe how to update the description of the $\LM$ quantum program for $(\ket{\psi},C_\ell)$ so that it now has the same functionality as the full quantum program $(\ket{\psi},C)$. The fact that these updates implement the desired functionality follow from <ref> and <ref> above.

* $\CNOT$ from wire $i$ to $j$: Append the description of this gate to the end of $L_{t+1}$ and append the operation  $(\widehat{x}^{(i)},\widehat{z}^{(i)}), (\widehat{x}^{(j)},\widehat{z}^{(j)}) \to (\widehat{x}^{(i)},\widehat{z}^{(i)} \oplus \widehat{z}^{(j)}), (\widehat{x}^{(i)} \oplus \widehat{x}^{(j)}, \widehat{z}^{(j)})$ to the end of $h$.

* $H$ on wire $i$: Refer to <ref>.

* Introduce two new wires $(n+1,n+2)$ and append $\ket{\phi_H}$ to $\ket{\psi'}$.

* Append the description of a $\CNOT$ gate from wire $i$ to $n+1$ to the end of $L_{t+1}$.

* Remove wire $i$ from and add wire $n+2$ to $O$.

* Add wires $i$ and $n+1$ to $V^*_{t+1}$.
* For $\tau \in [t]$, define $\theta_{\tau,n+1} = \theta_{\tau,n+2} = \bot$. Define $\theta^*_{t+1,i} = 1$, $\theta^*_{t+1,n+1} = 0$, and $\theta^*_{t+1,n+2} = \bot$.

* Update $h$ to $h'$ as follows. The function $h'$ will now take two additional input bits $v^{(i)}, v^{(n+1)}$ as part of $v^*_{t+1}$ and its output will now include $(\widehat{x}^{(n+2)},\widehat{z}^{(n+2)})$ rather than $(\widehat{x}^{(i)},\widehat{z}^{(i)})$, computed as follows. Let $\widehat{x}^{(O)},\widehat{z}^{(O)} = h(x,v_1,\dots,v_t,v^*_{t+1},r_1,\dots,r_t)$ be the output of the original $h$, which includes $(\widehat{x}^{(i)},\widehat{z}^{(i)})$. Then the output of $h'$ includes $\widehat{x}^{(n+2)} \coloneqq v^{(i)} \oplus \widehat{z}^{(i)}$ and $\widehat{z}^{(n+2)} \coloneqq v^{(n+1)} \oplus \widehat{x}^{(i)}$.

* $T$ on wire $i$: Refer to <ref>.

* Introduce two new wires $(n+1,n+2)$ and append $\ket{\phi_T}\ket{\psi_{PX}}$ to $\ket{\psi'}$.

* Append the description of a $\CNOT$ gate from wire $n+1$ to $i$ to the end of $L_{t+1}$.

* Remove wire $i$ from and add wire $n+1$ to $O$.

* Define $V_{t+1} \coloneqq V^*_{t+1} \cup \{i\}$ and define $W_{t+1} \coloneqq \{n+1,n+2\}$.

* For $\tau \in [t]$, define $\theta_{\tau,n+1} = \theta_{\tau,n+2} = \bot$. Define $\theta_{t+1}$ to be equal to $\theta_t$ on the sets $V_1,\dots,V_t$, equal to $\theta^*_{t+1}$ on the set $V^*_{t+1}$, equal to $0$ on index $i$, and equal to $\bot$ everywhere else.

* Define a function $f_{t+1}^{x,r_1,\dots,r_t}(v_1,\dots,v_{t+1},w_{t+1})$ as follows, where $v_{t+1} = (v^*_{t+1},v^{(i)})$. First, compute $(\widehat{x}^{(O)},\widehat{z}^{(O)}) = h(x,v_1,\dots,v_t,v^*_{t+1},r_1,\dots,r_t)$, which includes $(\widehat{x}^{(i)},\widehat{z}^{(i)})$. Then, set $c = v^{(i)} \oplus \widehat{x}^{(i)}$, and output $(v_{t+1},\Gamma_c(w_{t+1}))$. This defines measurement $M_{\theta_{t+1},f_{t+1}^{(\cdot)}}$.

* Initialize $V^*_{t+2} \coloneqq \{n+2\}$, $\theta^*_{t+2}$ to be equal to 1 at index $n+2$ and $\bot$ everywhere else, and $L_{t+2}$ to be empty.

* Update $h$ to $h'$ as follows. The function $h'$ will now take an additional input bit $v^{(i)}$ as part of $v_{t+1}$, an additional input bit $v^{(n+2)}$ as part of $v^*_{t+2}$, and an additional input bit $r_{t+1}$. Its output will now include $(\widehat{x}^{(n+1)},\widehat{z}^{(n+1)})$ rather than $(\widehat{x}^{(i)},\widehat{z}^{(i)})$, computed as follows. Let $\widehat{x}^{(O)},\widehat{z}^{(O)} = h(x,v_1,\dots,v_t,v^*_{t+1},r_1,\dots,r_t)$ be the output of the original $h$, which includes $(\widehat{x}^{(i)},\widehat{z}^{(i)})$. Then the output of $h'$ includes $\widehat{x}^{(n+1)} \coloneqq v^{(i)} \oplus \widehat{x}^{(i)}$ and $\widehat{z}^{(n+1)} \coloneqq (v^{(i)} \oplus \widehat{x}^{(i)}) \cdot (v^{(n+2)} \oplus r_{t+1})$.

This completes the description of the compiler. Observe that the $W_i$ wires consist of the two magic state wires used to implement the $i$'th $T$ gate (one initialized with $\ket{\phi_T}$ and the other initialized with $\ket{\phi_{PX}}$). The $\ket{\phi_T}$ wire is used as the control for a single CNOT gate just prior to the $i$'th measurement, and the $\ket{\phi_{PX}}$ wire is not touched until the $i$'th measurement. Thus, since $\Gamma_c$ is a standard basis projector, all the requirements of the standard-basis-collapsible $W$ wires property (<ref>) are fulfilled.

§ QUANTUM STATE OBFUSCATION: CONSTRUCTION

In this section, we define quantum state obfuscation, describe our construction, and show that it is correct. We will prove security in the following section.

For any $\epsilon = \epsilon(\secp)$, let $\cC_\epsilon$ be the set of families of $\epsilon$-pseudo-deterministic quantum programs (<ref>), where each family $\{\ket{\psi_\secp},C_\secp\}_{\secp \in \bbN} \in \cC_\epsilon$ is associated with an induced family of maps $\{Q_\secp : \{0,1\}^{m(\secp)} \to \{0,1\}^{m'(\secp)}\}_{\secp \in \bbN}$. A quantum state obfuscator is a pair of QPT algorithms $(\QObf,\QEval)$ with the following syntax.

* $\QObf\left(1^\secp,\ket{\psi},C\right) \to \ket*{\widetilde{\psi}}$: The obfuscator takes as input the security parameter $1^\secp$ and a quantum program $(\ket{\psi},C)$, and outputs an obfuscated state $\ket*{\widetilde{\psi}}$.

* $\QEval\left(x,\ket*{\widetilde{\psi}}\right) \to y$: The evaluation algorithm takes an input $x \in \{0,1\}^{m(\secp)}$ and an obfuscated state $\ket*{\widetilde{\psi}}$, and outputs $y \in \{0,1\}^{m'(\secp)}$.

Correctness is defined as follows for any quantum program $\{\ket{\psi_\secp},C_\secp\}_{\secp \in \bbN}$.

\[\forall x \in \{0,1\}^{m(\secp)}, \Pr\left[\QEval\left(x,\ket*{\widetilde{\psi}}\right) = Q_\secp(x) : \ket*{\widetilde{\psi}} \gets \QObf\left(1^\secp,\ket{\psi_\secp},C_\secp\right)\right] = 1-\negl(\secp).\]

We define two notions of security with respect to some pseudo-deterministic parameter $\epsilon = \epsilon(\secp)$.