paint-brush
How Many Grover Iterations Should a Quantum Bitcoin Miner Apply?by@escholar

How Many Grover Iterations Should a Quantum Bitcoin Miner Apply?

tldt arrow

Too Long; Didn't Read

This section explores how Grover’s quantum algorithm could disrupt Bitcoin mining, highlighting the challenges quantum miners face in optimizing their search process within the race for blocks.
featured image - How Many Grover Iterations Should a Quantum Bitcoin Miner Apply?
EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture
0-item

Abstract and I. Introduction

A. Quantum Bitcoin Mining

B. Our Contribution

C. Comparison with Related Works

D. Conventions

II. Background

A. Bitcoin Basics

B. Bitcoin Security

C. Grover’s Search Algorithm

D. Quantum Attacks

III. Approach

A. Algorithm

B. Markov Chain

C. Assumptions and Approximations

IV. Results

A. Probability of Success

B. Performance Measures

C. Example Application

V. Discussion, Acknowledgments, and References

A. Quantum Bitcoin Mining

Bitcoin mining is the process through which blocks are added to the Bitcoin blockchain, a public ledger which records transactions. In Bitcoin mining, miners attempt for a given hash function f, they search for a string x such that f(x) is less than some threshold τ . A solution to this problem yields a proof-of-work which allows the miner to add a block to the blockchain and receive a subsequent Bitcoin reward. Partial inversion of a hash function is equivalent to searching for a marked item in an unordered list of items (unstructured search) if f is computationally inefficient to invert. Here, x such that f(x) < τ are the marked items. Bitcoin mining is therefore an obvious potential application of Grover’s quantum algorithm for unstructured search [13]. Whereas classical algorithms for unstructured search find a marked item in Θ(√D) queries to f, where D := N/M is the ratio of total items to marked items, Grover’s search can find a marked item in Θ(√ D) queries [6, 27]. We refer to queries to a hash function f by hashes.


Quantum and classical search algorithms differ in another important way. The optimal classical algorithm for unstructured search is the simple brute-force method of guessing and checking through the search space in some random order. Contrarily, Grover’s algorithm consists of applying some number of quantum operations called Grover iterations followed by a measurement, where each Grover iteration contains two hashes. Unlike the classical brute-force algorithm, which can yield a marked item after any hash, Grover’s algorithm can only yield a marked item after the measurement step. Additionally, the more Grover iterations applied before measurement, the higher the probability that measurement yields a solution (assuming fewer than the optimal number of Grover iterations are applied).


This difference between classical and quantum search algorithms has key consequences to Bitcoin’s proof-ofwork. What makes Bitcoin sensitive to this difference is that miners race to be the first to find a marked item. It is important to win the race, as only a single winner reaps the Bitcoin reward for each block added. Once a block is added, a new search problem begins rendering progress on the previous problem irrelevant. For a classical miner the race setting does not change the optimal procedure from brute-force search. However, the difficulty in evaluating the effectiveness of quantum mining is that, for a quantum miner, determining the optimal procedure in the race setting requires answering the following question first asked in [21].


Question 1. How many Grover iterations should a quantum Bitcoin miner apply before measuring?


On one hand, the more Grover iterations the quantum miner applies before measuring, the more likely another miner is able to solve the problem before the measurement step is reached. On the other hand, the less Grover iterations the quantum miner applies before measuring, the less advantage they have over classical algorithms. What makes answering Question 1 challenging is that the optimal choice of when to measure depends on when other miners are expected to find a marked item.


Authors:

(1) Robert R. Nerem, Institute for Quantum Science and Technology, University of Calgary, Alberta T2N 1N4, Canada (riley.nerem@gmail.com);

(2) Daya R. Gaur, Department of Mathematics and Computer Science, University of Lethbridge, Alberta T1K 3M4, Canada.


This paper is available on arxiv under CC BY 4.0 DEED license.