Blockchain technology relies on the ability of a network of non-cooperating participants to reach consensus on validating and verifying a new set of block-bundled transactions, in a setting without centralized authority. A consensus algorithm is a procedure through which all the peers of the blockchain network reach a common agreement about the present state of the distributed ledger. One of the best tested consensus algorithms which has demonstrated robustness and security is Proof-of-Work (PoW).
PoW relies on validating a proposed block of new transactions to be added to the blockchain by selecting and rewarding a successful “miner” who is the first to solve a computational puzzle. This puzzle involves a one-way function, i.e. a function that is easy to compute, and hence easy to verify, but hard to invert.
There are, however, two issues that threaten to compromise continued usage of PoW consensus in a scalable manner. The first is energy consumption. The second issue is that PoW assumes only classical computers are available as mining resources.
Quantum computing technology, while only at the prototype stage now, is rapidly developing. Quantum computers running Grover’s search algorithm, can achieve a quadratic speedup in solving unstructured problems like inverting one-way functions. This means if they were integrated into PoW, the progress-free condition (the probability of successfully mining a block at any given instant is independent of prior mining attempts) would no longer apply and the probability of solving the problem grows super-linearly with computational time spent.
In a recent paper, researchers at academic institutions from Australia, Canada and the US have proposed a PoW consensus protocol that natively makes use of the quantum speedup afforded by boson-samplers. The quantum hardware required for the implementation of their protocol has already been experimentally demonstrated at a sufficient scale and is becoming commercially available (Xanadu Borealis).
Abstract
Since its advent in 2011, boson-sampling has been a preferred candidate for demonstrating quantum advantage because of its simplicity and near-term requirements compared to other quantum algorithms. Researchers propose to use a variant, called coarse-grained boson-sampling (CGBS), as a quantum Proof-of-Work (PoW) scheme for blockchain consensus.
The users perform boson-sampling using input states that depend on the current block information, and commit their samples to the network. Afterward, CGBS strategies are determined which can be used to both validate samples and to reward successful miners.
By combining rewards to miners committing honest samples together with penalties to miners committing dishonest samples, a Nash equilibrium is found that incentivizes honest nodes. The scheme works for both Fock state boson sampling and Gaussian boson sampling and provides dramatic speedup and energy savings relative to computation by classical hardware.