Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries

In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including…

• NS
  National Science Foundation

  Awards: CREST, 2022699
• MO
  Ministry of Education, Culture, Sports, Science and Technology

  Awards: CREST, JPMXS0120319794
• IS
  Israel Science Foundation

  Award: 2801/20
• JS
  Japan Society for the Promotion of Science

  Awards: JP20H05966, 20H00579, JPMXS0120319794, 22H00522, CREST, 24H00071, 24K22293
• CR
  Core Research for Evolutional Science and Technology

  Award: JPMJCR24I4