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

Communication-Optimal Blind Quantum Protocols

Davies, Ethan, Alastair Kay

Published Oct 8, 2025• 0 citations
arXivHTMLPDF

Abstract

A user, Alice, wants to get server Bob to implement a quantum computation for her. However, she wants to leave him blind to what she's doing. What are the minimal communication resources Alice must use in order to achieve information-theoretic security? In this paper, we consider a single step of the protocol, where Alice conveys to Bob whether or not he should implement a specific gate. We use an entropy-bounding technique to quantify the minimum number of qubits that Alice must send so that Bob cannot learn anything about the gate being implemented. We provide a protocol that saturates this bound. In this optimal protocol, the states that Alice sends may be entangled. For Clifford gates, we prove that it is sufficient for Alice to send separable states.

DOI
10.48550/arxiv.2510.07112

Related papers

Blind quantum computation protocol in which Alice only makes measurements

Tomoyuki Morimae, Keisuke Fujii

Blind quantum computation is a new secure quantum computing protocol which enables Alice (who does not have sufficient quantum technology) to delegate her quantum computation to Bob (who has a full-fledged quantum computer) in such a way that Bob cannot learn anything about Alice's input, output, and algorithm. In previous protocols, Alice needs to have a device which generates quantum states, such as single-photon states. Here we propose another type of blind computing protocol where Alice does only measurements, such as the polarization measurements with a threshold detector. In several experimental setups, such as optical systems, the measurement of a state is much easier than the generation of a single-qubit state. Therefore our protocols ease Alice's burden. Furthermore, the security of our protocol is based on the no-signaling principle, which is more fundamental than quantum physics. Finally, our protocols are device independent in the sense that Alice does not need to trust her measurement device in order to guarantee the security.

arXiv:1201.3966•Physical Review A•May 13, 2013•186 citations

BLIND QUANTUM COMPUTATION

Pablo J. Arrighi, Louis Salvail

We investigate the possibility of having someone carry out the work of executing a function for you, but without letting him learn anything about your input. Say Alice wants Bob to compute some known function f upon her input x, but wants to prevent Bob from learning anything about x. The situation arises for instance if client Alice has limited computational resources in comparison with mistrusted server Bob, or if x is an inherently mobile piece of data. Could there be a protocol whereby Bob is forced to compute ,f(x)blindly, i.e. without observing x? We provide such a blind computation protocol for the class of functions which admit an efficient procedure to generate random input–output pairs, e.g. factorization. The cheat-sensitive security achieved relies only upon quantum theory being true. The security analysis carried out assumes the eavesdropper performs individual attacks.

arXiv:quant-ph/0309152•International Journal of Quantum Information•Oct 1, 2006•141 citations

Secure assisted quantum computation

Andrew M. Childs

Suppose Alice wants to perform some computation that could be done quickly on a quantum computer, but she cannot do universal quantum computation. Bob can do universal quantum computation and claims he is willing to help, but Alice wants to be sure that Bob cannot learn her input, the result of her calculation, or perhaps even the function she is trying to compute. We describe a simple, efficient protocol by which Bob can help Alice perform the computation, but there is no way for him to learn anything about it. We also discuss techniques for Alice to detect whether Bob is honestly helping her or if he is introducing errors.

Quantum Information and Computation•Sep 1, 2005•130 citations

Towards communication-efficient quantum oblivious key distribution

M. V. Panduranga Rao, Markus Jakobi

Symmetrically private information retrieval, a fundamental problem in the field of secure multiparty computation, is defined as follows: A database $D$ of $N$ bits held by Bob is queried by a user Alice who is interested in the bit ${D}_{b}$ in such a way that (1) Alice learns ${D}_{b}$ and only ${D}_{b}$ and (2) Bob does not learn anything about Alice's choice $b$. While solutions to this problem in the classical domain rely largely on unproven computational complexity theoretic assumptions, it is also known that perfect solutions that guarantee both database and user privacy are impossible in the quantum domain. Jakobi et al. [Phys. Rev. A 83, 022301 (2011)] proposed a protocol for oblivious transfer using well-known quantum key device (QKD) techniques to establish an oblivious key to solve this problem. Their solution provided a good degree of database and user privacy (using physical principles like the impossibility of perfectly distinguishing nonorthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of the Scarani-Acin-Ribordy-Gisin 2004 protocol). However, their quantum oblivious key distribution (QOKD) protocol requires a communication complexity of $O(N\mathrm{log}N)$. Since modern databases can be extremely large, it is important to reduce this communication as much as possible. In this paper, we first suggest a modification of their protocol wherein the number of qubits that need to be exchanged is reduced to $O(N)$. A subsequent generalization reduces the quantum communication complexity even further in such a way that only a few hundred qubits are needed to be transferred even for very large databases.

arXiv:1208.2501•Physical Review A•Jan 28, 2013•63 citations

Selectively Blind Quantum Computation

Abbas Poshtvan, Oleksandra Lapiha, Mina Doosti +3 more

Known protocols for secure delegation of quantum computations from a client to a server in an information theoretic setting require quantum communication. In this work, we investigate methods to reduce communication overhead. First, we establish an impossibility result by proving that server-side local processes cannot decrease quantum communication requirements of secure delegation protocols. We develop no-go results that prohibit such processes within an information theoretic framework. Second, we present a possibility result by introducing Selectively Blind Quantum Computing (SBQC), a novel functionality that allows the client to hide one among a known set of possible computations. We characterize how differences between computations in the protected set influence the number of qubits sent during our SBQC implementation, yielding a communication-optimal protocol. This approach reduces qubit communication drastically and demonstrates the trade-off between information leaked to the server and communication cost.

arXiv:2504.17612•Apr 24, 2025•0 citations

Secure assisted quantum computation

Andrew M. Childs

Suppose Alice wants to perform some computation that could be done quickly on a quantum computer, but she cannot do universal quantum computation. Bob can do universal quantum computation and claims he is willing to help, but Alice wants to be sure that Bob cannot learn her input, the result of her calculation, or even the function she is trying to compute. We describe an efficient protocol by which Bob can help Alice perform the computation, but there is no way for him to learn anything about it. Furthermore, we show how Alice can efficiently detect whether Bob is honestly helping her or if he is introducing errors.

Quantum Information and Computation•Sep 1, 2005•111 citations
A user, Alice, wants to get server Bob to implement a quantum computation for her. However, she wants to leave him blind to what she's doing. What are the minimal communication resources Alice must use in order to achieve information-theoretic security? In this paper, we consider a single step of the protocol, where Alice conveys to Bob whether or not he should implement a specific gate. We use an entropy-bounding technique to quantify the minimum number of qubits that Alice must send so that Bob cannot learn anything about the gate being implemented. We provide a protocol that saturates this bound. In this optimal protocol, the states that Alice sends may be entangled. For Clifford gates, we prove that it is sufficient for Alice to send separable states.
Blind quantum computation is a new secure quantum computing protocol which enables Alice (who does not have sufficient quantum technology) to delegate her quantum computation to Bob (who has a full-fledged quantum computer) in such a way that Bob cannot learn anything about Alice's input, output, and algorithm. In previous protocols, Alice needs to have a device which generates quantum states, such as single-photon states. Here we propose another type of blind computing protocol where Alice does only measurements, such as the polarization measurements with a threshold detector. In several experimental setups, such as optical systems, the measurement of a state is much easier than the generation of a single-qubit state. Therefore our protocols ease Alice's burden. Furthermore, the security of our protocol is based on the no-signaling principle, which is more fundamental than quantum physics. Finally, our protocols are device independent in the sense that Alice does not need to trust her measurement device in order to guarantee the security.
We investigate the possibility of having someone carry out the work of executing a function for you, but without letting him learn anything about your input. Say Alice wants Bob to compute some known function f upon her input x, but wants to prevent Bob from learning anything about x. The situation arises for instance if client Alice has limited computational resources in comparison with mistrusted server Bob, or if x is an inherently mobile piece of data. Could there be a protocol whereby Bob is forced to compute ,f(x)blindly, i.e. without observing x? We provide such a blind computation protocol for the class of functions which admit an efficient procedure to generate random input–output pairs, e.g. factorization. The cheat-sensitive security achieved relies only upon quantum theory being true. The security analysis carried out assumes the eavesdropper performs individual attacks.
Suppose Alice wants to perform some computation that could be done quickly on a quantum computer, but she cannot do universal quantum computation. Bob can do universal quantum computation and claims he is willing to help, but Alice wants to be sure that Bob cannot learn her input, the result of her calculation, or perhaps even the function she is trying to compute. We describe a simple, efficient protocol by which Bob can help Alice perform the computation, but there is no way for him to learn anything about it. We also discuss techniques for Alice to detect whether Bob is honestly helping her or if he is introducing errors.
Symmetrically private information retrieval, a fundamental problem in the field of secure multiparty computation, is defined as follows: A database DDD of NNN bits held by Bob is queried by a user Alice who is interested in the bit Db{D}_{b}Db​ in such a way that (1) Alice learns Db{D}_{b}Db​ and only Db{D}_{b}Db​ and (2) Bob does not learn anything about Alice's choice bbb. While solutions to this problem in the classical domain rely largely on unproven computational complexity theoretic assumptions, it is also known that perfect solutions that guarantee both database and user privacy are impossible in the quantum domain. Jakobi et al. [Phys. Rev. A 83, 022301 (2011)] proposed a protocol for oblivious transfer using well-known quantum key device (QKD) techniques to establish an oblivious key to solve this problem. Their solution provided a good degree of database and user privacy (using physical principles like the impossibility of perfectly distinguishing nonorthogonal quantum states and the impossibility of superluminal communication) while being loss-resistant and implementable with commercial QKD devices (due to the use of the Scarani-Acin-Ribordy-Gisin 2004 protocol). However, their quantum oblivious key distribution (QOKD) protocol requires a communication complexity of O(NlogN)O(N\mathrm{log}N)O(NlogN). Since modern databases can be extremely large, it is important to reduce this communication as much as possible. In this paper, we first suggest a modification of their protocol wherein the number of qubits that need to be exchanged is reduced to O(N)O(N)O(N). A subsequent generalization reduces the quantum communication complexity even further in such a way that only a few hundred qubits are needed to be transferred even for very large databases.
Known protocols for secure delegation of quantum computations from a client to a server in an information theoretic setting require quantum communication. In this work, we investigate methods to reduce communication overhead. First, we establish an impossibility result by proving that server-side local processes cannot decrease quantum communication requirements of secure delegation protocols. We develop no-go results that prohibit such processes within an information theoretic framework. Second, we present a possibility result by introducing Selectively Blind Quantum Computing (SBQC), a novel functionality that allows the client to hide one among a known set of possible computations. We characterize how differences between computations in the protected set influence the number of qubits sent during our SBQC implementation, yielding a communication-optimal protocol. This approach reduces qubit communication drastically and demonstrates the trade-off between information leaked to the server and communication cost.
Suppose Alice wants to perform some computation that could be done quickly on a quantum computer, but she cannot do universal quantum computation. Bob can do universal quantum computation and claims he is willing to help, but Alice wants to be sure that Bob cannot learn her input, the result of her calculation, or even the function she is trying to compute. We describe an efficient protocol by which Bob can help Alice perform the computation, but there is no way for him to learn anything about it. Furthermore, we show how Alice can efficiently detect whether Bob is honestly helping her or if he is introducing errors.