Harold Ollivier

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.

With the advent of quantum cloud computing, the security of delegated quantum computation has become of utmost importance. While multiple statistically secure blind verification schemes in the prepare-and-send model have been proposed, none of them achieves full quantum fault-tolerance, a prerequisite for useful verification on scalable quantum computers. In this paper, we present the first fault-tolerant blind verification scheme for universal quantum computations able to handle secret-dependent noise on the verifier's quantum device. Composable security of the proposed protocol is proven in the Abstract Cryptography framework. Our main tools are two novel distillation protocols that turn secret-dependent noise into secret-independent noise. The first one is run by the verifier and acts on its noisy gates, while the second and more complex one is run entirely on the prover's device and acts on states provided by the verifier. Both are required to overcome the leakage induced by secret-dependent noise. We use these protocols to prepare states in the X-Y-plane whose noise is overwhelmingly secret-independent, which then allows us to verify with exponential confidence arbitrary fault-tolerant BQP computations.

Quantum state purification is the functionality that, given multiple copies of an unknown state, outputs a state with increased purity. This is an essential building block for the near- and middle-term quantum ecosystems before the availability of full fault tolerance, where one may want to obtain purified quantum states instead of expectation values. We propose an effective state purification gadget with a moderate quantum overhead by projecting multiple noisy quantum inputs to their symmetry subspace defined by a set of projectors forming a subgroup of the symmetry group. This provides a state purification performance scaling inverse-linearly to the number of state copies given a fixed stochastic error rate, which drastically improves the implementation overhead in previous works. Our method may find its application in designing robust verification protocols for quantum outputs before the availability of fully fault-tolerant computing.

Cryptographic verification is essential for establishing trust in quantum-computing-as-a-service. However, a fundamental gap exists in the current verification landscape: existing efficient protocols are largely restricted to decision problems where correctness is boosted by classical majority voting. This excludes observable estimation, the statistical task underpinning nearly all near-term quantum advantage applications. For such tasks, current verification techniques face a prohibitive trade-off: either weak security guarantees or massive space overhead that exceeds the capacity of near-term hardware. To resolve this, we introduce the Secure Delegated Observable Estimation (SDOE) ideal resource, the first formal cryptographic framework for trustworthy expectation-value estimation within Abstract Cryptography. We then present the Verifiable Blind Observable Estimation (VBOE) protocol, which efficiently constructs this resource. VBOE circumvents the limitations inherent in prior methodologies by enabling the sequential collection of samples with negligible security error, requiring zero extra qubit overhead. By directly averaging computation rounds in classical post-processing, our protocol provides the only known path to rigorous, composable verification for the most common class of near-term quantum-classical hybrid algorithms. This work bridges foundational cryptographic theory with practical quantum tasks, enabling the certification of quantum utility on current and near-future devices.

Interactive verification protocols for quantum computations allow to build trust between a client and a service provider, ensuring the former that the instructed computation was carried out faithfully. They come in two variants, one without quantum communication that requires large overhead on the server side to coherently implement quantum-resistant cryptographic primitives, and one with quantum communication but with repetition as the only overhead on the service provider's side. Given the limited number of available qubits on current machines, only quantum communication-based protocols have yielded proof of concepts. In this work, we show that the repetition overhead of protocols with quantum communication can be further mitigated if one examines the task of operating a quantum machine from the service provider's point of view. Indeed, we show that the test rounds data, whose collection is necessary to provide security, can indeed be recycled to perform continuous monitoring of noise model parameters for the service provider. This exemplifies the versatility of these protocols, whose template can serve multiple purposes and increases the interest in considering their early integration into development roadmaps of quantum machines.

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.

Secure Delegated Quantum Computation (SDQC) protocols allow a client to delegate a quantum computation to a powerful remote server while ensuring the privacy and the integrity of its computation. Recent resource-efficient and noise- robust protocols led to experimental proofs of concept. Yet, their physical re- quirements are still too stringent to be added directly to the roadmap of quantum hardware vendors. To address part of this issue, this paper shows how to alleviate the necessity for the client to have a single-photon source. It proposes a protocol that ensures that, among a sufficiently large block of transmitted weak coherent pulses, at least one of them was emitted as a single photon. This can then be used through quantum privacy amplification techniques to prepare a single secure qubit to be used in an SDQC protocol. As such, the obtained guarantee can also be used for Quantum Key Distribution (QKD) where the privacy amplification step is classical. In doing so, it proposes a workaround for a weakness in the security proof of the decoy state method. The simplest instantiation of the protocol with only 2 intensities already shows improved scaling at low transmittance and adds verifiability to previous SDQC proposals.

With the advent of delegated quantum computing as a service, verifying quantum computations is becoming a question of great importance. Existing information theoretically Secure Delegated Quantum Computing (SDQC) protocols require the client to possess the ability to perform either trusted state preparations or measurements. Whether it is possible to verify universal quantum computations with information-theoretic security without trusted preparations or measurements was an open question so far. In this paper, we settle this question in the affirmative by presenting a modular, composable, and efficient way to turn known verification schemes into protocols that rely only on trusted gates.

With the recent availability of cloud quantum computing services, the question of verifying quantum computations delegated by a client to a quantum server is becoming of practical interest. While Verifiable Blind Quantum Computing (VBQC) has emerged as one of the key approaches to address this challenge, current protocols still need to be optimised before they are truly practical. To this end, we establish a fundamental correspondence between error-detection and verification and provide sufficient conditions to both achieve security in the Abstract Cryptography framework and optimise resource overheads of all known VBQC-based protocols. As a direct application, we demonstrate how to systematise the search for new efficient and robust verification protocols for BQP computations. While we have chosen Measurement-Based Quantum Computing (MBQC) as the working model for the presentation of our results, one could expand the domain of applicability of our framework via direct known translation between the circuit model and MBQC.

Secure multi-party computation (SMPC) protocols allow several parties that distrust each other to collectively compute a function on their inputs. In this paper, we introduce a protocol that lifts classical SMPC to quantum SMPC in a composably and statistically secure way, even for a single honest party. Unlike previous quantum SMPC protocols, our proposal only requires very limited quantum resources from all but one party; it suffices that the weak parties, i.e. the clients, are able to prepare single-qubit states in the X-Y plane. The novel quantum SMPC protocol is constructed in a naturally modular way, and relies on a new technique for quantum verification that is of independent interest. This verification technique requires the remote preparation of states only in a single plane of the Bloch sphere. In the course of proving the security of the new verification protocol, we also uncover a fundamental invariance that is inherent to measurement-based quantum computing.

With the development of delegated quantum computation, clients will want to ensure confidentiality of their data and algorithms, and the integrity of their computations. While protocols for blind and verifiable quantum computation exist, they suffer from high overheads and from over-sensitivity: When running on noisy devices, imperfections trigger the same detection mechanisms as malicious attacks, resulting in perpetually aborted computations. We introduce the first blind and verifiable protocol for delegating BQP computations to a powerful server with repetition as the only overhead. It is composably statistically secure with exponentially-low bounds and can tolerate a constant amount of global noise.