Resource analysis for quantum-aided Byzantine agreement with the four-qubit singlet state

Zoltán Guba1, István Finta2,3, Ákos Budai1,4,2, Lóránt Farkas2, Zoltán Zimborás4,5, and András Pályi1,6

1Department of Theoretical Physics, Institute of Physics, Budapest University of Technology and Economics, Műegyetem rkp. 3., H-1111 Budapest, Hungary
2Nokia Bell Labs
3Óbuda University
4Wigner Research Centre for Physics, H-1525 Budapest, P.O.Box 49, Hungary
5Eötvös University, Budapest, Hungary
6MTA-BME Quantum Dynamics and Correlations Research Group, Műegyetem rkp. 3., H-1111 Budapest, Hungary

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


In distributed computing, a Byzantine fault is a condition where a component behaves inconsistently, showing different symptoms to different components of the system. Consensus among the correct components can be reached by appropriately crafted communication protocols even in the presence of byzantine faults. Quantum-aided protocols built upon distributed entangled quantum states are worth considering, as they are more resilient than traditional ones. Based on earlier ideas, here we establish a parameter-dependent family of quantum-aided weak broadcast protocols. We compute upper bounds on the failure probability of the protocol, and define and illustrate a procedure that minimizes the quantum resource requirements. Following earlier work demonstrating the suitability of noisy intermediate scale quantum (NISQ) devices for the study of quantum networks, we experimentally create our resource quantum state on publicly available quantum computers. Our work highlights important engineering aspects of the future deployment of quantum communication protocols with multi-qubit entangled states.

In distributed computing, an important challenge is to achieve system reliability in the presence of faulty components. This often requires protocols to reach consensus among the components. Applications of such consensus protocols range from aircraft flight control systems to blockchain technologies. In this work, we analyse a parameter-dependent family of consensus protocols that are based on entangled multi-partite quantum states that are distributed among the components. We prove that the protocol guarantees the consensus in a certain range of its parameters. We establish and exemplify a procedure that minimises the number of resource quantum states required to ensure a pre-defined low failure probability, highlighting important engineering aspects of the future deployment of such distributed protocols. We also prepare and benchmark the four-qubit resource state of our protocol, performing experiments on superconducting and trapped-ion quantum computers.

► BibTeX data

► References

[1] M. Pease, R. Shostak, and L. Lamport, ``Reaching Agreement in the Presence of Faults'' J. ACM 27, 228–234 (1980).

[2] Matthias Fitzi ``Generalized Communication and Security Models in Byzantine Agreement'' thesis (2003) Reprint as vol. 4 of ETH Series in Information Security and Cryptography, ISBN 3-89649-853-3, Hartung-Gorre Verlag, Konstanz, 2003.

[3] Leslie Lamport, Robert Shostak, and Marshall Pease, ``The Byzantine Generals Problem'' ACM Trans. Program. Lang. Syst. 4, 382–401 (1982).

[4] Juan Garayand Yoram Moses ``Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds'' SIAM Journal on Computing 27, 247–290 (1999).

[5] Miguel Castroand Barbara Liskov ``Practical byzantine fault tolerance'' OSDI 99, 173–186 (1999).

[6] Diego Ongaroand John Ousterhout ``In Search of an Understandable Consensus Algorithm'' Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference 305–320 (2014).

[7] Leslie Lamport ``The Part-Time Parliament'' ACM Trans. Comput. Syst. 16, 133–169 (1998).

[8] Matthias Fitzi, Nicolas Gisin, Ueli M. Maurer, and Oliver von Rotz, ``Unconditional Byzantine Agreement and Multi-Party Computation Secure against Dishonest Minorities from Scratch'' Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology 482–501 (2002).

[9] Adán Cabello ``Solving the liar detection problem using the four-qubit singlet state'' Phys. Rev. A 68, 012304 (2003).

[10] Sascha Gaertner, Mohamed Bourennane, Christian Kurtsiefer, Adán Cabello, and Harald Weinfurter, ``Experimental Demonstration of a Quantum Protocol for Byzantine Agreement and Liar Detection'' Phys. Rev. Lett. 100, 070504 (2008).

[11] Poramet Pathumsoot, Takaaki Matsuo, Takahiko Satoh, Michal Hajdušek, Sujin Suwanna, and Rodney Van Meter, ``Modeling of measurement-based quantum network coding on a superconducting quantum processor'' Phys. Rev. A 101, 052301 (2020).

[12] Mohammand Amin Taherkhani, Keivan Navi, and Rodney Van Meter, ``Resource-aware system architecture model for implementation of quantum aided Byzantine agreement on quantum repeater networks'' Quantum Science and Technology 3, 014011 (2017).

[13] Michael Ben-Orand Avinatan Hassidim ``Fast Quantum Byzantine Agreement'' Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing 481–485 (2005).

[14] Matthias Fitzi, Nicolas Gisin, and Ueli Maurer, ``Quantum Solution to the Byzantine Agreement Problem'' Phys. Rev. Lett. 87, 217901 (2001).

[15] Stephanie Wehner, David Elkouss, and Ronald Hanson, ``Quantum internet: A vision for the road ahead'' Science 362, eaam9288 (2018).

[16] M. Pompili, S. L. N. Hermans, S. Baier, H. K. C. Beukers, P. C. Humphreys, R. N. Schouten, R. F. L. Vermeulen, M. J. Tiggelman, L. dos Santos Martins, B. Dirkse, S. Wehner, and R. Hanson, ``Realization of a multinode quantum network of remote solid-state qubits'' Science 372, 259–264 (2021).

[17] John Preskill ``Quantum Computing in the NISQ era and beyond'' Quantum 2, 79 (2018).

[18] ``IBM Quantum'' https:/​/​​ (2021).

[19] Christopher Monroe ``IonQ Quantum Computers: Clear to Scale'' APS March Meeting Abstracts 2021, P10.002 (2021).

[20] P. Magnard, S. Storz, P. Kurpiers, J. Schär, F. Marxer, J. Lütolf, T. Walter, J.-C. Besse, M. Gabureac, K. Reuer, A. Akin, B. Royer, A. Blais, and A. Wallraff, ``Microwave Quantum Link between Superconducting Circuits Housed in Spatially Separated Cryogenic Systems'' Phys. Rev. Lett. 125, 260502 (2020).

[21] Simon Storz, Josua Schär, Anatoly Kulikov, Paul Magnard, Philipp Kurpiers, Janis Lütolf, Theo Walter, Adrian Copetudo, Kevin Reuer, Abdulkadir Akin, Jean-Claude Besse, Mihai Gabureac, Graham J. Norris, Andrés Rosario, Ferran Martin, José Martinez, Waldimar Amaya, Morgan W. Mitchell, Carlos Abellan, Jean-Daniel Bancal, Nicolas Sangouard, Baptiste Royer, Alexandre Blais, and Andreas Wallraff, ``Loophole-free Bell inequality violation with superconducting circuits'' Nature 617, 265–270 (2023).

[22] D. Hucul, I. V. Inlek, G. Vittorini, C. Crocker, S. Debnath, S. M. Clark, and C. Monroe, ``Modular entanglement of atomic qubits using photons and phonons'' Nature Physics 11, 37–42 (2015).

[23] V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. A. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Canteri, M. Teller, J. Schupp, J. Bate, M. Meraner, N. Sangouard, B. P. Lanyon, and T. E. Northup, ``Entanglement of Trapped-Ion Qubits Separated by 230 Meters'' Phys. Rev. Lett. 130, 050803 (2023).

[24] L. J. Stephenson, D. P. Nadlinger, B. C. Nichol, S. An, P. Drmota, T. G. Ballance, K. Thirumalai, J. F. Goodwin, D. M. Lucas, and C. J. Ballance, ``High-Rate, High-Fidelity Entanglement of Qubits Across an Elementary Quantum Network'' Phys. Rev. Lett. 124, 110501 (2020).

[25] Constantin Gonzalez ``Cloud based QC with Amazon Braket'' Digitale Welt 5, 14–17 (2021).

[26] Yanzhu Chen, Maziar Farahzad, Shinjae Yoo, and Tzu-Chieh Wei, ``Detector tomography on IBM quantum computers and mitigation of an imperfect measurement'' Physical Review A 100, 052315 (2019).

[27] Filip B Maciejewski, Zoltán Zimborás, and Michał Oszmaniec, ``Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography'' Quantum 4, 257 (2020).

[28] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani, ``Device-Independent Security of Quantum Cryptography against Collective Attacks'' Phys. Rev. Lett. 98, 230501 (2007).

[29] Feihu Xu, Xiongfeng Ma, Qiang Zhang, Hoi-Kwong Lo, and Jian-Wei Pan, ``Secure quantum key distribution with realistic devices'' Rev. Mod. Phys. 92, 025002 (2020).

[30] Akos Budai, Istvan Finta, and Zoltán Guba, ``akosbudai/​quantum-byzantine: v0.0.2'' (2023).

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-05-26 09:21:03). On SAO/NASA ADS no data on citing works was found (last attempt 2024-05-26 09:21:04).