Joshua Nevin

Cloud-based quantum computing, coupled with the rapid progress in quantum algorithms, brings to the forefront the question of verifiability in delegated quantum computations. In the current landscape of noisy quantum devices, this question must be addressed alongside noise tolerance. In this work, we revisit the circuit-based framework for verifiable quantum computation introduced by Broadbent [Theory of Computing, 2018], and extend it to the setting of server-side noise. Our contribution is an improved upper bound on the noise-tolerance threshold, achieved through a protocol that interleaves computation and test rounds in an indistinguishable manner. This structure enables a concise security proof against arbitrary deviations by the server, while ensuring robustness to realistic noise.

In 2021, Broadbent and Kazmi developed a gate-teleportation-based protocol for computational indistinguishability obfuscation of quantum circuits. This protocol is efficient for Clifford+T circuits with logarithmically many T-gates, where the limiting factor in the efficiency of the protocol is the difficulty, on input a quantum circuit C, of the classical task of producing a description of the unitary obtained by conjugating a Pauli P (corresponding to a Bell-measurement outcome) by C, where this description only depends on the input-output functionality of the conjugate of P by C. The task above, in turn, is at least as hard as the problem of determining whether two n-qubit quantum circuits are perfectly equivalent up to global phase (Exact Non-Identity Check, ENIC), which is known to be NQP-complete (Tanaka, 2010). Motivated by this, we consider in this work what happens when we pass from low T-count to low T-depth. We show that, for Clifford+T-circuits of T-depth O(log(n)), deciding ENIC remains NP-hard. In particular, we show this by relating certain decision problems on Pauli coefficients of Clifford+T unitaries to well-known hardness results for codeword weights in binary linear codes. This effectively rules out the possibility, for Clifford+T-circuits of logarithmic T-depth, of either efficient ENIC or efficient gate-teleportation-based computational indistinguishability obfuscation, unless P = NP.