paint-brush
Assumptions and Approximations for Quantum Bitcoin Miningby@escholar

Assumptions and Approximations for Quantum Bitcoin Mining

tldt arrow

Too Long; Didn't Read

This section outlines assumptions and approximations for quantum Bitcoin mining, including the quantum miner's Grover iteration speed, computational power compared to the network, and simplifications made to focus on mining time.
featured image - Assumptions and Approximations for Quantum Bitcoin Mining
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

C. Assumptions and Approximations


We now motivate each part of our assumption. We take 1 <<K since if K is close to 1 then the quantum miner has little advantage over classical mining. Furthermore, even a relatively slow quantum computer is still fast enough to apply many more than a single Grover iteration in the 10 minutes average time it takes for a block to be mined. As an example, if r is one Grover iteration per second then the quantum miner can apply 600 Grover iterations in 10 minutes.


Second, we take K <<√G since this aligns with the quantum computer having small computational power compared to the Bitcoin network, which is the predicted to be the most likely scenario by [4]. To see this, notice if K is near √ G then quantum miner mines blocks with high probability. We expect K <<√G if r/λ0 <<√D, that is, if the number of Grover iterations the quantum miner can apply in 10 minutes is small compared to optimal.


We take the stronger assumption that mK <<√D in the final step of our derivation of conditions for advantegous quantum mining (Eq. 68). As K is the number of sequential Grover iterations the quantum miner applies, and mK is the total number of Grover iterations they apply (both sequential and in parallel) this is the regime in which the quantum miner applies far fewer Grover iterations than the optimal number of sequential Grover iterations before measuring. No other approximations in our paper require mK  K.


We distinguish between λ, the rate at which classical miners mine blocks, and λ0 the rate at which the entire network mines blocks. However, in the small computational power regime, the quantum miner contributes only a small portion to the rate at which blocks are mined by the network. As a result, λ ≈ λ0. We frequently turn to this approximation to make simplifications as λ0 is fixed to 10 minutes by the Bitcoin protocol.


For all parts of our analysis, we only consider the time cost to implement Grover iterations. We expect this time cost to dominate the time used by other operations such as measuring quantum registers, resetting quantum registers, and inverting η. This assumption is accurate in the 1 >>K limit we consider.


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.