Blind and Delegated Quantum Computation

Delegated quantum computation lets a computationally limited client ask a quantum server to perform a computation. Blind quantum computation adds a privacy guarantee: the server learns no more about the client’s input, algorithm, or output than a declared leakage function permits. Verifiable delegation adds an integrity guarantee: a cheating server can make the client accept an incorrect result only with bounded probability.

These are distinct properties. A protocol may verify a public computation without hiding it, or hide a computation without detecting a deliberately wrong result. Neither property forces the server to answer. A malicious server can usually delay, refuse service, or cause an abort.

The central example is prepare-and-send universal blind quantum computation (UBQC): a client hides measurement instructions with random qubit phases and random outcome flips. Verification adds a separate mechanism for detecting incorrect computation. We compare the assumptions needed when a client can prepare qubits, measure them, or communicate only classically.

Required background. Circuit computation describes the delegated task; graph states and teleportation explain the quantum resource and feed-forward. Trace distance measures distinguishability of real and ideal outputs.

Delegated channels and security guarantees

Let Alice be the client and Bob the quantum server. Alice supplies a computation $C$, an input $x$ or quantum state $\rho_{\mathrm{in}}$, and a security parameter $\lambda$. Bob supplies quantum processing, memory, measurement, and communication resources. At the end Alice obtains one of:

• a classical result $z$;
• a quantum output register, usually still encrypted under a Pauli key;
• a rejection symbol $\mathsf{rej}$.

The ideal computation is a channel $\mathcal U_C$. For a unitary task,

$$\mathcal U_C(\rho_{\mathrm{in}}) = U_C\rho_{\mathrm{in}}U_C^\dagger.$$

For sampling, measurement, or noisy-channel tasks, $\mathcal U_C$ should be read as the complete intended channel, including the declared measurement and classical output. Stating only a circuit is not enough. One must also specify which party supplies and receives each input and output register, which transcript fields are public, what Bob may retain, and whether Alice accepts approximate output.

Four guarantees that should not be merged

An honest execution should be correct. For a protocol without abort, a composable quantum-output criterion compares the implemented channel $\mathcal P_{\mathrm{hon}}$ with the intended channel even on an input entangled with a reference $R$:

$$\frac12\left\|[(\mathcal P_{\mathrm{hon}}-\mathcal U_C)\otimes\mathrm{id}_R](\rho_{\mathrm{in},R})\right\|_1\le\varepsilon_{\mathrm{cor}}$$

for every allowed input and reference. Including $R$ matters: correct reduced output states alone need not preserve their correlations. An aborting implementation must additionally specify the accepted branch and abort behavior in its ideal comparison.

If the protocol includes tests, honest noise may make Alice reject. Its completeness error is

$$\Pr[\mathsf{rej}\mid \text{honest Bob}] \leq \varepsilon_{\mathrm{cmp}}.$$

Blindness concerns Bob’s information, not Alice’s output accuracy. Write $V_B$ for Bob’s final quantum system together with the entire classical transcript visible to him. Let $L(C)$ be explicitly permitted leakage, such as a padded upper bound on circuit size. An information-theoretic blindness statement has the form

$$\frac12 \left\| \rho_{V_B}^{\mathrm{real}}(C,\rho_{\mathrm{in}}) - \mathsf{Sim}_B\bigl(L(C)\bigr) \right\|_1 \leq \varepsilon_{\mathrm{bl}}.$$

For each server strategy, the simulator has the allowed leakage and the server’s permitted initial side information, but not Alice’s private data. The displayed expression suppresses these strategy and side-information arguments; a full definition includes them and any external reference. If it can reproduce Bob’s real view, Bob cannot extract extra information from that view. Perfect blindness has $\varepsilon_{\mathrm{bl}}=0$; statistical blindness allows a small trace-distance error.

Computational protocols use a different claim. For every efficient quantum distinguisher $D$ and security parameter $\lambda$,

$$\left| \Pr[D(V_B^{(0)})=1] - \Pr[D(V_B^{(1)})=1] \right| \leq \operatorname{negl}(\lambda),$$

provided the two delegated tasks have the same permitted leakage and the declared post-quantum assumption holds. Calling this “unconditional” would be wrong even if the underlying quantum computation is ideal.

Verifiability concerns accepted wrong outputs. For a deterministic classical task with answer $z_C$ and accepted tolerance $\eta$, a direct condition is

$$\Pr\left[ \mathsf{acc} \mathbin{\wedge} d\bigl(z,z_C\bigr)>\eta \right] \leq \varepsilon_{\mathrm{ver}}.$$

For a sampling task, there is no single correct sample $z_C$: the target is an output distribution, or a task-specific relation. Checking that each answer lies in the distribution’s support cannot verify its probabilities. For quantum output, the ideal resource instead says that Alice receives either the correct output, up to the stated error, or $\mathsf{rej}$. This formulation avoids pretending that one can inspect an unknown quantum state and compare it with a classical answer sheet.

Composability and availability

A guarantee about one isolated run need not imply security when its output is reused or sessions interact. Dunjko, Fitzsimons, Portmann and Renner (2014) give a composable framework and explain why local blindness and ordinary local verifiability alone are not a general composition theorem. Their independent-verifiability condition restricts how acceptance can depend on private data.

Once complete components are proved close to compatible ideal resources, a composition theorem can add their distinguishing errors. For example, replacing a delegated-computation resource with error $\epsilon_D$ and an authenticated channel with error $\epsilon_A$ gives a bound $\epsilon_D+\epsilon_A$ in a framework supporting these substitutions. One cannot obtain $\epsilon_D$ merely by adding separately named correctness, blindness, completeness and trap-failure numbers.

None of these security properties guarantees availability. Bob can stop sending messages or force tests to fail. Redundant providers and service-level mechanisms may improve availability, but they do not turn cryptographic verification into a liveness theorem.

Trust and Capability Models

There is no single “minimal client” without a trust model. Preparing one of a few qubit states, measuring incoming photons, keeping two servers isolated, and running lattice-based cryptography are incomparable resources.

Client model	Trusted ability	Additional premise
Prepare and send	prepare hidden qubit states	quantum link and characterized source
Receive and measure	measure incoming systems	isolated laboratory; protocol-specific detector model
Remote state preparation	measure a flying partner	interface and heralding model
Small quantum verifier	encode or measure a small register	authentication or hidden-test construction
Classical, multiple servers	classical control	separated entangled servers cannot communicate as excluded by the proof
Classical, one server	classical cryptography	named post-quantum hardness assumptions

“Device-independent” must also be qualified. A receive-and-measure protocol may remove trust in a client measurement model for a particular privacy claim, while a multi-prover protocol may certify behavior from nonlocal correlations. Neither label means that timing, laboratory isolation, randomness, classical software, and all interfaces can be ignored. The declared boundary matters more than the adjective.

Universal Blind Quantum Computation

The UBQC protocol of Broadbent, Fitzsimons and Kashefi (2009) is an example of information-theoretic blindness with a weak quantum client. It uses measurement-based quantum computation, but only a small amount of that model is needed here.

Minimal measurement-based mechanics

Bob prepares a universal graph-state geometry, such as a brickwork state, by entangling qubits with controlled-$Z$ gates. A single-qubit measurement basis in the equatorial plane is

$$|\pm_\alpha\rangle = \frac{|0\rangle\pm e^{i\alpha}|1\rangle}{\sqrt2}.$$

Measuring successive graph vertices teleports logical information through the resource while applying gates determined by the measurement angles. Outcomes are random, so later angles must depend on parities of earlier outcomes. For the algorithmic angle $\phi_i$, write the corrected angle as

$$\phi_i' = (-1)^{s_i^X}\phi_i + s_i^Z\pi,$$

where $s_i^X$ and $s_i^Z$ are protocol-defined parities of earlier decoded outcomes. The graph’s flow or generalized flow determines those dependencies. The full measurement-pattern model, including branch maps, byproduct propagation, flow or gflow determinism, and compilation boundaries, belongs to Measurement-Based Quantum Computation; here the issue is how to conceal the pattern from Bob.

Protocol skeleton

For each resource qubit $i$, Alice samples

$$\theta_i \xleftarrow{\$} \mathcal A, \qquad r_i \xleftarrow{\$} \{0,1\},$$

where

$$\mathcal A = \left\{ 0,\frac\pi4,\frac\pi2,\ldots,\frac{7\pi}{4} \right\}.$$

The protocol proceeds as follows.

1. Alice sends Bob independently prepared states $|+_{\theta_i}\rangle$. A private classical input can be compiled into the initial measurement pattern. Quantum inputs require the protocol’s additional input-encryption procedure; equatorial resource preparation alone does not encode an arbitrary unknown input.
2. Bob entangles the qubits according to the public, usually padded, resource graph.
3. Before measurement $i$, Alice computes $\phi_i'$ from earlier decoded outcomes and sends

$$\delta_i = \phi_i' + \theta_i + r_i\pi \pmod{2\pi}.$$

4. Bob measures in the basis $\{|+_{\delta_i}\rangle, |-_{\delta_i}\rangle\}$ and returns the raw bit $b_i$.
5. Alice removes the outcome pad,

$$s_i = b_i\oplus r_i,$$

and uses $s_i$ to compute future corrections. 6. Alice decodes the classical output or removes the final Pauli key from a quantum output.

Why both masks matter

Bob receives an ensemble whose average state is maximally mixed:

$$\begin{aligned} \frac18 \sum_{\theta\in\mathcal A} |+_\theta\rangle\langle+_\theta| &= \frac12 \begin{pmatrix} 1 & \frac18\sum_\theta e^{-i\theta}\\ \frac18\sum_\theta e^{i\theta} & 1 \end{pmatrix}\\ &= \frac{I}{2}. \end{aligned}$$

The roots of unity sum to zero. Moreover, measuring $|+_{\theta_i}\rangle$ at physical angle $\delta_i$ is equivalent to measuring an unrotated state at angle

$$\delta_i-\theta_i = \phi_i'+r_i\pi.$$

Adding $\pi$ swaps the labels of the two basis vectors, so $r_i$ encrypts the outcome without changing the logical operation after Alice decodes it.

The marginal average is not enough because Bob later receives $\delta_i$, which is correlated with the prepared qubit. Consider one nonadaptive instruction with fixed target angle $\phi\in\mathcal A$. For any announced $\delta$, the two equally likely possibilities are

$$\theta=\delta-\phi\quad(r=0),\qquad \theta=\delta-\phi-\pi\quad(r=1).$$

The corresponding states are orthogonal. Thus

$$\rho_{Q\mid\delta,\phi} =\frac12\bigl(|+_{\delta-\phi}\rangle\langle+_{\delta-\phi}| +|-_{\delta-\phi}\rangle\langle-_{\delta-\phi}|\bigr)=\frac I2, \qquad \Pr(\delta\mid\phi)=\frac18.$$

The joint state of the instruction and qubit is independent of $\phi$. If Alice omitted $r$, the qubit conditioned on $\delta$ would instead be the pure state $|+_{\delta-\phi}\rangle$. Targets $\phi=0$ and $\phi=\pi$ would then be perfectly distinguishable, despite identical qubit marginals and uniformly random instructions. Exercise 8 constructs Bob’s measurement.

Condition on the same public instruction $\delta=0$. For $\phi=0$ the unknown outcome pad selects the two $X$ eigenstates; for $\phi=\pi/2$ it selects the two $Y$ eigenstates. Each equal mixture is $I/2$, the center of the Bloch disk. The full adaptive malicious-server proof also covers entangling operations, earlier messages and retained ancillas; this one-round calculation explains its masking mechanism.

A masked-angle example

Suppose

$$\phi_i=\frac\pi4, \qquad s_i^X=s_i^Z=1.$$

Then

$$\phi_i' = -\frac\pi4+\pi = \frac{3\pi}{4}.$$

If Alice sampled $\theta_i=\pi/2$ and $r_i=1$, she sends

$$\delta_i = \frac{3\pi}{4} + \frac\pi2 + \pi = \frac\pi4 \pmod{2\pi}.$$

Bob sees the ordinary-looking instruction $\pi/4$. If he reports $b_i=0$, Alice records $s_i=1$. The arithmetic does not reveal $\phi_i$ because Bob does not know the phase and outcome masks or the corrected feed-forward parities.

What UBQC still leaks

The standard construction does not make the interaction invisible. Unless it is padded and scheduled independently of private data, Bob may learn:

• the resource-graph geometry and an upper bound on width and depth;
• the number and timing of measurements;
• which messages are quantum and which are classical;
• loss, retry, and abort patterns;
• the output type or number of output qubits;
• network metadata and client identity.

A universal brickwork graph hides which gates are active within the graph, but its dimensions can reveal a circuit-size bound. Padding hides size only within an anonymity set and adds qubits, time, and noise. The leakage function $L(C)$ must list what remains; “the server learns nothing” is incomplete.

From Blindness to Verifiability

Blindness can make tests indistinguishable from computation. This lets Alice hide checks among useful operations so that Bob cannot target only the data.

Hidden traps and dummies

In the trap-based construction of Fitzsimons and Kashefi (2017), Alice embeds vertices with known deterministic outcomes. Dummy qubits isolate selected trap qubits from the computation graph. Random preparation and hidden placement prevent Bob from knowing which vertices are traps.

An honest execution produces the expected trap outcomes, apart from the declared physical-noise model. A malicious deviation large enough to corrupt the computation has a protocol-dependent probability of disturbing a hidden trap. Repetition, graph coloring, or encoded constructions can reduce the soundness error while retaining polynomial overhead.

For intuition only, if each independent repetition detects a fixed attack with probability at least $p_{\mathrm{det}}$, then $R$ repetitions miss it with probability at most

$$\varepsilon_{\mathrm{ver}} \leq (1-p_{\mathrm{det}})^R.$$

Real security proofs cannot assume that a quantum adversary attacks rounds independently. They reduce arbitrary coherent deviations to a form for which the hidden test structure gives a bound. The toy expression is useful for planning, not for replacing that reduction.

Quantum authentication

Another family authenticates the quantum data. Alice encodes the input using a secret key, for example through a random Clifford or signed polynomial code. Bob computes on authenticated data using prescribed gadgets. At the end Alice checks the authentication syndrome and accepts only if it is valid.

Authentication hides the data when combined with a quantum one-time pad and detects tampering, but its client operations, ancillary states, interaction, and fault-tolerance requirements differ from trap-based UBQC. Aharonov et al. (2017) develop authentication-based interactive proofs. Stabilizer codes provide useful encoding tools; cryptographic authentication additionally uses a secret key and a bound against adversarial tampering.

Computation rounds and test rounds

Some protocols randomly interleave computation rounds with efficiently checkable test rounds. If the protocol’s hiding mechanism makes the two types indistinguishable to Bob, failures in the tests constrain his ability to corrupt the computation unnoticed. The inference must include the test-sampling rule, tolerated honest noise, confidence procedure, and a proof relating test statistics to accepted computation, including coherent attacks.

Passing a few stabilizer checks is not automatically universal verification. The inference depends on the protocol theorem and its noise assumptions.

Classical Clients and Multiple Servers

Removing the client’s last trusted quantum operation is conceptually valuable, but it moves the burden elsewhere.

Two or more noncommunicating servers

A classical verifier can interact with entangled quantum provers that are prevented from communicating during the protocol. Nonlocal games and rigidity theorems constrain the provers’ effective measurements and shared state. This supports classical control and verification of general quantum computations, and variants can provide blindness.

The isolation assumption is cryptographic, not cosmetic. If the servers share the verifier’s questions during the live protocol, the soundness argument may collapse. Space-like separation is one route, but practical deployments must also control hidden radio, optical, timing, and supply-chain channels. A two-server protocol does not become a one-server protocol merely because both machines are operated by the same provider.

Reichardt, Unger and Vazirani (2013) use rigidity to obtain classical verification with entangled, separated provers. Privacy is an additional protocol property, not a consequence of rigidity alone.

One server under computational assumptions

Mahadev’s 2018 protocol showed that a probabilistic polynomial-time classical verifier can verify general quantum computation with one quantum prover under post-quantum cryptographic assumptions related to learning with errors (LWE). Trapdoor claw-free function families let the verifier enforce measurements in incompatible bases without possessing a qubit.

This changes the security category:

• soundness is computational rather than information-theoretic;
• the prover is assumed unable to break the selected post-quantum primitive;
• key generation, parameter selection, classical cryptography, and protocol compilation enter the trusted base;
• asymptotic polynomial overhead may still be impractical at useful sizes.

Classical verification does not automatically hide the circuit or input. Blind delegation requires a protocol and proof that explicitly provide privacy, or an additional encryption layer. “Mahadev-style” is not a complete security specification.

Measurement-only clients

In a measurement-only protocol, Bob sends quantum systems and Alice performs single-qubit measurements. Morimae and Fujii (2013) use the no-signaling principle to protect Alice’s choices in models where her laboratory does not leak the basis or outcome. This may be easier than preparing calibrated states on some optical platforms.

The direction of the quantum channel reverses the implementation risks. Alice must address detector behavior, wavelength and mode dependence, loss, malicious bright-light inputs, and basis-dependent side channels. Protocols also differ in whether Alice’s measurement device is trusted, characterized, or covered by a device-independent claim. Those variants should not be merged.

Quantum Homomorphic Encryption

Blind interactive computation and quantum homomorphic encryption (QHE) solve related but different tasks. In QHE, a client encrypts quantum data, a server evaluates a circuit on the ciphertext, and the client decrypts the result. A compact scheme asks that decryption cost depend on the security parameter and output size rather than on the full evaluated circuit.

The quantum one-time pad encrypts an $n$-qubit state as

$$\mathcal E_{a,b}(\rho) = X^a Z^b\rho Z^b X^a, \qquad a,b\in\{0,1\}^n.$$

Averaging over secret keys gives

$$\frac{1}{4^n} \sum_{a,b} \mathcal E_{a,b}(\rho) = \frac{I}{2^n}.$$

Clifford gates transform Pauli keys into new Pauli keys, so Alice can update the encryption classically. Non-Clifford gates are harder: they require interaction, auxiliary states, gate gadgets, or classical homomorphic encryption of key-dependent corrections. This is one reason $T$-gate count or $T$-depth appears in resource bounds.

Yu, Pérez-Delgado and Fitzsimons (2014) establish a no-go boundary. Perfectly information-theoretic, deterministic fully homomorphic quantum encryption for arbitrary circuits incurs exponential overhead under the standard compactness setting. Schemes such as Broadbent and Jeffery (2015), and restricted circuit families, avoid that conclusion by changing the security or functionality assumptions. The no-go result does not forbid interactive blind computation, approximate tradeoffs, or QHE for limited gate sets.

Adaptive communication and physical noise

Measurement dependencies determine how much computation can be batched. In a deliberately serial latency model,

$$T_{\mathrm{wall}}=T_{\mathrm{prepare}}+N_{\mathrm{round}}T_{\mathrm{network}} +T_{\mathrm{server}}+T_{\mathrm{verify}}+T_{\mathrm{decode}}.$$

Here $T_{\mathrm{network}}$ is a round-trip delay and the local times exclude that delay. Pipelining can overlap these terms, so the sum is not a general lower bound. An adaptive layer cannot start before the outcomes needed to determine its angles arrive. Padding, hidden traps and error correction increase both graph size and communication demands. The relevant rate is accepted computations per wall-clock time, with failed attempts included.

Honest noise and adversarial deviations

Cryptographic and physical errors play different roles. A trap should detect a malicious deviation, but honest noise can also trigger it. Raising the test tolerance improves completeness and may weaken soundness unless the proof accounts for the noise. Postselecting every inconvenient event can open a security loophole and destroy scalability.

Fault-tolerant blind computation combines encrypted or hidden logical operations with quantum error correction. Topological measurement-based constructions can hide a computation within a three-dimensional cluster-state architecture. Authentication-code protocols can incorporate fault-tolerant gadgets. In either case, one must jointly track:

$$\varepsilon_{\mathrm{logical}}, \quad \varepsilon_{\mathrm{cmp}}, \quad \varepsilon_{\mathrm{ver}}, \quad \varepsilon_{\mathrm{bl}}.$$

These terms are not interchangeable. A low logical error rate does not prove blindness, and a strong trap bound does not correct decoherence. Threshold Theorem explains when logical error can be suppressed; Resource Estimation connects physical qubits, factories, cycles and decoding to runtime.

Implementation Security

A proof applies to an interface model. Hardware and software must implement that interface closely enough that excluded degrees of freedom do not carry the secret.

State-preparation leakage

The states labeled $|+_{\theta}\rangle$ must differ only in the intended qubit degree of freedom. Angle-dependent spectra, emission time, pulse energy, spatial mode, multiphoton probability, or device memory can reveal $\theta$. The relevant object is Bob’s full emitted state $\rho_\theta^{QE}$, including side-channel system $E$, not an ideal qubit alone.

Malicious inputs to the client

Receive-and-measure and remote-state-preparation clients should constrain wavelength, intensity, timing, and spatial mode. Otherwise Bob may probe the measurement setting with reflected light, exploit detector nonlinearities, or inject systems outside the proof’s dimension. Optical isolators, filters, power monitoring, randomized calibration, and explicit abort rules belong to the security design.

Loss and selective reporting

If a party may declare “no detection” after learning a hidden variable, postselected data can be biased. The protocol must specify which losses are trusted, when a herald is committed, whether retries reuse secrets, and how acceptance depends on missing events. Loss tolerance is a theorem property, not an automatic benefit of using photons.

Randomness and key lifecycle

Phase masks, outcome pads, trap locations, challenge bits, and cryptographic keys require suitable private randomness. Reusing $(\theta_i,r_i)$ across sessions creates transcript correlations. Keys and decoded feed-forward data should be domain-separated by session, authenticated in transit, and erased according to the threat model. Quantum Randomness explains entropy certification and extraction.

Metadata, compiler, and abort leakage

A private source program can leak before the quantum protocol begins. Compiler branching, graph dimensions, cache and queue behavior, message timing, retry counts, and distinct error messages may depend on private data. A secure stack uses data-independent padding where required, canonical compilation, fixed transcript formats, authenticated session identifiers, and coarse abort categories. Diagnostic logs must not reveal secret masks or private feed-forward data.

Collusion and endpoint compromise

Multi-client and multi-server claims must list allowed coalitions. A protocol secure against one malicious server may fail if that server colludes with a client, source, orchestrator, or second server. Blindness also does not protect against malware that reads Alice’s input before encryption or her output after decryption.

Choosing the client’s assumptions

A client that can prepare a small set of calibrated states can use prepare-and-send UBQC. A measurement client reverses the quantum link and must account for malicious incoming light and the protocol’s detector assumptions. A fully classical client in the constructions discussed here uses either separated provers or computational assumptions. These choices exchange physical and cryptographic requirements; they do not form a simple hierarchy.

Blindness, accepted-output accuracy and honest acceptance must all match the implemented interface. A universal gate set or a small trap demonstration alone does not establish a large verified computation. The distributed-computing page treats remote gates and network scheduling; the privacy guarantees here additionally depend on what each server is allowed to learn.

Exercises

1: Separate the guarantees

A protocol encrypts Alice’s input perfectly, but Bob may replace the output with any string and Alice always accepts. Classify its correctness, blindness, verifiability, and availability against malicious Bob.

Solution

The encryption may provide perfect blindness for the input, provided the full view and leakage are covered by a proof. The protocol is not verifiable because Bob can make Alice accept a wrong result with probability one. Its honest correctness may still be perfect if an honest Bob computes correctly. It has no malicious-server availability guarantee because Bob can return nonsense or stop. The four statements concern different experiments.

2: Average the phase ensemble

Show directly that uniformly averaging $|+_\theta\rangle\langle+_\theta|$ over $\theta=k\pi/4$ for $k=0,\ldots,7$ gives $I/2$.

Solution

Write

$$|+_\theta\rangle\langle+_\theta| = \frac12 \begin{pmatrix} 1&e^{-i\theta}\\ e^{i\theta}&1 \end{pmatrix}.$$

The diagonal entries average to $1/2$. The off-diagonal sum is a geometric series over all eighth roots of unity:

$$\sum_{k=0}^{7}e^{ik\pi/4} = \frac{1-e^{i2\pi}}{1-e^{i\pi/4}} =0.$$

The conjugate sum also vanishes, leaving $I/2$.

3: Decode a masked instruction

Let $\phi_i=3\pi/4$, $s_i^X=1$, $s_i^Z=0$, $\theta_i=7\pi/4$, and $r_i=1$. Compute $\phi_i'$ and the angle $\delta_i$ sent to Bob. If Bob returns $b_i=1$, what outcome does Alice record?

Solution

The corrected angle is

$$\phi_i' = -\frac{3\pi}{4}.$$

Therefore

$$\delta_i = -\frac{3\pi}{4} + \frac{7\pi}{4} + \pi = 2\pi =0 \pmod{2\pi}.$$

Alice decodes $s_i=b_i\oplus r_i=1\oplus1=0$.

4: Leakage and padding

Two private circuits compile to brickwork graphs of dimensions $12\times20$ and $15\times17$. Alice pads both to $16\times24$. What circuit information is hidden, and what still leaks if message timing follows graph layers?

Solution

Bob can no longer distinguish the two circuits from the graph dimensions; he learns only that the compiled computation fits inside $16\times24$, assuming the dummy construction is itself blind. If timing reveals which layers contain real adaptive work, the active depth or dependency pattern may still leak. Alice needs a fixed schedule and fixed transcript shape if those properties are intended to be hidden. Network identity, total padded size, and the fact that a session occurred remain visible unless separately protected.

5: Toy trap amplification

In a simplified independent-round model, any fixed corrupting attack triggers a trap with probability at least $1/4$ per repetition. How many repetitions make the miss probability at most $10^{-6}$?

Solution

We need

$$\left(\frac34\right)^R \leq 10^{-6}.$$

Thus

$$R \geq \frac{\ln 10^{-6}}{\ln(3/4)} \approx 48.0.$$

Since $R$ is an integer and direct substitution is required, $R=49$ is the first value strictly below $10^{-6}$. A real protocol needs a proof against coherent attacks and cannot assume independent detection events without justification.

6: Pauli-key update through a Hadamard gate

An encrypted qubit is $X^aZ^b|\psi\rangle$. Show that after Bob applies $H$, Alice can regard the output as an encryption of $H|\psi\rangle$ with updated key $(a',b')=(b,a)$, up to an irrelevant global phase.

Solution

Using $HXH=Z$ and $HZH=X$,

$$HX^aZ^b = Z^aX^bH = (-1)^{ab}X^bZ^aH.$$

The factor $(-1)^{ab}$ is a global phase. Therefore the new $X$ key is $b$ and the new $Z$ key is $a$. Clifford gates permit this efficient classical key tracking; non-Clifford gates require additional machinery.

7: Choose a client model

Alice has no qubit source but has a well-characterized single-photon detector. She requires information-theoretic blindness from one server and can receive photons over a quantum link. Which family is the natural starting point, and which assumptions still need examination?

Solution

A receive-and-measure or remote-state-preparation protocol is the natural starting point. Alice must still state whether her measurement device is trusted or covered by the protocol proof, constrain incoming optical modes and intensity, handle loss without selective-reporting leakage, protect basis and outcome data inside her laboratory, authenticate classical communication, and verify that the server-memory and heralding model matches the theorem. Having a detector does not by itself establish device independence.

8: Remove the outcome pad

Consider the single-round construction with $r=0$, uniform $\theta\in\mathcal A$ and target $\phi\in\{0,\pi\}$. Bob receives $|+_\theta\rangle$ and $\delta=\phi+\theta$ modulo $2\pi$. Show that both marginals are independent of $\phi$, but Bob can recover $\phi$ exactly from their joint state.

Solution

The qubit average is $I/2$ and $\delta$ is uniform on eight angles for either target. After receiving $\delta$, Bob measures in the basis $\{|+_\delta\rangle,|-_\delta\rangle\}$. If $\phi=0$, the sent state is $|+_\delta\rangle$; if $\phi=\pi$, it is $|-_\delta\rangle$. The outcome identifies the target with probability one. Separate privacy of each marginal does not imply privacy of their correlations. Restoring a secret uniform $r$ mixes these two orthogonal states for either target and removes this attack.

References

• D. Aharonov, M. Ben-Or, E. Eban, and U. Mahadev, “Interactive proofs for quantum computations,” SIAM Journal on Computing 46, 1230–1272 (2017), arXiv:1704.04487.
• A. Broadbent, J. Fitzsimons, and E. Kashefi, “Universal blind quantum computation,” in 50th Annual IEEE Symposium on Foundations of Computer Science, 517–526 (2009), doi:10.1109/FOCS.2009.36.
• A. Broadbent and S. Jeffery, “Quantum homomorphic encryption for circuits of low $T$-gate complexity,” in Advances in Cryptology – CRYPTO 2015, 609–629 (2015), arXiv:1412.8766.
• V. Dunjko, J. F. Fitzsimons, C. Portmann, and R. Renner, “Composable security of delegated quantum computation,” in Advances in Cryptology – ASIACRYPT 2014, 406–425 (2014), doi:10.1007/978-3-662-45608-8_22.
• J. F. Fitzsimons and E. Kashefi, “Unconditionally verifiable blind quantum computation,” Physical Review A 96, 012303 (2017), doi:10.1103/PhysRevA.96.012303.
• U. Mahadev, “Classical verification of quantum computations,” in 59th Annual IEEE Symposium on Foundations of Computer Science, 259–267 (2018), doi:10.1109/FOCS.2018.00033.
• T. Morimae and K. Fujii, “Blind quantum computation protocol in which Alice only makes measurements,” Physical Review A 87, 050301(R) (2013), doi:10.1103/PhysRevA.87.050301.
• B. W. Reichardt, F. Unger, and U. Vazirani, “Classical command of quantum systems,” Nature 496, 456–460 (2013), doi:10.1038/nature12035.
• L. Yu, C. A. Pérez-Delgado, and J. F. Fitzsimons, “Limitations on information-theoretically secure quantum homomorphic encryption,” Physical Review A 90, 050303(R) (2014), doi:10.1103/PhysRevA.90.050303.