Sami Abdul Sater

As quantum computing machines move towards the utility regime, it is essential that users are able to verify their delegated quantum computations with security guarantees that are (i) robust to noise (ii) composable with other secure protocols and (iii) exponentially stronger as the number of resources dedicated to security increases. Previous works that achieve these guarantees are expressed in the Measurement-Based Quantum Computation (MBQC) model and benefit from a modular framework of verification protocols. This leaves architectures based on the circuit model---in particular those using the Magic State Injection (MSI)---with fewer options to verify their computations or with the need to compile their circuits in MBQC which leads to overheads. This paper introduces a family of noise robust, composable and efficient verification protocols for Clifford + MSI circuits that are secure against arbitrary malicious behavior. This family contains the verification protocol of Broadbent (2018, ToC), extends its security guarantees while also bridging the modularity gap between protocols for MBQC and those for the circuit model, and reducing quantum communication costs. As a result, it opens the prospect of rapid implementation tailored to near-term quantum devices. Our technique is based on a refined notion of blindness, called magic-blindness, which hides only the injected magic states---the sole source of non-Clifford computational power. This enables verification by randomly interleaving computation rounds with classically simulable, magic-free test rounds, leading to a trap-based framework for circuit verification. As a result, circuit-based quantum verification attains the same level of security and robustness previously known only in MBQC. It also reduces the quantum communication cost as transmitted qubits are required only at the locations of state injection.

Verification of quantum computations is crucial as experiments advance toward fault-tolerant quantum computing. Yet, no efficient protocol exists for certifying states generated in the Magic-State Injection model -- the foundation of several fault-tolerant quantum computing architectures. Here, we introduce an efficient protocol for certifying Clifford-enhanced Product States, a large class of quantum states obtained by applying an arbitrary Clifford circuit to a product of single-qubit, possibly magic, states. Our protocol only requires single-qubit Pauli measurements together with efficient classical post-processing, and has efficient sample complexity in both the independent (i.i.d.) and adversarial (non-i.i.d.) settings. This fills a key gap between Pauli-based certification schemes for stabilizer or (hyper)graph states and general protocols demanding non-Pauli measurements or classically intractable information about the target state. Our work provides the first efficient, Pauli-only certification protocol for the Magic-State Injection model, leading to practical verification of universal quantum computation under minimal experimental assumptions.

As quantum computing machines move towards the utility regime, it is essential that users are able to verify their delegated quantum computations with security guarantees that are (i) robust to noise, (ii) composable with other secure protocols, and (iii) exponentially stronger as the number of resources dedicated to security increases. Previous works that achieve these guarantees and provide modularity necessary to optimization of protocols to real-world hardware are most often expressed in the Measurement-Based Quantum Computation (MBQC) model. This leaves architectures based on the circuit model -- in particular those using the Magic State Injection (MSI) -- with fewer options to verify their computations or with the need to compile their circuits in MBQC leading to overheads. This paper introduces a family of noise robust, composable and efficient verification protocols for Clifford + MSI circuits that are secure against arbitrary malicious behavior. This family contains the verification protocol of Broadbent (ToC, 2018), extends its security guarantees while also bridging the modularity gap between MBQC and circuit-based protocols, and reducing quantum communication costs. As a result, it opens the prospect of rapid implementation for near-term quantum devices. Our technique is based on a refined notion of blindness, called magic-blindness, which hides only the injected magic states -- the sole source of non-Clifford computational power. This enables verification by randomly interleaving computation rounds with classically simulable, magic-free test rounds, leading to a trap-based framework for verification. As a result, circuit-based quantum verification attains the same level of security and robustness previously known only in MBQC. It also optimizes the quantum communication cost as transmitted qubits are required only at the locations of state injection.