  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. We 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.
