Exploring Grover's Algorithm

In this week’s episode, Anna Rose and Kobi Gurkan chat with Or Sattath, Assistant Professor at the Ben-Gurion University in the Computer Science department. They deep dive into Or’s work on Quantum Cryptography. They begin with definitions of Quantum Computing and Quantum Cryptography, covering what these will mean for existing cryptography. They also explore how new discoveries in this field can interact with existing Proof-of-work systems and how Quantum computers could affect the game theory of mining in the future.

Here’s some additional links for this episode:

• On the insecurity of quantum Bitcoin mining by Sattath
• Strategies for quantum races by Lee, Ray, and Santha
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer by Shor
• Shor’s Algorithm
• Grover’s Algorithm
• A fast quantum mechanical algorithm for database search by Grover
• Bell’s Theorem

More in-depth resources recommended by Or Sattath:

• A recommended smbc-comics about the power of quantum computing, authored by Zack Weinersmith (the usual cartoonist) and Scott Aaronson (a quantum computing expert)
• For an in-depth introduction to quantum computing, I recommend Ronald de-Wolf's lecture notes
• The Bitcoin backbone protocol with a single quantum miner, by Cojocaru et al
• The fingerprint of quantum mining slightly below 16 minutes by Nerem-Gaur
• Some estimates regarding timelines, which we didn't discuss, are available here and here
• The insecurity of quantum Bitcoin mining, and the need to change the tie-breaking rule.
• The work by Lee-Ray-Santh that analyzes the equilibrium strategy for multiple quantum miners, as a simplified one-shot game.

zkSummit 10 is happening in London on September 20, 2023! Apply to attend now -> zkSummit 10 Application Form.

Polygon Labs is thrilled to announce Polygon 2.0: The Value Layer for the Internet.

Polygon 2.0 and all of our ZK tech is open-source and community-driven. Reach out to the Polygon community on Discord to learn more, contribute, or join in and build the future of Web3 together with Polygon!

If you like what we do:

• Find all our links here! @ZeroKnowledge | Linktree
• Subscribe to our podcast newsletter
• Follow us on Twitter @zeroknowledgefm
• Join us on Telegram
• Catch us on YouTube