Quantum Distributed Proofs for Replicated Data

This research explores Quantum Distributed Computing protocols for tasks like leader election, Byzantine agreement, and more. It introduces Quantum dMA protocols for verifying equality of replicated data on a network without shared randomness. The study discusses the need for efficient protocols with minimal rounds and outlines the distributed certification process in the context of distributed Merlin-Arthur protocols.

• Quantum Computing
• Distributed Protocols
• Replicated Data
• Network Verification

mkam Follow

Uploaded on Nov 14, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Distributed Quantum Proofs for Replicated Data arXiv: 2002.10018 Proc. ITCS2021 Pierre Fraigniaud (CNRS/U de Paris) Francois Le Gall, Harumichi Nishimura (Nagoya U) Ami Paz (U Wien) February 5th, 2021 QIP2021 1

2. Quantum Distributed Computing Leader election [Tani, Kobayashi, Matsumoto 05, 09] Byzantine agreement [Ben-Or, Hassidim 05] Diameter [Le Gall, Magniez 18] All pairs shortest paths [Izumi, Le Gall 19] Triangle finding [Izumi, Le Gall, Magniez 20] etc 2

3. Outline Problem (Equality of data on networks) Setting (Distributed Merlin-Arthur protocols) Results (Quantum dMA protocols) Overview of our protocol 3

4. Our Problem: Equality of Replicated Data YES Replicated data on a network Are all data identical? ? ? ? terminals (nodes who have data) 4

5. Our Problem: Equality of Replicated Data NO Replicated data on a network Are all data identical? ? ? ? terminals (nodes who have data) 5

6. Our Problem: Equality of Replicated Data Replicated data on a network Are all data identical? No O(1) round protocol (?) rounds are needed (? diameter of the network) We assume the nodes do not share prior randomness & entanglement 1 round NP-like protocol (distributed certification) ? ? ? terminals (nodes who have data) 6

7. Outline Problem (Equality of data on networks) Setting (Distributed Merlin-Arthur protocols) Results (Quantum dMA protocols) Overview of our protocol 7

8. Distributed Certification Verifier (Arthur) Distributed Merlin-Arthur (dMA) protocols Proof labeling scheme [Korman, Kutten, Peleg 10] Locally checkable proof [Goos, Suomela 16] etc ? ? ? P Prover (Merlin) ? 8

9. Distributed Certification Distributed Merlin-Arthur (dMA) protocols Proof labeling scheme [Korman, Kutten, Peleg 10] Locally checkable proof [Goos, Suomela 16] etc ? ? ? ? Two phases: 1. (Prover phase) Prover sends certificates to each node P Prover (Merlin) ? 9

10. Distributed Certification Distributed Merlin-Arthur (dMA) protocols Proof labeling scheme [Korman, Kutten, Peleg 10] Locally checkable proof [Goos, Suomela 16] etc ? ? ? ? Two phases: 1. (Prover phase) Prover sends certificates to each node 2. (Verification phase) Each node exchanges messages with the neighbors P Prover (Merlin) ? 10

11. Distributed Certification Distributed Merlin-Arthur (dMA) protocols Proof labeling scheme [Korman, Kutten, Peleg 10] Locally checkable proof [Goos, Suomela 16] etc ? ? Properties: (YES case: Completeness) ?[all nodes accept] (w.h.p.) (NO case: Soundness) ?[some node rejects] (w.h.p.) ? P Prover (Merlin) ? 11

12. Distributed Certification Distributed Merlin-Arthur (dMA) protocols Proof labeling scheme [Korman, Kutten, Peleg 10] Locally checkable proof [Goos, Suomela 16] etc ? ? ? ? Trivial protocol: (P) Prover sends ? when all data are ? (V) Each node checks if it is same as the neighbor s one ? ? P ? Prover (Merlin) ? ? (YES case: Completeness) ?[all nodes accept] ? 12

13. Distributed Certification Distributed Merlin-Arthur (dMA) protocols Proof labeling scheme [Korman, Kutten, Peleg 10] Locally checkable proof [Goos, Suomela 16] etc ? ? ? ? Trivial protocol: (P) Prover sends ? when all data are ? (V) Each node checks if it is same as the neighbor s one ? ? P ? Prover (Merlin) ? ? (NO case: Soundness) ?[some node rejects] ? 13

14. Distributed Certification Distributed Merlin-Arthur (dMA) protocols Proof labeling scheme [Korman, Kutten, Peleg 10] Locally checkable proof [Goos, Suomela 16] etc ? ? ? ? Trivial Protocol is communication inefficient Prover sends ? bits for each node (? length of ?) Each node sends ? bits to the neighbors ? ? P ? Prover (Merlin) ? ? ? 14

15. Outline Problem (Equality of data on networks) Setting (Distributed quantum Merlin-Arthur protocols) Results (Quantum dMA protocols) Overview of our protocol 15

16. Our Results Distributed Quantum Merlin-Arthur (dQMA) protocols Quantum certificates from the prover Quantum messages among nodes Quantum upper bound dQMA protocol for equality of replicated data with ?(??2log(? + ?))-qubit certificates & messages ?:= number of the terminals (= nodes who have data) ? diameter of the network ? and ? are typically much smaller than ? Classical lower bound Any dMA protocol requires (?)-bit certificates if error probability is reasonably small (say, 1/3) ? ? |? P |? ? 16

17. Outline Problem (Equality of data on networks) Setting (Distributed quantum Merlin-Arthur protocols) Results (Quantum dMA protocols) Overviews of our protocol Path networks # Our protocol for general networks is obtained by a combination of the protocol for paths and classical dMA protocols such as certifying spanning trees 17

18. Path Path network ? = 2, ? =path length Only the left & right nodes have input strings P ? ? 18

19. Path (2 nodes): Classical case ?(log?) messages are enough on the path of 2 nodes Prover is unnecessary Use hash functions Pr ? ? Length of pair , ? = ?(log?) 1/poly(?) when ? ? : randomly chosen : randomly chosen ( , (?)) ? ? ( , (?)) 19

20. Path (3 nodes or more): Classical case Similar strategy is impossible on the path of 3 nodes as the left node and the right node cannot communicate directly in one round The case of 3 nodes is similar to the SMP model in communication complexity (since the central node has no information on inputs and his/her simultaneous message is useless) : randomly chosen : randomly chosen ( , (?)) ( , (?)) ? ? 20

21. Path (3 nodes or more): Classical case Similar strategy is impossible on the path of 3 nodes Prover does not help much (as he/she might be malicious for NO instances) Classical lower bound (?)for the prover s certificate size can be proved for the path of 4 nodes P : may be NOT randomly chosen ? = ( , (?)) ? ? ? = ( , (?)) ? = ( , (?)) 21

22. Basic Tools for Quantum Protocol Quantum fingerprint [Buhrman, Cleve, Watrous, de Wolf 01] ? = | ? (?(log?)-qubit state) ? ? SWAP test [Buhrman, Cleve, Watrous, de Wolf 01] Can estimate ? ? ? log? is enough for the 3 nodes case without the prover (by [BCWW01]) Our protocol uses quantum fingerprints as certificates | ? | ? 2< 1/poly(?) when ? ? ? ? 2 even if the input states ?,| ? are not known Pr ? = 0 (accept) =1 2+1 2 M H |0 H ? ? 2 | ? | ? 22

23. Our Quantum Protocol (Prover phase) Honest prover (when ? = ?) sends certificate | ? to each of the intermediate nodes The left node creates | ? and the right node creates | ? P | ? | ? | ? | ? | ? | ? | ? ? ? 23

24. Our Quantum Protocol (Verification phase) 1. Each node ? (except right node) chooses ?? {0,1} uniformly at random: if ??= 0, ? sends the state to the right neighbor; otherwise, keep it by itself. 2. Each node (except left node) does SWAP test if it has two states, and outputs its result (accept/reject), and accepts otherwise P | ? | ? | ? | ? | ? | ? | ? ? ? 24 ?2= 0 ?3= 1

25. Analysis When ? = ?, all nodes accept with probability 1 P ? = ? ? | ? | ? | ? ? ? 25

26. Analysis When ? = ?, all nodes accept with probability 1 When ? ?, the probability that all nodes accept is 1 (1/?2) Soundness error can be reduced to 1/3 by ?(?2) repetitions P ? 1 2 | ? 1 | ? | ? ? ? 26

27. Soundness: ? ? (NO instance) We want some node to reject SWAP test with prob. (1/?2) The property we use: [Property] If the SWAP test accepts on input ???w.h.p., the two reduced states ??& ??must be close (?? ??) Assuming all nodes accept w.h.p., ? ?1 ?2 ?? 1 ?, which contradicts ? ? M H H |0 ??? 2 1/poly(?) P Verification phase ? 1 | ? 1 1. Each node ? (except right node) chooses ?? {0,1} uniformly at random: if ??= 0, ? sends the state to the right neighbor; otherwise, keep it by itself. Each node (except left node) does SWAP test if it has two states, and outputs its result (accept/reject), and accepts otherwise ? ? ? | ? | ? 2. ??= 0 ??+1= 1 27

28. Our Results & Future Work Distributed Quantum Merlin-Arthur (dQMA) protocols Quantum certificates from the prover Quantum messages among nodes Quantum upper bound dQMA protocol for equality of replicated data with ?(??2log(? + ?))-qubit certificates & messages (?:= number of the terminals; ? radius of the network) Extends to a more general protocol that converts one-way quantum communication complexity protocol to dQMA protocol Classical lower bound Any dMA protocol requires (?)-bit certificates if error probability is reasonably small (say, 1/3) Future Work dQMA protocols for other problems Lower bounds for dQMA protocols arXiv: 2002.10018 Proc. ITCS2021 28