A new protocol and lower bounds for quantum coin flipping

DOI10.1145/380752.380788zbMath1323.81023OpenAlexW2125657904MaRDI QIDQ5175961

Andris Ambainis

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380788

Mathematics Subject Classification ID

Quantum computation (81P68) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum cryptography (quantum-theoretic aspects) (81P94)

Related Items (8)

Secure certification of mixed quantum states with application to two-party randomness generation ⋮ Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game ⋮ Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment ⋮ Quantum dice rolling: a multi-outcome generalization of quantum coin flipping ⋮ Semi-loss-tolerant strong quantum coin-flipping protocol using quantum non-demolition measurement ⋮ On the power of Ambainis lower bounds ⋮ Weak coin flipping with small bias ⋮ A search for quantum coin-flipping protocols using optimization techniques

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: A new protocol and lower bounds for quantum coin flipping