Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2601.07111

Composable Verification in the Circuit-Model via Magic-Blindness

Sami Abdul Sater, Harold Ollivier

quant-phSubmitted Jan 12, 2026• Announced Jan 13, 2026• 0 citations• Revised Mar 24, 2026 (v2)
v1 · Jan 12, 2026v2 · Mar 24, 2026v3 · May 22, 2026
arXivHTMLPDF

Abstract

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.

Comments
45 pages, 14 figures

Related papers

Unifying quantum verification and error-detection: theory and tools for optimisations

Theodoros Kapourniotis, Elham Kashefi, Dominik Leichtle +2 more

Abstract With the advent of cloud-based quantum computing, it has become vital to provide strong guarantees that computations delegated by clients to quantum service providers have been executed faithfully. Secure—blind and verifiable—delegated quantum computing (SDQC) has emerged as one of the key approaches to address this challenge, yet current protocols lack at least one of the following three ingredients: composability, noise-robustness and modularity. To tackle this question, our paper lays out the fundamental structure of SDQC protocols, namely mixing two components: the computation which the client would like the server to perform and tests that are designed to detect a server’s malicious behaviour. Using this abstraction, our main technical result is a set of sufficient conditions on these components which imply the security and noise-robustness of generic SDQC protocols in the composable Abstract Cryptography framework. This is done by establishing a correspondence between these security properties and the error-detection capabilities of the test computations. Changing the types of tests and how they are mixed with the client’s computation automatically yields new SDQC protocols with different security and noise-robustness capabilities. This approach thereby provides the desired modularity as our sufficient conditions on test computations simplify the steps required to prove the security of the protocols and allows to focus on the design and optimisation of test rounds to specific situations. We showcase this by systematising the search for improved SDQC protocols for bounded-error quantum polynomial-time ( BQP ) computations. The resulting protocols do not require more hardware on the server’s side than what is necessary to blindly delegate the computation without verification, and they outperform all previously known results.

arXiv:2206.00631•Quantum Science and Technology•May 2, 2024•15 citations

Noise-Robustness for Delegated Quantum Computation in the Circuit Model

Anne Broadbent, 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.

quant-pharXiv:2511.22844•Dec 1, 2025•0 citations

Circuit-model blind quantum computation with key decoupling

Ting Xiang, Bingwen Feng, Xiaoqian Zhang

In the noisy intermediate-scale quantum (NISQ) era, quantum computing resources are increasingly provided through cloud platforms, enabling users to perform quantum computations without owning expensive hardware. However, delegating computations to remote servers raises a key challenge: ensuring the privacy of the client’s input, algorithm, and output. To address this issue, we propose a circuit-model blind quantum computation (CMBQC) protocol that conceals the target quantum computation while decoupling the encryption and decryption keys. This key-decoupled structure avoids gate-by-gate propagation of decryption information on the client side. We establish blindness of the target operation within its Pauli equivalence class and prove the verifiability of the protocol, where verification is achieved by estimating expectation values of randomly chosen Pauli observables, thereby substantially reducing the verification overhead. We further demonstrate a single-qubit implementation of the CMBQC protocol on an International Business Machines Corporation (IBM) superconducting quantum system. The simple structure and low verification cost of the CMBQC protocol make it a promising framework for secure delegated quantum computation, with potential applications in quantum cloud computing.

Quantum Research•Sep 21, 2026•0 citations

Verifiable blind probabilistic error cancellation

Bo Yang, Elham Kashefi, Harold Ollivier

Quantum error mitigation (QEM) is an essential tool for mitigating hardware noise without incurring space overhead. Yet, its reliability depends on modeling, calibration, and implementation, leaving end-to-end security on untrusted quantum hardware unresolved. We address this problem by introducing verifiable blind probabilistic error cancellation (VBPEC), the first secure verification protocol against a fully malicious adversary that integrates QEM. VBPEC brings probabilistic error cancellation (PEC), a widely studied QEM technique, within the scope of composable security by formalizing delegated mitigation as a cryptographic resource in the abstract cryptography framework. The protocol performs PEC with perfect blindness and an exponentially small security error. VBPEC retains the absence of quantum-space overhead from recent statistically-secure verified quantum computation protocols and from PEC. The only overhead takes the form of additional repetitions due to the QEM procedure. To achieve this, we extend trap-based verification from deterministic pass/fail checks to statistical tests that benefit from QEM and develop a new proof technique that integrates the corresponding additional deviation sources. Rather than merely tolerating honest noise below a fixed threshold, VBPEC actively cancels it, enabling correctly mitigated estimates to be accepted with high probability without compromising security. Our framework thus establishes an essential route towards secure, reliable, and practical delegated quantum computation on near-future quantum hardware: VBPEC fundamentally improves the practicality of verification.

quant-pharXiv:2607.25704•Jul 29, 2026•0 citations

Verifier-on-a-leash: New schemes for verifiable delegated quantum computation, with quasilinear resources

Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery +1 more

$ $ The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two non-communicating but entangled quantum provers, with statistical soundness. Our protocols have near-optimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as $O(g\log g)$ for delegating a circuit of size $g$. This is in contrast to previous protocols, whose overhead in terms of resources employed, while polynomial, is far beyond what is feasible in practice. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit or its input. The second protocol is not blind, but requires only a constant number of rounds of interaction. Our main technical innovation is an efficient rigidity theorem that allows a verifier to test that two entangled provers perform measurements specified by an arbitrary $m$-qubit tensor product of single-qubit Clifford observables on their respective halves of $m$ shared EPR pairs, with a robustness that is independent of $m$. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent (Theory of Computing, 2018). ------------------- A conference version of this paper appeared in the Proceedings of the 48th Ann. Internat. Conf. on Theory and Appl. of Cryptographic Techniques (EUROCRYPT 2019).

Theory of Computing•Jan 1, 2024•4 citations

Verification of Quantum Computations: Hardware-Efficient Security Proofs

Harold Ollivier

How can a user with limited quantum resources verify the output of an untrusted, fully quantum server? This manuscript provides a conceptual synthesis of some recent developments toward answering this question under statistical (information-theoretic) security. Rather than duplicating the dense technical proofs of the underlying publications, our focus here is on the physical motivations, the structural connections between different protocols, and the path toward hardware-efficient implementation. We begin by introducing a modular, composable framework that partitions verification into three distinct, independent primitives: remote state preparation, trap-based deviation detection, and error-correcting embedding. Using this framework, we show how the demanding hardware requirements of early protocols can be systematically relaxed. We review schemes that eliminate the spatial overhead, remove the need to prepare computational-basis dummy states, and replace single-photon sources with trusted local rotations or weak coherent pulses. Finally, we examine how these techniques scale, both to asymmetric multi-party settings and to the delegation of fully fault-tolerant computations in the presence of gate-level noise. This document is intended as a guide to the architectural principles of practical quantum verification.

quant-pharXiv:2607.03983•Jul 7, 2026•0 citations
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.
Abstract With the advent of cloud-based quantum computing, it has become vital to provide strong guarantees that computations delegated by clients to quantum service providers have been executed faithfully. Secure—blind and verifiable—delegated quantum computing (SDQC) has emerged as one of the key approaches to address this challenge, yet current protocols lack at least one of the following three ingredients: composability, noise-robustness and modularity. To tackle this question, our paper lays out the fundamental structure of SDQC protocols, namely mixing two components: the computation which the client would like the server to perform and tests that are designed to detect a server’s malicious behaviour. Using this abstraction, our main technical result is a set of sufficient conditions on these components which imply the security and noise-robustness of generic SDQC protocols in the composable Abstract Cryptography framework. This is done by establishing a correspondence between these security properties and the error-detection capabilities of the test computations. Changing the types of tests and how they are mixed with the client’s computation automatically yields new SDQC protocols with different security and noise-robustness capabilities. This approach thereby provides the desired modularity as our sufficient conditions on test computations simplify the steps required to prove the security of the protocols and allows to focus on the design and optimisation of test rounds to specific situations. We showcase this by systematising the search for improved SDQC protocols for bounded-error quantum polynomial-time ( BQP ) computations. The resulting protocols do not require more hardware on the server’s side than what is necessary to blindly delegate the computation without verification, and they outperform all previously known results.
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 the noisy intermediate-scale quantum (NISQ) era, quantum computing resources are increasingly provided through cloud platforms, enabling users to perform quantum computations without owning expensive hardware. However, delegating computations to remote servers raises a key challenge: ensuring the privacy of the client’s input, algorithm, and output. To address this issue, we propose a circuit-model blind quantum computation (CMBQC) protocol that conceals the target quantum computation while decoupling the encryption and decryption keys. This key-decoupled structure avoids gate-by-gate propagation of decryption information on the client side. We establish blindness of the target operation within its Pauli equivalence class and prove the verifiability of the protocol, where verification is achieved by estimating expectation values of randomly chosen Pauli observables, thereby substantially reducing the verification overhead. We further demonstrate a single-qubit implementation of the CMBQC protocol on an International Business Machines Corporation (IBM) superconducting quantum system. The simple structure and low verification cost of the CMBQC protocol make it a promising framework for secure delegated quantum computation, with potential applications in quantum cloud computing.
Quantum error mitigation (QEM) is an essential tool for mitigating hardware noise without incurring space overhead. Yet, its reliability depends on modeling, calibration, and implementation, leaving end-to-end security on untrusted quantum hardware unresolved. We address this problem by introducing verifiable blind probabilistic error cancellation (VBPEC), the first secure verification protocol against a fully malicious adversary that integrates QEM. VBPEC brings probabilistic error cancellation (PEC), a widely studied QEM technique, within the scope of composable security by formalizing delegated mitigation as a cryptographic resource in the abstract cryptography framework. The protocol performs PEC with perfect blindness and an exponentially small security error. VBPEC retains the absence of quantum-space overhead from recent statistically-secure verified quantum computation protocols and from PEC. The only overhead takes the form of additional repetitions due to the QEM procedure. To achieve this, we extend trap-based verification from deterministic pass/fail checks to statistical tests that benefit from QEM and develop a new proof technique that integrates the corresponding additional deviation sources. Rather than merely tolerating honest noise below a fixed threshold, VBPEC actively cancels it, enabling correctly mitigated estimates to be accepted with high probability without compromising security. Our framework thus establishes an essential route towards secure, reliable, and practical delegated quantum computation on near-future quantum hardware: VBPEC fundamentally improves the practicality of verification.
$ $ The problem of reliably certifying the outcome of a computation performed by a quantum device is rapidly gaining relevance. We present two protocols for a classical verifier to verifiably delegate a quantum computation to two non-communicating but entangled quantum provers, with statistical soundness. Our protocols have near-optimal complexity in terms of the total resources employed by the verifier and the honest provers, with the total number of operations of each party, including the number of entangled pairs of qubits required of the honest provers, scaling as O(glog⁡g)O(g\log g)O(glogg) for delegating a circuit of size ggg. This is in contrast to previous protocols, whose overhead in terms of resources employed, while polynomial, is far beyond what is feasible in practice. Our first protocol requires a number of rounds that is linear in the depth of the circuit being delegated, and is blind, meaning neither prover can learn the circuit or its input. The second protocol is not blind, but requires only a constant number of rounds of interaction. Our main technical innovation is an efficient rigidity theorem that allows a verifier to test that two entangled provers perform measurements specified by an arbitrary mmm-qubit tensor product of single-qubit Clifford observables on their respective halves of mmm shared EPR pairs, with a robustness that is independent of mmm. Our two-prover classical-verifier delegation protocols are obtained by combining this rigidity theorem with a single-prover quantum-verifier protocol for the verifiable delegation of a quantum computation, introduced by Broadbent (Theory of Computing, 2018). ------------------- A conference version of this paper appeared in the Proceedings of the 48th Ann. Internat. Conf. on Theory and Appl. of Cryptographic Techniques (EUROCRYPT 2019).
How can a user with limited quantum resources verify the output of an untrusted, fully quantum server? This manuscript provides a conceptual synthesis of some recent developments toward answering this question under statistical (information-theoretic) security. Rather than duplicating the dense technical proofs of the underlying publications, our focus here is on the physical motivations, the structural connections between different protocols, and the path toward hardware-efficient implementation. We begin by introducing a modular, composable framework that partitions verification into three distinct, independent primitives: remote state preparation, trap-based deviation detection, and error-correcting embedding. Using this framework, we show how the demanding hardware requirements of early protocols can be systematically relaxed. We review schemes that eliminate the spatial overhead, remove the need to prepare computational-basis dummy states, and replace single-photon sources with trusted local rotations or weak coherent pulses. Finally, we examine how these techniques scale, both to asymmetric multi-party settings and to the delegation of fully fault-tolerant computations in the presence of gate-level noise. This document is intended as a guide to the architectural principles of practical quantum verification.