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:2603.09368

Verified delegated quantum computation requires techniques beyond cut-and-choose

Fabian Wiesner, Anna Pappa

quant-phcs.CRSubmitted Mar 10, 2026• Announced Mar 11, 2026• 1 citation
arXivHTMLPDF

Abstract

Delegated quantum computation enables a client with limited quantum capabilities to outsource computations to a more powerful quantum server while preserving correctness and privacy. Verification is crucial in this setting to ensure that the untrusted quantum server performs the computation honestly and returns correct results. A common verification method is the quantum cut-and-choose technique. Inspired by classical verification methods for two-party computation, the client uses the majority of the delegated rounds to test the server's honesty, while keeping the remaining ones for the actual computation. Combining this technique with other methods, such as quantum error correction, could help achieve negligible cheating probabilities for the server; however, such methods can impose significant overheads making implementations unfeasible for the near-term future. In this work, we investigate whether cut-and-choose can yield efficient and secure verifiable quantum computation without additional costly techniques. We find that verifiable delegated quantum computation protocols relying solely on cut-and-choose techniques cannot be secure and efficient at the same time.

Comments
19 pages, 2 figures, 2 protocols

Related papers

Verifiable Multiparty Delegated Quantum Computation

Qin Li, Can Wang, Jiang Zhu +2 more

Multiparty delegated quantum computation (MDQC) allows multiple clients with limited quantum capability to jointly complete a quantum computational task with the aid of an untrusted quantum server. But in existing MDQC protocols, the verifiability that clients should verify whether the server executed the protocol correctly and gave correct results was not handled. Therefore, in this paper, we improve a typical MDQC protocol to enable clients to verify the correctness of computation by inserting trap qubits and develop a novel method to enforce clients to send qubits honestly while avoiding the positions of trap qubits being leaked to the server. The security and verifiability of the improved MDQC protocol are also analyzed. In addition, a specific example of the proposed verifiable MDQC protocol is given and simulated on IBM’s quantum platform.

International Journal of Intelligent Systems•Jan 1, 2023•5 citations

A three-party verifiable blind quantum computing protocol with separated input and function ownership

Yinqi Feng, Ri‐Gui Zhou, Ran Guo +2 more

Abstract Blind quantum computing enables quantum-limited clients to securely access untrusted quantum servers. This paper proposes a three-party verifiable blind quantum computing protocol with separated input and function ownership, where Alice holds the private input, Bob holds the target function, and Charlie performs the delegated quantum computation, with the result released only to Alice. Alice and Bob first establish a shared key using BB84. Under the measurement-based quantum computing framework, a secure two-party computation protocol is then used to jointly generate adaptive blinded measurement instructions, eliminating the need for Bob to transmit quantum states to Charlie. A hidden dummy-trap mechanism is further incorporated to verify malicious server behavior. Under the honest-but-curious client model without client-server collusion, the protocol protects input and function privacy while ensuring computation blindness, shared-key security, and verifiability. Most quantum operations are performed by Charlie, while the clients require only limited quantum capabilities.

Physica Scripta•Aug 28, 2026•0 citations

Verifiable blind quantum computation for two types of clients via iterated gate teleportation

Yuxun Wang, Qunfeng Dai, Qin Li

Blind quantum computation (BQC) provides a secure framework for clients to delegate quantum computations to servers without revealing their private information. Among BQC protocols, those built on iterated gate teleportation (IGTBQC) have demonstrated promising potential in overcoming the constraints imposed by the no-programming theorem and significantly reducing communication overhead. However, existing IGTBQC protocols lack mechanisms for clients to verify the correctness of computation results and deal with only one type of clients capable of preparing qubits. To address these limitations, we first extend the current IGTBQC protocol to be a verifiable one and then propose another verifiable IGTBQC protocol tailored for a different type of clients with the capability of measuring single-qubit states. Furthermore, both protocols are shown to satisfy blindness and verification simultaneously in a relatively formal way. Our results not only broaden the applicability to a wider range of clients but also enhance the practicality of delegated quantum computation.

Physical Review A•Aug 5, 2025•2 citations

Time-Delayed Publicly Verifiable Quantum Computation with Classical Verifiers

Aydin Abadi

Publicly verifiable delegation is a well-known problem involving a user who wishes to outsource a resource-intensive computational task to a more powerful but potentially untrusted server such that any other party is able to efficiently check the veracity of the com- putation's result. This problem has been extensively studied in the classical domain where the user and server are both non-quantum machines. However, the problem becomes more challenging when the classical user wants to delegate a quantum circuit to a single prover with quantum-computing capabilities. Previous solutions have resorted to using impractical or non-standard cryptographic solutions (e.g. indistinguishability obfuscation) to achieve this re- quirement. In this work, we relax the requirement to have time- delayed publicly verifiable proofs, where the verification key is made known to the public only when the computation (and its proof) are guaranteed to have been completed. We propose a prac- tical non-interactive scheme leveraging commitment schemes and time-lock puzzles, which can be efficiently realized through well- established and standard post-quantum assumptions. The main idea of our technique lies in using time-lock puzzles to compile a 2-round privately verifiable scheme into a non-interactive publicly verifiable scheme with timestamped proofs, outsourcing not only the quantum computation but the puzzle solving as well. Security is proven in the quantum random oracle model with a common reference string (CRS).

•Oct 22, 2026•0 citations

The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation

Elham Kashefi, Luka Music, Petros Wallden

The application and analysis of the Cut-and-Choose technique in protocols secure against quantum adversaries is not a straightforward transposition of the classical case, among other reasons due to the difficulty to use rewinding in the quantum realm. We introduce a Quantum Computation Cut-and-Choose (QC-CC) technique which is a generalisation of the classical Cut-and-Choose in order to build quantum protocols secure against quantum covert adversaries. Such adversaries can deviate arbitrarily provided that their deviation is not detected. As an application of the QC-CC we give a protocol for securely performing two-party quantum computation with classical input/output. As basis we use secure delegated quantum computing (Broadbent et al 2009), and in particular the garbled quantum computation of (Kashefi et al 2016) that is secure against only a weak specious adversaries, defined in (Dupuis et al 2010). A unique property of these protocols is the separation between classical and quantum communications and the asymmetry between client and server, which enables us to sidestep the quantum rewinding issues. This opens the prospect of using the QC-CC to other quantum protocols with this separation. In our proof of security we adapt and use (at different parts) two quantum rewinding techniques, namely Watrous' oblivious q-rewinding (Watrous 2009) and Unruh's special q-rewinding (Unruh 2012). Our protocol achieves the same functionality as in previous works (e.g. Dupuis et al 2012), however using the QC-CC technique on the protocol from (Kashefi et al 2016) leads to the following key improvements: (i) only one-way offline quantum communication is necessary , (ii) only one party (server) needs to have involved quantum technological abilities, (iii) only minimal extra cryptographic primitives are required, namely one oblivious transfer for each input bit and quantum-safe commitments.

arXiv:1703.03754•Mar 10, 2017•20 citations

Time-Delayed Publicly Verifiable Quantum Computation with Classical Verifiers

Ameer Mohammed, Aydin Abadi, Jaffer Mahdi

Publicly verifiable delegation is a well-known problem involving a user who wishes to outsource a resource-intensive computational task to a more powerful but potentially untrusted server such that any other party is able to efficiently check the veracity of the computation's result. This problem has been extensively studied in the classical domain where the user and server are both non-quantum machines. However, the problem becomes more challenging when the classical user wants to delegate a quantum circuit to a single prover with quantum-computing capabilities. Previous solutions have resorted to using impractical or non-standard cryptographic solutions (e.g. indistinguishability obfuscation) to achieve this requirement. In this work, we relax the requirement to have time-delayed publicly verifiable proofs, where the verification key is made known to the public only when the computation (and its proof) are guaranteed to have been completed. We propose a practical non-interactive scheme leveraging commitment schemes and time-lock puzzles, which can be efficiently realized through well-established and standard post-quantum assumptions. The main idea of our technique lies in using time-lock puzzles to compile a 2-round privately verifiable scheme into a non-interactive publicly verifiable scheme with timestamped proofs, outsourcing not only the quantum computation but the puzzle solving as well. Security is proven in the quantum random oracle model with a common reference string (CRS).

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2026•0 citations
Delegated quantum computation enables a client with limited quantum capabilities to outsource computations to a more powerful quantum server while preserving correctness and privacy. Verification is crucial in this setting to ensure that the untrusted quantum server performs the computation honestly and returns correct results. A common verification method is the quantum cut-and-choose technique. Inspired by classical verification methods for two-party computation, the client uses the majority of the delegated rounds to test the server's honesty, while keeping the remaining ones for the actual computation. Combining this technique with other methods, such as quantum error correction, could help achieve negligible cheating probabilities for the server; however, such methods can impose significant overheads making implementations unfeasible for the near-term future. In this work, we investigate whether cut-and-choose can yield efficient and secure verifiable quantum computation without additional costly techniques. We find that verifiable delegated quantum computation protocols relying solely on cut-and-choose techniques cannot be secure and efficient at the same time.
Multiparty delegated quantum computation (MDQC) allows multiple clients with limited quantum capability to jointly complete a quantum computational task with the aid of an untrusted quantum server. But in existing MDQC protocols, the verifiability that clients should verify whether the server executed the protocol correctly and gave correct results was not handled. Therefore, in this paper, we improve a typical MDQC protocol to enable clients to verify the correctness of computation by inserting trap qubits and develop a novel method to enforce clients to send qubits honestly while avoiding the positions of trap qubits being leaked to the server. The security and verifiability of the improved MDQC protocol are also analyzed. In addition, a specific example of the proposed verifiable MDQC protocol is given and simulated on IBM’s quantum platform.
Abstract Blind quantum computing enables quantum-limited clients to securely access untrusted quantum servers. This paper proposes a three-party verifiable blind quantum computing protocol with separated input and function ownership, where Alice holds the private input, Bob holds the target function, and Charlie performs the delegated quantum computation, with the result released only to Alice. Alice and Bob first establish a shared key using BB84. Under the measurement-based quantum computing framework, a secure two-party computation protocol is then used to jointly generate adaptive blinded measurement instructions, eliminating the need for Bob to transmit quantum states to Charlie. A hidden dummy-trap mechanism is further incorporated to verify malicious server behavior. Under the honest-but-curious client model without client-server collusion, the protocol protects input and function privacy while ensuring computation blindness, shared-key security, and verifiability. Most quantum operations are performed by Charlie, while the clients require only limited quantum capabilities.
Blind quantum computation (BQC) provides a secure framework for clients to delegate quantum computations to servers without revealing their private information. Among BQC protocols, those built on iterated gate teleportation (IGTBQC) have demonstrated promising potential in overcoming the constraints imposed by the no-programming theorem and significantly reducing communication overhead. However, existing IGTBQC protocols lack mechanisms for clients to verify the correctness of computation results and deal with only one type of clients capable of preparing qubits. To address these limitations, we first extend the current IGTBQC protocol to be a verifiable one and then propose another verifiable IGTBQC protocol tailored for a different type of clients with the capability of measuring single-qubit states. Furthermore, both protocols are shown to satisfy blindness and verification simultaneously in a relatively formal way. Our results not only broaden the applicability to a wider range of clients but also enhance the practicality of delegated quantum computation.
Publicly verifiable delegation is a well-known problem involving a user who wishes to outsource a resource-intensive computational task to a more powerful but potentially untrusted server such that any other party is able to efficiently check the veracity of the com- putation's result. This problem has been extensively studied in the classical domain where the user and server are both non-quantum machines. However, the problem becomes more challenging when the classical user wants to delegate a quantum circuit to a single prover with quantum-computing capabilities. Previous solutions have resorted to using impractical or non-standard cryptographic solutions (e.g. indistinguishability obfuscation) to achieve this re- quirement. In this work, we relax the requirement to have time- delayed publicly verifiable proofs, where the verification key is made known to the public only when the computation (and its proof) are guaranteed to have been completed. We propose a prac- tical non-interactive scheme leveraging commitment schemes and time-lock puzzles, which can be efficiently realized through well- established and standard post-quantum assumptions. The main idea of our technique lies in using time-lock puzzles to compile a 2-round privately verifiable scheme into a non-interactive publicly verifiable scheme with timestamped proofs, outsourcing not only the quantum computation but the puzzle solving as well. Security is proven in the quantum random oracle model with a common reference string (CRS).
The application and analysis of the Cut-and-Choose technique in protocols secure against quantum adversaries is not a straightforward transposition of the classical case, among other reasons due to the difficulty to use rewinding in the quantum realm. We introduce a Quantum Computation Cut-and-Choose (QC-CC) technique which is a generalisation of the classical Cut-and-Choose in order to build quantum protocols secure against quantum covert adversaries. Such adversaries can deviate arbitrarily provided that their deviation is not detected. As an application of the QC-CC we give a protocol for securely performing two-party quantum computation with classical input/output. As basis we use secure delegated quantum computing (Broadbent et al 2009), and in particular the garbled quantum computation of (Kashefi et al 2016) that is secure against only a weak specious adversaries, defined in (Dupuis et al 2010). A unique property of these protocols is the separation between classical and quantum communications and the asymmetry between client and server, which enables us to sidestep the quantum rewinding issues. This opens the prospect of using the QC-CC to other quantum protocols with this separation. In our proof of security we adapt and use (at different parts) two quantum rewinding techniques, namely Watrous' oblivious q-rewinding (Watrous 2009) and Unruh's special q-rewinding (Unruh 2012). Our protocol achieves the same functionality as in previous works (e.g. Dupuis et al 2012), however using the QC-CC technique on the protocol from (Kashefi et al 2016) leads to the following key improvements: (i) only one-way offline quantum communication is necessary , (ii) only one party (server) needs to have involved quantum technological abilities, (iii) only minimal extra cryptographic primitives are required, namely one oblivious transfer for each input bit and quantum-safe commitments.
Publicly verifiable delegation is a well-known problem involving a user who wishes to outsource a resource-intensive computational task to a more powerful but potentially untrusted server such that any other party is able to efficiently check the veracity of the computation's result. This problem has been extensively studied in the classical domain where the user and server are both non-quantum machines. However, the problem becomes more challenging when the classical user wants to delegate a quantum circuit to a single prover with quantum-computing capabilities. Previous solutions have resorted to using impractical or non-standard cryptographic solutions (e.g. indistinguishability obfuscation) to achieve this requirement. In this work, we relax the requirement to have time-delayed publicly verifiable proofs, where the verification key is made known to the public only when the computation (and its proof) are guaranteed to have been completed. We propose a practical non-interactive scheme leveraging commitment schemes and time-lock puzzles, which can be efficiently realized through well-established and standard post-quantum assumptions. The main idea of our technique lies in using time-lock puzzles to compile a 2-round privately verifiable scheme into a non-interactive publicly verifiable scheme with timestamped proofs, outsourcing not only the quantum computation but the puzzle solving as well. Security is proven in the quantum random oracle model with a common reference string (CRS).