* [36] A.J.E.M. Janssen, S.J.L. Eijndhoven _Spaces of type W, growth of Hermite coefficients, Wigner distribution, and Bargmann transform_, J. Math. Anal. Appl. 152 (1990), 368–390.
  * [37] K. Kato, M. Kobayashi, S. Ito _Remark on wave front sets of solutions to Schrödinger equation of a free particle and a harmonic oscillator_ , SUT J. Math. 47 (2011), 175–183.
  * [38] K. Kato, M. Kobayashi, S. Ito _Representation of Schrödinger operator of a free particle via short time Fourier transform and its applications_ , Tohoku Math. J. 64 (2012), 223–231.
  * [39] K. Kato, M. Kobayashi, S. Ito _Remarks on Wiener Amalgam space type estimates for Schrödinger equation_ , in: RIMS Kôkyûroku Bessatsu, B33, Res. Inst. Math. Sci. (RIMS), Kyoto 2012, pp. 41–48.
  * [40] K. Kato, M. Kobayashi, S. Ito _Estimates on modulation spaces for Schrödinger evolution operators with quadratic and sub-quadratic potentials_ , J. Func. Anal. 266 (2014), 733–753.
  * [41] H. Kober _Wurzeln aus der Hankel- und Fourier und anderen stetigen Transformationen_ , Quart. J. Math. Oxford Ser. 10 (1939), 45–49.
  * [42] M. A. Kutay, H. M. Ozaktas _The Fractional Fourier Transform and Harmonic Oscillation_ Nonlinear Dynam. 29 (2002), 157–172.
  * [43] F. G. Mehler _Ueber die Entwicklung einer Function von beliebig vielen Variabeln nach Laplaceschen Functionen höherer Ordnung_ , J. Reine Angew. Math. (in German) 66 (1866), 161–176.
  * [44] V. Namias _The fractional order Fourier transform and its application to quantum mechanics_ , J. Inst. Math. Appl. 25 (1980), 241–265.
  * [45] H. M. Ozaktas, Z. Zalevsky, M. A. Kutay _The fractional Fourier transform_ , Wiley Series in Pure and Applied Optics, Wiley, 2001.
  * [46] S. Pilipović _Generalization of Zemanian spaces of generalized functions which have orthonormal series expansions_ , SIAM J. Math. Anal. 17 (1986), 477–484.
  * [47] S. Pilipović _Tempered ultradistributions_ , Boll. U.M.I. 7 (1988), 235–251.
  * [48] M. Reed, B. Simon _Methods of Modern Mathematical Physics_ , Academic Press, London New York, 1979.
  * [49] J. J. Sakurai, J. Napolitano _Modern quantum mechanics_ , Pearson Education, Inc., 2011.
  * [50] R. J. Taggart _Inhomogeneous Strichartz estimates_ , Forum Math. 22 (2010), 825–853.
  * [51] J. Toft _Continuity properties for modulation spaces, with applications to pseudo-differential operators, II_ , Ann. Glob. Anal. and Geom. 26 (2004), 73–106.
  * [52] J. Toft _The Bargmann transform on modulation and Gelfand-Shilov spaces, with applications to Toeplitz and pseudo-differential operators_ , J. Pseudo-Differ. Oper. Appl. 3 (2012), 145–227.
  * [53] J. Toft _Images of function and distribution spaces under the Bargmann transform_ , J. Pseudo-Differ. Oper. Appl. 8 (2017), 83–139.
  * [54] J. Toft _Wick and Anti-Wick Characterizations of Linear Operators on Spaces of Power Series Expansions_ , J. Fourier Anal. Appl. 28, Paper no. 71.
  * [55] P. Wahlberg _Semigroups for quadratic evolution equations acting on Shubin–Sobolev and Gelfand–Shilov spaces_ , Ann. Fenn. Math. 47 (2022), 821–853.


# Uncertainty in Real-Time Semantic Segmentation on Embedded Systems

Ethan Goan, Clinton Fookes
Queensland University of Technology
Queensland, Australia
<EMAIL_ADDRESS>
###### Abstract

Application for semantic segmentation models in areas such as autonomous
vehicles and human computer interaction require real-time predictive
capabilities. The challenges of addressing real-time application is amplified
by the need to operate on resource constrained hardware. Whilst development of
real-time methods for these platforms has increased, these models are unable
to sufficiently reason about uncertainty present when applied on embedded
real-time systems. This paper addresses this by combining deep feature
extraction from pre-trained models with Bayesian regression and moment
propagation for uncertainty aware predictions. We demonstrate how the proposed
method can yield meaningful epistemic uncertainty on embedded hardware in
real-time whilst maintaining predictive performance.

##  1 Introduction

Development and capabilities of semantic segmentation models has increased
dramatically, with models based on deep learning applied to domains such as
autonomous vehicles [1, 2, 3], robotics [4] and human computer interaction [5,
2]. Practical application in these areas requires systems to provide real-time
performance, and in safety critical domains meaningful uncertainty information
is essential. Providing this uncertainty information becomes increasingly
challenging for real-time operation, as obtaining this uncertainty information
can considerably increase compute demands. A natural way to represent
epistemic uncertainty is through a Bayesian framework, where uncertainty in
the model is propagated to predictions.

Complete Bayesian inference is intractable for deep learning models, meaning
expensive Monte Carlo integration is often used for approximate inference [6,
7, 8]. These sampling based techniques considerably increase the time required
for prediction, making them unsuitable for real-time operation. Other research
have proposed utilising uncertainty information during training [9, 10],
though are unable to sufficiently reason about epistemic uncertainty present
during predictions. Given that the primary practical application of many
semantic segmentation models is performed on edge computing devices, it is
crucial that we are able to deliver this uncertainty information on these
platforms in real time.

input image

segmentation

epistemic uncertainty

aleatoric uncertainty

Figure 1: Example of semantic segmentation results obtainable from proposed
real-time semantic segmentation method and the forms of uncertainty it permits
in real-time applications.

This work aims to address this through the use of an analytic probabilistic
module inspired by the work of the Gaussian Process treatments of deep kernel
learning and Bayesian optimization [11, 12], where the task of feature
extraction is computed deterministically with fixed model parameters, which
are then used as inputs to a probabilistic classification module. Complexity
for Gaussian processes is cubic in the number of training samples, thus making
them infeasible for the intended applications. Instead we opt for
parameterised probabilistic regression module combined with a moment
propagating non-linearity for classification. This reduces the inference
overhead for high-dimensional data whilst providing analytic results when
using conjugate models, avoiding the need for expensive Monte Carlo
approximations. We demonstrate how this approach can be applied to existing
real-time semantic segmentation models on embedded hardware whilst providing
meaningful uncertainty measures with minimal compute overhead. An example of
the predictions and uncertainty measures for the presented models is shown in
Figure 1. The contributions of this paper are as follows,

  * •

Propose a light-weight method for uncertainty in semantic segmentation by
combining Bayesian methods within moment propagation,

  * •

Develop meaningful real-time aleatoric and epistemic uncertainty metrics and
investigation into how they can inform end users and decision protocols,

  * •

Demonstrate how these methods can be easily adapted to pre-trained models,
enabling them to provide real time uncertainty quantification on embedded
devices.

##  2 Related Work

###  2.1 Deep Learning Models for Real-Time Semantic Segmentation

Whilst state-of-the-art methods in terms of predictive performance utilise
modern deep-learning architectures such as transformers [13, 14] or large
Fully Convolutional Networks (FCN) models [15, 16], real-time methods are
restricted to a class of computationally efficient methods that allow them to
be deployed in practice. Real-time semantic segmentation models utilising deep
learning architectures traditionally build upon [17] by using FCN
architectures consisting of both an encoder and decoder. Foundational real-
time methods include ENet [18] which provides a lightweight FCN utilising
skip-connections and bottleneck layers similar to ResNets [19], and max-
unpooling in the decoder stage. This lightweight model has shown to provide
fast predictive performance on consumer hardware at the expense of accuracy.
Modern real-time models extend upon this work to design more complex encoders
and decoders [20] or through the inclusion of additional auxilliary loss
functions that aim to capture semantic information over a larger receptive
field[21, 22, 23].

###  2.2 Uncertainty in Semantic Segmentation

Description of epistemic uncertainty in semantic segmentation methods
typically rely on sampling based procedures such as Monte-Carlo Dropout [8,
24, 25, 6]. To obtain uncertainty information with these methods, a single
sample must be passed through the model multiple times whilst sampling model
parameters from the approximate posterior. These factors restrict their
application to offline methods where considerable compute resources are
available. Deterministic Uncertainty Quantification (DUQ) methods avoid the
need for multiple forward passes during test time, though requires the
inclusion of an additional weight matrix for each class present in the dataset
and a Gaussian Discriminant Model to be placed afterwards [26, 27]. [28]
provide an uncertainty mechanism building upon Monte-Carlo Dropout that
incorporates averages of an optical flow model to avoid multiple forward
passes through frames, though is only applicable to video capture scenarios
and relies on aggregating samples over multiple time-steps. This aggregation
increases memory footprint for predictions, as prior samples from the optical
flow model need to be stored, and computational load is increased due to the
need to calculate uncertainty metrics over samples within the flow model. None
of the methods reviewed here have been shown to offer real-time predictive
performance on traditional hardware, and to the best of our knowledge no prior
work has investigated real-time epistemic uncertainty estimation on resource
constrained embedded devices.

###  2.3 Gaussian Process Methods and Expectation Propagation

To address the limitations of existing uncertainty quantification for semantic
segmentation, we will build upon the work of Deep Gaussian Process models and
Expectation Propegation (EP). Deep Gaussian Process models such as [11, 12]
separate the tasks of feature extraction and classification, where a Gaussian
Process (GP) model is utilised for probabilistic classification. Whilst GPs
reduce the need for multiple forward passes, their application requires a
large number of parameters to approximate the corresponding covariance
function. [29] use a similar concept for separating feature extraction and
probabilistic classification for monocular depth estimation. EP methods [30,
31] similarly avoid the need for multiple forward passes, where the
distribution of a random variable is approximated analytically through the
different transformations. We build upon the concepts of probabilistic
classification using deep features and EP to enable uncertainty quantification
for semantic segmentation in real–time on embedded hardware, which we describe
in the following section.

##  3 Real-time Uncertainty Quantification

Figure 2: Summary of the proposed model. The pink box represent the
deterministic feature extractor $f(\mathbf{x};\theta)$ that can be any
pretrained semantic segmentation network. The blue convolutional layer
represents our probabilistic layer, which allows for analytic predictive
inference, and is used to generate a mean and variance representation of the
predictive logits $\alpha$. These are then passed through the EPSoftmax layer
to represent final predictive categories $\mathbf{t}$ and epistemic
uncertainty information.

We pose the quantification of epistemic uncertainty within the Bayesian
framework, where we propagate uncertainty in the model parameters to
predictions. For this we require a posterior of our model latent variables
$\boldsymbol{\omega}$ such that,

$p(\boldsymbol{\omega}|\mathbf{X},\mathbf{Y})\propto
p(\boldsymbol{\omega})p(\mathbf{X},\mathbf{Y}|\boldsymbol{\omega})$ (1)

where $\mathbf{X}$ is the set of our training inputs and $\mathbf{Y}$ is a
matrix of our predictive labels. We can then form a predictive distribution
for new test data $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ as,

$p(\hat{y}|\hat{\mathbf{x}},\mathbf{X},\mathbf{Y})=\int
p(\boldsymbol{\omega}|\mathbf{X},\mathbf{Y})p(\hat{\mathbf{x}},\hat{\mathbf{y}}|\boldsymbol{\omega})d\boldsymbol{\omega}.$
(2)

For the case of a neural network representing our likelihood, the integrals
required for Eqns. (1) and (2) are intractable when treating all network
parameters as random variables. For the case of (1), the posterior may be
approximated by a tractable form through means such as variational inference,
though the predictive posterior in (2) for deep neural networks remains
intractable and requires expensive Monte-Carlo integration to be used.

The goal of this work is to find a simpler probabilistic representation of
model predictions for semantic segmentation that provides efficient analytic
computation, thus avoiding the need for expensive sampling approximations. To
achieve this, we propose simplifying the probabilistic component of our model
to that of linear model with respect to latent variables, where the basis
function applied to the input is a neural network $f(\cdot;\theta)$
parameterised by $\theta$ which includes all but the last layer of the neural
network. These parameters are treated as fixed and known values. We then
replace the final linear layer within a given network with a probabilistic
layer parameterised by our latent variables $\boldsymbol{\omega}$ for which we
will perform inference. This can be seen as separating the model into a
feature extraction stage with fixed parameters $\theta$, and the
classification stage with parameters treated as random variables
$\boldsymbol{\omega}$. The latent parameters in $\boldsymbol{\omega}$ will
represent the weights and bias of a final convolutional layer applied to the
model. Figure 2 illustrates the proposed model, and can be summarised as,

$\displaystyle\Phi(\mathbf{x})$ $\displaystyle=f(\mathbf{x};\theta)$ (3)
$\displaystyle\alpha$ $\displaystyle=\Phi(\mathbf{x})\boldsymbol{\omega}$ (4)
$\displaystyle\mathbf{t}$ $\displaystyle=\text{Softmax}(\alpha),$ (5)

where $\Phi(\mathbf{x})$ represents the design matrix for input $\mathbf{x}$
generated from a neural network with fixed parameters $\theta$, $\alpha$ and
$\mathbf{t}$ represents the corresponding logits and final predictive
categorical probability respectively, and $\boldsymbol{\omega}\sim
p(\boldsymbol{\omega}|\mathbf{X},\mathbf{Y},\theta)$ is the latent variables
we wish to perform inference for. We represent the multiplication between the
design matrix and the probabilistic parameters as an inner product, but note
that this inner product can be computed with an equivalent convolution
operation. Since inference is only required for the final latent variables, we
are able to leverage pretrained networks $f(\mathbf{x};\theta)$ for the
generation of design matrices.

For the work presented within, we frame inference in the logit space as
opposed to the final categorical distribution. This allows us to frame the
inference problem as a simple linear regression model, such that our posterior
of latent variables $\boldsymbol{\omega}$ with $N$ data points is,

$\displaystyle
p(\boldsymbol{\omega}|\mathbf{X},\mathbf{Y},\theta)\propto\Big{[}\prod_{i=0}^{N-1}\mathcal{N}\Big{(}\boldsymbol{\omega}|f(\mathbf{x}_{i};\theta)\boldsymbol{\omega},\sigma^{2}\Big{)}\Big{]}p(\boldsymbol{\omega}).$
(6)

With a conjugate Gaussian prior placed on latent variables
$\boldsymbol{\omega}$, our posterior will also be Gaussian [32],

$p(\boldsymbol{\omega}|\mathbf{X},\mathbf{Y},\theta)=\mathcal{N}(\mu_{\pi},\Sigma_{\pi}).$
(7)

The advantage of representing our model in this way is that it allows us to
represent predictive probabilities over the logits for a single test image
$\hat{\mathbf{X}}$ analytically as,

$\displaystyle p(\hat{\alpha}|\hat{\mathbf{x}},\mathbf{X},\mathbf{Y},\theta)$
$\displaystyle=\int\mathcal{N}\Big{(}\Phi(\hat{\mathbf{x}})\boldsymbol{\omega},\sigma^{2}\Big{)}p(\boldsymbol{\omega}|\mathbf{X},\mathbf{Y},\theta)d\boldsymbol{\omega}$
(8)
$\displaystyle=\mathcal{N}(\hat{\alpha}|\Phi(\hat{\mathbf{x}})\mu_{\pi},\sigma^{2}_{N}(\hat{\mathbf{x}}))$
(9) $\displaystyle\sigma^{2}_{N}(\hat{\mathbf{x}})$
$\displaystyle=\sigma^{2}+\hat{\mathbf{x}}^{T}\Sigma_{\pi}\hat{\mathbf{x}}$
(10)

###  3.1 Inference of Latent Variables

A challenge with this modelling scheme is that since we are performing
inference in the logit space, we cannot directly define a likelihood based on
the data, as the labels for our data is represented as final categorical
probabilites and the softmax function applied to logits to obtain this
predictive probability is not bijective. To address this, we instead propose
to approximate samples from the conditional posterior of our latent variables
$\boldsymbol{\omega}$ using the diagonal SWAG method [33].

Given a conjugate prior, we know that the posterior of our latent variables
$\boldsymbol{\omega}$ will be a Gaussian, meaning it can be fully described
using only the first two moments. To summarise these moments, we apply the
diagonal SWAG method to approximately sample from our model parameters using
SGD iterates to compute
$\boldsymbol{\omega}_{\text{SWA}}=\frac{1}{T}\sum_{i=1}^{T}\boldsymbol{\omega}_{i}$.
From this, we can compute an online empirical variance estimate for our
probabilistic parameters as
$\Sigma_{\text{diag}}=\text{diag}(\bar{\boldsymbol{\omega}}^{2}-\boldsymbol{\omega}_{\text{SWG}}^{2})$.
In this work, we differ from the original SWAG method, where instead of
computing the empirical mean from the SWAG iterates, we use the pretrained
weights for the last convolutional layer in our network
$\bar{\boldsymbol{\omega}}=\boldsymbol{\omega}_{\text{pretrained}}$. This
reduces the need to record many parameter values during training, and
encourages mean predictions from the probabilistic model to be similar to the
point estimate network. With this empirical variance parameters, we can
represent our approximate posterior over our $N$ probabilistic parameters as a
factorised Gaussian distribution,

$p(\boldsymbol{\omega}|\mathbf{X},\mathbf{Y},\theta)\approx\prod_{i=1}^{N}\mathcal{N}(\boldsymbol{\omega}_{i}|\bar{\boldsymbol{\omega}},\Sigma_{\text{diag}}).$
(11)

This allows us to perform approximate inference in the logit space by
utilising the categorical labels available for our data sets. Furthermore, the
use of a factorised approximation accelerates computation of predictive
posterior, as the covariance matrix $\Sigma_{\pi}$ in (10) becomes a diagonal
matrix, such that,

$\displaystyle\sigma^{2}_{N}(\hat{\mathbf{x}})$
$\displaystyle\approx\sigma^{2}+\hat{\mathbf{x}}^{T}\Sigma_{\text{diag}}\hat{\mathbf{x}}.$
(12)

Whilst eliminating covariance within our posterior approximation, the use of a
diagonal covariance matrix considerably reduces the number of model
parameters, allowing for easier adaption to low memory applications and
accelerate prediction on resource constrained devices.

###  3.2 Predictive Distributions and Measures of Uncertainty

Whilst providing an analytic solution to the predictive probabilities of our
logits, we ultimately wish to represent a predictive distribution for final
categorical probabilities. An exact analytical solution when using the softmax
activation is not known. We address this by building on the methods of moment
propagation used in the works of EP, where instead of computing exact
distributions, we approximate the moments of random variables after applying
certain functions, and use these moments to approximate the transformed random
variables as Gaussians. Similar to [31], we compute intermediate moments of
the softmax using properties of the Log-Normal distribution.

For a Gaussian random variable
$\gamma\sim\mathcal{N}(\mu_{\gamma},\sigma_{\gamma}^{2})$,
$\beta=\exp(\gamma)\sim\text{Lognormal}(\mu_{\beta},\sigma_{\beta}^{2})$,
where the mean and variance of $\beta$ is
$\mu_{\beta}=\exp\big{(}\mu_{\gamma}+\sigma_{\gamma}^{2}/2\big{)}$ and
$\sigma^{2}_{\beta}=\big{(}\exp{\sigma_{\gamma}^{2}}-1\big{)}\exp(2\mu_{\gamma}+\sigma_{\gamma}^{2})$
respectively. We can use these two moments to approximate the transformed
random variables as a Gaussian
$\beta\dot{\sim}\mathcal{N}(\mu_{\beta},\sigma^{2}_{\beta})$. From this we can
approximate the distribution of the output for each class as,

$t_{j}=\frac{\exp(\alpha_{j})}{\sum_{i=0}^{N-1}\exp(\alpha_{i})}=\frac{y_{j}}{\sum_{i=0}^{N-1}y_{i}}$
(13)

where $\alpha_{j}$ is a single logit from our probabilistic layer and
$y_{i}\sim\mathcal{N}(\mu_{y,i},\sigma^{2}_{y,i})$ using the properties of the
Log-Normal distribution. To find the mean and variance for our output $t_{i}$
using moment propagation, we first find the mean and variance of the
denominator. Assuming independence in our outputs, the denominator
distribution in Equation 13 can be represented as,

$\sum_{i=0}^{N-1}y_{i}\sim\mathcal{N}(\sum\mu_{y,i},\sum\sigma^{2}_{y,i})=\mathcal{N}(\mu_{d},\sigma^{2}_{d}).$
(14)

The application of moment propagation used in [31] does not aim to approximate
the moments from the ratio distribution encountered within a probabilistic
treatment of the softmax, and instead reduce the Gaussian random variable to a
Dirichlet random variable, meaning additional computation is required to
obtain class-conditional uncertainty measures. We rectify this by following
ratio distribution approximation of [34], where a Gaussian approximation is
derived from a Taylor expansion. With this we can approximate the mean and
variance of each softmax output indexed by $j$ as,

$t_{j}\dot{\sim}\mathcal{N}\Big{(}\frac{\mu_{j}}{\mu_{d}},\frac{\mu^{2}_{j}}{\mu^{2}_{d}}(\sigma^{2}_{j}+\sigma^{2}_{d})\Big{)},$
(15)

where $\mu_{j}$ and $\sigma_{j}$ are found from the Log-Normal properties. We
label the use of this moment propagation as the Expectation Propagation
Softmax (EPSoftmax).

Whilst having the ability to represent classification uncertainty conditional
on our deep feature extraction, we also wish to form a suitable categorical
distribution over outputs for classification using the conventional argmax
operator. We show how we can obtain categorical probabilities for
classification using the described approach.

######  Proposition 1.

With the probabilistic output in Eq. 15, we can create a valid $k-$dimensional
categorical distribution such that,

$C\sim\text{Cat}(k,\mathbb{E}[\mathbf{t}]).$ (16)

###### Proof.

For $\text{Cat}(k,\mathbb{E}[\mathbf{t}])$ to be a valid categorical
distribution, we require that the parameters generated by
$\mathbb{E}[\mathbf{t}]$ satisfy the condition that
$\mathbb{E}[\mathbf{t}]_{j}\leq 1$ for $0\leq j<k$ and
$\sum_{i=0}^{k-1}\mathbb{E}[\mathbf{t}]_{i}=1$. We first observe that
expectation for the $j^{th}$ component is,

$\mathbb{E}[\mathbf{t}]_{j}=\frac{\mu_{j}}{\mu_{d}}=\frac{\exp\big{(}\mu_{j}+\sigma^{2}_{j}/2\big{)}}{\sum_{i=0}^{k-1}\exp\big{(}\mu_{i}+\sigma^{2}_{i}/2\big{)}}=\frac{\exp\big{(}\mu_{j}+\sigma^{2}_{j}/2\big{)}}{\mu_{d}},$
(17)

where properties of the Lognormal distribution have been used and $\mu_{d}$ is
that of Equation 14. Similar to the traditional softmax function, the
denominator is shared amongst all components, and the exponential function
ensures all components are strictly positive. Following the same arguments of
the softmax, this implies that $\exp\big{(}\mu_{j}+\sigma^{2}_{j}/2\big{)}$
for valid index $j$, and that $\sum_{i}^{k-1}\mathbb{E}[\mathbf{t}]_{i}=1$ as
required. ∎

With this categorical representation, we can easily perform final
classification similar to point estimate networks, whilst also delivering
important uncertainty information in these predictions. In the next section,
we discuss the uncertainty metrics available.

###  3.3 Computing Predictive Uncertainty

With our representation of predictive probabilities, we want to be able to
reason about the different types of uncertainty present. It is common to refer
to the epistemic and aleatoric uncertainty [25], where epistemic uncertainty
is a representation of reducible uncertainty identified by the model, and
aleatoric uncertainty is irreducible uncertainty caused by the data present.
With the probabilistic model presented within, we are able to reason about
both forms of uncertainty.

We propose to capture epistemic uncertainty using the variance information
available in our model predictions. An advantage of our approach is that we
can measure this uncertainty in both the logit and prediction space. Given we
are modelling these spaces as Gaussians, we can succinctly summarise this
uncertainty using the entropy of these distributions. The entropy for a
D-dimensional multivariate Gaussian is,

$\mathbb{H}[x]=\frac{1}{2}\log|\Sigma|+\frac{D}{2}(1+\log 2\pi).$ (18)

We see from Eq. 18 that the entropy depends only on the covariance information
in the distribution. This is advantageous as it provides a succinct and
natural form to summarise the uncertainty induced by our latent variables in
our predictions. Furthermore, given that we are representing our distributions
over our logits and final predictions as independent Gaussian variables, the
determinant operator can be reduced to a product of the variance components
for each component in the relevant distribution.

Entropy provides a succinct summary for our uncertainty over all categories of
interest, though there are instances where we may wish to view uncertainty
information pertaining to a single class of interest. For example, for an
autonomous vehicle scenario we may be interested in observing the uncertainty
for safety critical classes such as other vehicles or pedestrians. We can
summarise the class conditional uncertainty utilising the corresponding
variance in our marginal predictive probability in Eq. 15 for classes of
interest.

It has been shown that entropy of the final categorical probability obtained
from classification models can serve as an upper-bound for aleatoric
uncertainty [35]. We build upon this insight in this work to allow us to
approximate aleatoric uncertainty $\mathcal{U}_{A}$ using the entropy
$\mathbb{H}$ of the categorical distribution represented in (16) such that,

$\mathcal{U}_{A}\approx\mathbb{H}[C]$ (19)

Using the method described here, we are able to reason about both aleatoric
uncertainty and epistemic uncertainty present within our model. We demonstrate
in the following section how we can use the described approach for real-time
semantic segmentation.

##  4 Experiments

###  4.1 Experimental Setup

With our probabilistic model, inference scheme and uncertainty measures
defined, we now demonstrate how they can all be combined to deliver
uncertainty in real-time compute constrained devices. The NVIDIA Jetson AGX
Xavier embedded device is used as the computing platform. Our aim here is to
demonstrate how the proposed uncertainty mechanism can be applied to existing
pretrained semenatic segmentation models to endow them with the capability to
compute aleatoric uncertainty measures. Code for experiments is available at
https://github.com/egstatsml/eu-seg.

input

predicted segmentation

epistemic uncertainty

aleatoric uncertainty

class uncertainty

Figure 3: Examples of predictions from the proposed model for the CityScapes
Dataset utilising the BiSeNetv1 backbone (top row) and the CamVid datasets
using the PIDNet backbone (bottom row). From left to right, the columns
represent the input, classification, epistemic uncertainty, aleatoric
uncertainty, and class conditional epistemic uncertainty. For epistemic and
aleatoric uncertainty, green regions indicate larger uncertainty, whilst red
indicates greater uncertainty for class conditional uncertainty. For class
conditional uncertainty, we show the standard deviations for the classes
“truck” and “person”. Best viewed on computer screen.

For our inference procedure, we perform training on the existing models to
obtain our diagonal SWAG samples with the Ohem cross-entropy loss [36]. We
perform a total of 5,000 SGD iterations, with a warmup of 1,000 iterations
using a linear increase of the learning rate. After this warmup period, the
learning rate remains constant. The parameters are observed every 50 SGD
iterations for the remainder of training for inference utilising diagonal
SWAG. These recorded parameters are then used to estimate the empirical
covariance matrix for the final probabilistic convolutional layer. Our prior
over our latent variables is a Gaussian distribution $\mathcal{N}(0,1\times
10^{-4})$, which is implemented using weight decay.

After training is completed, the models are then compiled to the TensorRT
format to be used on the Jetson board for calculation of inference speed
metrics. During compilation, the models are converted to half-precision
floating point values to accelerate computation. To measure predictive speed,
we time the computation required for 1,000 forward passes. Our primary
measures for evaluating model predictive performance is the mean intersection
over union (mIOU) and the Macro and Micro F1 scores. Predictive speed is
measured in frames-per-second (fps) on the Jetson device, and compared against
traditional point estimate networks.

###  4.2 Urban-Scene Datasets for Autonomous Driving

One area where real-time predictions is required is autonomous vehicles. Given
the rapid development and need for uncertainty measures in this safety
critical scenario, we perform experimentation on the CamVid [1] and CityScapes
[3] datasets where pre-trained base networks are available to form our feature
extractor $f(:,\theta)$. For the CamVid datasets, we perform experimentation
adding the proposed EP uncertainty mechanism to ENet [18] and PIDNet [23]. For
ENet models, UnMaxpooling operations in the decoder were replaced with
interpolation stages followed by a small finetuning stage to accomodate the
change. This change is required as TensorRT does not support the unpooling
operations. For CityScapes, a larger number of pre-trained models are
available, allowing us to perform experimentation using the previous models
and BiSeNetV1[21], BiSeNetv2 [22] and PPLiteSegT and PPLiteSegB [37]. We
summarise the predictive performance of these models for the CityScapes and
CamVid datasets in Tables 1 and 2 respectively, where they are also compared
against equivalent point estimate networks.

From the results in Table 1, we see comparable performance amongst the
probabilistic models and their point estimate equivalents. Whilst the
predictive speed does decrease across the Bayesian models, we see that
predictive performance remains suitable for real time application.
Interestingly, we note that the models that have shown faster predictions on
traditional hardware such as ENet and BiSeNetV2 suffer from slower than
expected predictive times. We attribute this decrease in predictive
performance on the Jetson hardware to the depth-wise convolutional operations
used in the BiSeNetv2 model and the excessive interpolation stages in ENet not
being as thoroughly optimised within the TensorRT framework. This highlights
the importance of designing bespoke architectures for edge devices.

Table 1: Summary of predictive performance of real-time semantic segmentation methods on Jetson Xavier embedded hardware for CityScapes dataset. Uncertainty enabled models are given the ”“Bayes-” prefix. Model | Macro-F1 | Micro-F1 | mIOU | fps
---|---|---|---|---
BiSeNetV1 | 0.8423 | 0.9556 | 0.7426 | 68.81
Bayes-BiSeNetV1 | 0.8415 | 0.9550 | 0.7408 | 57.359
BiSeNetV2 | 0.8473 | 0.9565 | 0.7476 | 49.502
Bayes-BiSeNetV2 | 0.8456 | 0.9558 | 0.7451 | 57.359
ENet | 0.7125 | 0.8976 | 0.5795 | 45.1638
Bayes-ENet | 0.7125 | 0.8974 | 0.5795 | 30.709
PIDNet | 0.9150 | 0.9705 | 0.8486 | 84.298
Bayes-PIDNet | 0.9129 | 0.9695 | 0.8454 | 69.367
PPLiteSegT | 0.8534 | 0.9558 | 0.7578 | 72.5234
Bayes-PPLiteSegT | 0.8481 | 0.9536 | 0.7501 | 65.931
PPLiteSegB | 0.8666 | 0.9597 | 0.7750 | 56.9437
Bayes-PPLiteSegB | 0.8603 | 0.9571 | 0.7656 | 52.022
Table 2: Summary of predictive performance of real-time semantic segmentation methods on Jetson Xavier embedded hardware for CamVid dataset. Uncertainty enabled models are given the ”“Bayes-” prefix. Model | Macro-F1 | Micro-F1 | mIOU | fps
---|---|---|---|---
ENet | 0.6932 | 0.9116 | 0.5950 | 42.2916
Bayes-ENet | 0.6702 | 0.8990 | 0.5698 | 30.825
PIDNet | 0.8683 | 0.9485 | 78.4699 | 73.7831
Bayes-PIDNet | 0.8661 | 0.9471 | 0.7816 | 59.978

With our predictive performance measured quantitatively, we now investigate
the uncertainty measures qualitatively. In Section 3.3, we state how the
proposed modelling method is capable of producing measures for aleatoric,
epistemic and class conditional epistemic uncertainty. Figure 3 illustrates
the predictive performance over CityScapes and CamVid datasets and the
relevant uncertainty measures. We can see from these figures that the measured
epistemic uncertainty from entropy in Gaussian representation of our output
(Eqn 18) is largest within the objects of interest, whilst the aleatoric
uncertainty measured from the entropy of the final categorical distribution
(Eqn 19) is concentrated around the edges of these objects. We further see
from the class conditional uncertainty measures that when targeting individual
classes, the uncertainty is targeted towards the edge of the objects for the
class of interest. We explore additional examples of the class-conditional
uncertainty measures in Figure 4 to further verify this result.

(a) Input

(b) “car” std.

(c) “vegetation” std.

(d) “road” std.

Figure 4: Visualisation of class-conditional uncertainty for a sample from
CityScapes dataset. Red regions indicate an increase in uncertainty.
Uncertainties presented as standard deviations. Predictions performed with
PIDNet.

###  4.3 Semantic Segmentation of General Objects

Robotics and human computer interaction systems are another class of practical
application where semantic segmentation methods are required to operate in
real-time on edge devices. Given the complexity of operating with humans or
the dynamic environments robotics systems encounter, it is important that
segmentation methods used within these scenarios are able to reason about
uncertainty present. We perform additional experimentation using the
challenging ADE20k [5] and CoCoStuff [2] datasets to assert the suitability of
the proposed probabilistic module for data seen within these scenarios. These
experiments build upon the available pre-trained BiSeNetV1 and BiSeNetV2
models to form $f(:,\theta)$, with results shown in Tables 3 and 4.
Visualisations of uncertainty measures is shown in Figure 5, and examples of
class conditional uncertainty in Figure 6.

input

predicted segmentation

epistemic uncertainty

aleatoric uncertainty

class uncertainty

Figure 5: Examples of predictions from the proposed model for the ADE20k Dataset (top row) and the CoCoStuff dataset (bottom row) when utilising the BiSeNetv1 backbone. From left to right, the columns represent the input, classification, epistemic uncertainty, aleatoric uncertainty, and class conditional epistemic uncertainty. For epistemic and aleatoric uncertainty, green regions indicate larger uncertainty, whilst red indicates greater uncertainty for class conditional uncertainty. For class conditional uncertainty, we show the standard deviations for the classes “building” and “dog”. Best viewed on computer screen. Table 3: Summary of predictive performance of real-time semantic segmentation methods on Jetson Xavier embedded hardware for CoCoStuff dataset. Model | Macro-F1 | Micro-F1 | mIOU | fps
---|---|---|---|---
BiSeNetV1 | 0.4254 | 0.6295 | 0.3077 | 72.4150
Bayes-BiSeNetV1 | 0.4256 | 0.6300 | 0.3079 | 43.3340
BiSeNetV2 | 0.4042 | 0.6025 | 0.2851 | 58.6345
Bayes-BiSeNetV2 | 0.4047 | 0.6027 | 0.2855 | 41.2032
Table 4: Summary of predictive performance of real-time semantic segmentation methods on Jetson Xavier embedded hardware for ADE20k dataset. Model | Macro-F1 | Micro-F1 | mIOU | fps
---|---|---|---|---
BiSeNetV1 | 0.4859 | 0.7643 | 0.3513 | 62.4800
Bayes-BiSeNetV1 | 0.4861 | 0.7642 | 0.3514 | 54.2450
BiSeNetV2 | 0.4490 | 0.7593 | 0.3211 | 59.5024
Bayes-BiSeNetV2 | 0.4494 | 0.7591 | 0.3215 | 41.8055

These results further demonstrate the ability of the proposed uncertainty
mechanism to provide comparable predictive accuracy to the corresponding
point-estimate networks on embedded hardware, whilst also providing a range of
meaningful uncertainty estimates. We see in Figure 6 that class conditional
accuracy has started to become much more diffuse, though is still concentrated
around the edges of the objects of interest. This can be attributed to the
greater complexity and diversity offered within the ADE20k and CoCoStuff
datasets, and highlights the importance of these uncertainty measures for
these challenging scenarios.

(a) Input

(b) “car” std.

(c) “dog” std.

(d) “frisbee” std.

Figure 6: Visualisation of class-conditional uncertainty for a sample from
CoCoStuff dataset. Red regions indicate an increase in uncertainty.
Uncertainty presented as standard deviations. Predictions performed with
BiSeNetV2.

##  5 Discussion and Future Research

Experimental results in Section 4 have demonstrated how the proposed
uncertainty propegation method can provide meaningful uncertainty estimates
when included with a variety of existing real-time segmentation networks. From
these results we highlight areas for future research and how to further
enhance the ability to capture uncertainty within real-time semantic
segmentation models.

The proposed approach builds upon existing segmentation models to enable them
to capture uncertainty present within parameters in the classification layer
and propegate these uncertainties to meaningful predictive measurements. Since
the incorporation of the proposed uncertainty mechanism is included post-
training of the feature extractor $f(;,\theta)$, any uncertainty present
during training of the base network is not explicitly captured. Recent methods
have proposed training mechanisms to fit semantic-segmentation models that
incorporate aleatoric uncertainty into the training procedure [38, 39, 40].
Incorporation of these training schemes with the proposed uncertainty
propegation module could allow meaningful epistemic uncertainty estimates to
be found whilst encouraging the base network to have a more accurate
representation of aleatoric uncertainty present for resource constrained
hardware.

Whilst the vast majority of work on modelling uncertainty within deep-learning
has focused on finding predictive uncertainty estimates, there has been
relatively little research on how best to utilise these measures in practice
despite the existence of a rich and mature theory to address these important
challenges[41, 42]. Given the rising prevalence of semantic segmentaion
systems to safety critical environments such as autonomous vehicles, medical
imaging or human-computer interaction, it is crucial that sensible and safe
decisions are made by the machine learning system. Optimal and safe decisions
require the incorporation of meaningful uncertainty information. The
sensitivity to context of different application poses further challenges
associated with optimal and safe decision making for automated systems. Given
the need to process and interpret uncertainty information present, the
additional processing of this information will incur a computational overhead.
This computational burden is especially important for real-time embedded
systems, and we highlight as an important area for future research in
practical uncertainty aware semantic segmentation systems.

##  6 Conclusion

Within this research, we targeted the need for meaningful uncertainty
information for semantic segmentation on resource constrained hardware. We
proposed a combination of a deterministic feature extractor with a
probabilistic regression module, that can be combined with an EP softmax
module to generate final predictive outputs and uncertainties. We demonstrate
how the proposed probabilistic module can be included with existing pre-
trained networks. Evaluation of these models on embedded hardware using
multiple datasets demonstrate how the proposed probabilistic scheme can
mitigate the expensive compute traditionally required for a complete
probabilistic treatment of deep segmentation models to provide real-time
performance on resource constrained hardware. Qualitative evaluation of
obtained uncertainty measures demonstrate how the different forms of
uncertainty obtained can be used to identify different regions of interest.

## References

  * [1] Gabriel J Brostow, Julien Fauqueur, and Roberto Cipolla,  “Semantic object classes in video: A high-definition ground truth database,”  Pattern Recognition Letters, vol. 30, no. 2, pp. 88–97, 2009.
  * [2] Holger Caesar, Jasper Uijlings, and Vittorio Ferrari,  “Coco-stuff: Thing and stuff classes in context,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [3] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele,  “The cityscapes dataset for semantic urban scene understanding,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 3213–3223.
  * [4] Andres Milioto, Philipp Lottes, and Cyrill Stachniss,  “Real-time semantic segmentation of crop and weed for precision agriculture robots leveraging background knowledge in cnns,”  in 2018 IEEE international conference on robotics and automation (ICRA). IEEE, 2018, pp. 2229–2235.
  * [5] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba,  “Scene parsing through ade20k dataset,”  in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
  * [6] Jishnu Mukhoti and Yarin Gal,  “Evaluating bayesian deep learning methods for semantic segmentation,”  arXiv preprint arXiv:1811.12709, 2018.
  * [7] Clément Dechesne, Pierre Lassalle, and Sébastien Lefèvre,  “Bayesian u-net: Estimating uncertainty in semantic segmentation of earth observation images,”  Remote Sensing, vol. 13, no. 19, 2021.
  * [8] Michael Kampffmeyer, Arnt-Borre Salberg, and Robert Jenssen,  “Semantic segmentation of small objects and modeling of uncertainty in urban remote sensing images using deep convolutional neural networks,”  in Proceedings of the IEEE conference on computer vision and pattern recognition workshops, 2016, pp. 1–9.
  * [9] Prabhu Teja Sivaprasad and Francois Fleuret,  “Uncertainty reduction for model adaptation in semantic segmentation,”  in 2021 Ieee/Cvf Conference On Computer Vision And Pattern Recognition, Cvpr 2021. IEEE, 2021, number CONF, pp. 9608–9618.
  * [10] Zhedong Zheng and Yi Yang,  “Rectifying pseudo label learning via uncertainty estimation for domain adaptive semantic segmentation,”  International Journal of Computer Vision, vol. 129, no. 4, pp. 1106–1120, 2021.
  * [11] Andrew Gordon Wilson, Zhiting Hu, Ruslan Salakhutdinov, and Eric P Xing,  “Deep kernel learning,”  in Artificial intelligence and statistics. PMLR, 2016, pp. 370–378.
  * [12] Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams,  “Scalable bayesian optimization using deep neural networks,”  in International conference on machine learning. PMLR, 2015, pp. 2171–2180.
  * [13] Zhe Chen, Yuchen Duan, Wenhai Wang, Junjun He, Tong Lu, Jifeng Dai, and Yu Qiao,  “Vision transformer adapter for dense predictions,”  arXiv preprint arXiv:2205.08534, 2022.
  * [14] Yuhui Yuan, Xiaokang Chen, Xilin Chen, and Jingdong Wang,  “Segmentation transformer: Object-contextual representations for semantic segmentation,”  2020\.
  * [15] Wenhai Wang, Jifeng Dai, Zhe Chen, Zhenhang Huang, Zhiqi Li, Xizhou Zhu, Xiaowei Hu, Tong Lu, Lewei Lu, Hongsheng Li, et al.,  “Internimage: Exploring large-scale vision foundation models with deformable convolutions,”  arXiv preprint arXiv:2211.05778, 2022.
  * [16] Jun Fu, Jing Liu, Jie Jiang, Yong Li, Yongjun Bao, and Hanqing Lu,  “Scene segmentation with dual relation-aware attention network,”  IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 6, pp. 2547–2560, 2020.
  * [17] Jonathan Long, Evan Shelhamer, and Trevor Darrell,  “Fully convolutional networks for semantic segmentation,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2015, pp. 3431–3440.
  * [18] Adam Paszke, Abhishek Chaurasia, Sangpil Kim, and Eugenio Culurciello,  “Enet: A deep neural network architecture for real-time semantic segmentation,”  arXiv preprint arXiv:1606.02147, 2016.
  * [19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * [20] Haochen Wang, Xiaolong Jiang, Haibing Ren, Yao Hu, and Song Bai,  “Swiftnet: Real-time video object segmentation,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 1296–1305.
  * [21] Changqian Yu, Jingbo Wang, Chao Peng, Changxin Gao, Gang Yu, and Nong Sang,  “Bisenet: Bilateral segmentation network for real-time semantic segmentation,”  CoRR, 2018.
  * [22] Changqian Yu, Changxin Gao, Jingbo Wang, Gang Yu, Chunhua Shen, and Nong Sang,  “Bisenet v2: Bilateral network with guided aggregation for real-time semantic segmentation,”  CoRR, 2020.
  * [23] Jiacong Xu, Zixiang Xiong, and Shankar P Bhattacharyya,  “Pidnet: A real-time semantic segmentation network inspired from pid controller,”  arXiv preprint arXiv:2206.02066, 2022.
  * [24] Alex Kendall, Vijay Badrinarayanan, and Roberto Cipolla,  “Bayesian segnet: Model uncertainty in deep convolutional encoder-decoder architectures for scene understanding,”  in British Machine Vision Conference 2017, BMVC 2017, London, UK, September 4-7, 2017. 2017, BMVA Press.
  * [25] Alex Kendall and Yarin Gal,  “What uncertainties do we need in bayesian deep learning for computer vision?,”  Advances in neural information processing systems, vol. 30, 2017\.
  * [26] Joost Van Amersfoort, Lewis Smith, Yee Whye Teh, and Yarin Gal,  “Uncertainty estimation using a single deep deterministic neural network,”  in International conference on machine learning. PMLR, 2020, pp. 9690–9700.
  * [27] Jishnu Mukhoti, Joost van Amersfoort, Philip HS Torr, and Yarin Gal,  “Deep deterministic uncertainty for semantic segmentation,”  arXiv preprint arXiv:2111.00079, 2021.
  * [28] Po-Yu Huang, Wan-Ting Hsu, Chun-Yueh Chiu, Ting-Fan Wu, and Min Sun,  “Efficient uncertainty estimation for semantic segmentation in videos,”  in Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 520–535.
  * [29] Chao Qu, Wenxin Liu, and Camillo J Taylor,  “Bayesian deep basis fitting for depth completion with uncertainty,”  in Proceedings of the IEEE/CVF international conference on computer vision, 2021, pp. 16147–16157.
  * [30] Brendan J Frey and Geoffrey E Hinton,  “Variational learning in nonlinear gaussian belief networks,”  Neural Computation, vol. 11, no. 1, pp. 193–213, 1999.
  * [31] Jochen Gast and Stefan Roth,  “Lightweight probabilistic deep networks,”  CoRR, 2018.
  * [32] kevin Murphey,  Machine learning, a probabilistic perspective,  MIT Press, Cambridge, MA, 2012.
  * [33] Wesley J. Maddox, Pavel Izmailov, Timur Garipov, Dmitry P. Vetrov, and Andrew Gordon Wilson,  “A simple baseline for bayesian uncertainty in deep learning,”  in Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, Eds., 2019, pp. 13132–13143.
  * [34] Eloísa Díaz-Francés and Francisco J Rubio,  “On the existence of a normal approximation to the distribution of the ratio of two independent normal random variables,”  Statistical Papers, vol. 54, no. 2, pp. 309–323, 2013.
  * [35] Lewis Smith and Yarin Gal,  “Understanding measures of uncertainty for adversarial example detection,”  in Uncertainty in AI, 2018.
  * [36] Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick,  “Training region-based object detectors with online hard example mining,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 761–769.
  * [37] Juncai Peng, Yi Liu, Shiyu Tang, Yuying Hao, Lutao Chu, Guowei Chen, Zewu Wu, Zeyu Chen, Zhiliang Yu, Yuning Du, et al.,  “Pp-liteseg: A superior real-time semantic segmentation model,”  arXiv preprint arXiv:2204.02681, 2022.
  * [38] Francois Fleuret et al.,  “Uncertainty reduction for model adaptation in semantic segmentation,”  in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 9613–9623.
  * [39] Yuxi Wang, Junran Peng, and ZhaoXiang Zhang,  “Uncertainty-aware pseudo label refinery for domain adaptive semantic segmentation,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 9092–9101.
  * [40] Qianyu Zhou, Zhengyang Feng, Qiqi Gu, Guangliang Cheng, Xuequan Lu, Jianping Shi, and Lizhuang Ma,  “Uncertainty-aware consistency regularization for cross-domain semantic segmentation,”  Computer Vision and Image Understanding, vol. 221, pp. 103448, 2022\.
  * [41] Morris H DeGroot,  Optimal statistical decisions,  John Wiley & Sons, 2005.
  * [42] Mykel J Kochenderfer, Tim A Wheeler, and Kyle H Wray,  Algorithms for decision making,  MIT press, 2022.


# Quantum Advantage on Proof of Work

Dan A. Bard<EMAIL_ADDRESS>Joseph J. Kearney<EMAIL_ADDRESS>Carlos A.
Perez-Delgado<EMAIL_ADDRESS>School of Computing, University of Kent,
Canterbury, Kent CT2 7NF United Kingdom

###### Abstract

Proof-of-Work (PoW) is a fundamental underlying technology behind most major
blockchain cryptocurrencies. It has been previously pointed out that quantum
devices provide a computational advantage in performing PoW in the context of
Bitcoin. Here we make the case that this quantum advantage extends not only to
all existing PoW mechanisms, but to any possible PoW as well. This has strong
consequences regarding both quantum-based attacks on the integrity of the
entirety of the blockchain, as well as more legitimate uses of quantum
computation for the purpose of mining Bitcoin and other cryptocurrencies. For
the first case, we estimate when these quantum attacks will become feasible,
for various cryptocurrencies, and discuss the impact of such attacks. For the
latter, we derive a precise formula to calculate the economic incentive for
switching to quantum-based cryptocurrency miners. Using this formula, we
analyze several test scenarios, and conclude that investing in quantum
hardware for cryptocurrency mining has the potential to pay off immensely.

##  I Introduction

Blockchain systems have become an integral part of modern financial society
with their use reaching beyond the storage of value and cryptocurrencies into
the wider financial market crosby2016blockchain . One of the core tenets of
these systems is that decisions about what data is immutably written to the
blockchain’s ledger, and therefore what is made a permanent entry on the
chain’s state going forwards, is made by consensus between nodes connected to
and storing the ledger’s information.

Although, consensus can be achieved utilizing several different methods
8400278 , Proof of Work (PoW) powered blockchains currently account for more
than 90% of the current market share anand2016colored  and include some of the
largest cryptocurrencies such as Bitcoin and Ethereum. These two blockchains
alone account for a market cap of over US$430 billion (approximate as of
December 2020) CoinMarketCap . This demonstrates that considerable financial
assets are stored and maintained by blockchains, their transactions and
therefore the underlying consensus algorithms.

In this paper we focus on the PoW mechanisms of blockchains. We show that
quantum computers give a quadratic advantage in PoW efficiency; not just for
all existing protocols but for any possible PoW protocol that relies on
computational work being done.

Unlike many other cryptographic standards, blockchain systems intrinsically
tie the protected asset (the ledger) with the encryption systems used. It has
been previously shown that this makes blockchains particularly vulnerable to
quantum attacks kearney ; aggarwal2017quantum . The main concern is that
replacing the cryptographic protocols that build a blockchain with ‘post-
quantum’ ones is extremely more difficult than with more traditional
cryptographic uses kearney ; aggarwal2017quantum . Several predicted timelines
van2013blueprint ; mosca  pin the year 2035 as when we can expect quantum
computers to reliably be able to break current mainstream cryptographic
protocols such as RSA2048 and ECDSA. These two key facts make these concerns
timely and pressing.

Within most blockchain technologies, PoW underpins the protocols’ consensus
algorithm and because the consensus algorithm determines which transactions
and actions performed on the network are integrated into the chain. This gives
a quantum actor a potentially much stronger ability to control the decision-
making in the blockchain. From a cybersecurity perspective, when one actor (or
group of actors) can reliably force all decisions in the blockchain, it is
called a ‘51%’ attack ye2018analysis . In the first part of this paper, we
will describe how quantum actors can much more reliably, and with much fewer
resources than any classical counterpart, perform ‘51%’ attacks.

In the second part of this paper, we will consider a much less sinister, and
much more profitable, use of quantum resources. Given the quadratic increase
in PoW efficiency, one may consider using a quantum computer to _‘mine’_
Bitcoin or some other cryptocurrency (_mining_ is the act of performing PoW in
order to help the blockchain arrive at a consensus). Performing this task
generally involves economic remuneration to the _‘miner’_. A quantum
cryptocurrency miner can potentially require fewer clock cycles, a lot less
energy, and dissipate a lot less heat, in order to mine the same amount of
cryptocurrency as a classical computer counterpart. Whether this makes the
endeavor profitable, of course, will depend on both the initial cost, and
operating costs of such a quantum device. We explore these questions in
Section IV.

First, however, in the following section, we will discuss PoW as it is
understood today, in more technical and formal detail. Then, in Section III,
we summarize the quantum technologies that can be deployed for PoW, and the
advantages in doing so. Finally, we conclude with a summary of results, and a
discussion on the future outlook for PoW.

##  II Proof of Work

Consensus algorithms within blockchain technologies are critical to the
running of the protocol and PoW is the most commonly utilized mechanism. It is
used to ensure miners act honestly according to the rules of the blockchain
protocol antonopoulos2014mastering . It was adapted as a mechanism for
consensus across a blockchain by Satoshi Nakamoto nakamoto2019bitcoin ;
back2002hashcash . PoW is widely used partly due to the utilization of
Bitcoin’s technologies and code base within a large amount of subsequent
projects, but also because it is a highly secure mechanism for ensuring the
good nature of mining nodes and because it lends itself well to distributed
networks.

Blockchain consensus employs the concept of the longest chain. The longest
chain is typically the valid chain that a majority of the network holds as the
state of the blockchain. While a miner can create a malicious block and add it
to the network trivially, it will not be accepted by a majority of the nodes,
as other peers on the network will reject the block and choose an alternate
proposed block, therefore, excluding the malicious block from the longest
chain. If a malicious user controls a majority of the network’s computational
power, they could potentially overwhelm this consensus mechanism by adding
blocks to the chain faster than the rest of the network can compete, meaning
they consistently have the longest chain. This means that the user could gain
overall control of what is included into each block. This is known as a ‘51%’
attack and is the most damaging threat to a blockchain’s integrity.

In PoW-based systems a user proposing a new block must perform a
computationally-intensive task. The successful completion of this task must be
easily verified by other users on the network. Miners must expend a non-
trivial amount of resources—usually computational _work_ and its associated
costs, such as electricity and heat. This incurs a sunk cost for the miner
that will be lost if the block they present is malicious or malformed.

The Bitcoin PoW algorithm employs a NP-Complete problem where the goal is to
create a hash digest based on a given input string ren2019analysis . This hash
digest is required to be in a specific form. This form is dictated by a target
value (some integer in the range $[0,2^{256}]$) and Bitcoin miners must
compute the hash digest that has an equal to or smaller value than the target.
The target value is determined by the difficulty value of the blockchain
network, which is altered depending on the computational power on the network
as a whole as determined by the network’s current _hash-rate_ (leading to the
final target value being in the range of $[0,(2^{256}-difficulty)]$). Within
Bitcoin, the difficulty value is changed according to the current
computational power on the network once every 2016
blocksantonopoulos2014mastering  in order to maintain a block time of
approximately 10 minutes. While this example is taken from Bitcoin, this is
applicable to any network which utilizes PoW.

The hash is calculated using the block header, which is constant for a
specific block, and a nonce, which is changed repeatedly by the miner, to
create different hash digests in the hope of finding a digest that fits the
requirements for the block. As noted earlier, this problem is NP-Complete. The
best known classical algorithms for solving PoW scale exponentially to the
size of the difficulty (which in turn is bounded by the size of the hash
itself).

It is important to note that while hash-based PoW uses a NP-Complete problem,
this does not necessarily have to be the case. It _must_ be the case, however,
that the miner expend a non-trivial amount of work, and that this expenditure
can be verified by other users of the blockchain in a relatively trivial
manner. In other words, let $TC_{V}$ be the time complexity for verification
and $TC_{S}$ be the time complexity for the miner to solve the problem. Then,
any PoW mechanism must guarantee that:

$TC_{V}\ll TC_{S}.$ (1)

Clearly, any NP-Complete problem will satisfy the equation above. More
generally, however, any PoW algorithm must satisfy the following requirements:

######  Definition (Proof of Work).

A computational problem can be considered as a PoW problem if it satisfies the
following two requirements

  1. 1.

The computational complexity of the problem must satisfy Eq. 1,

  2. 2.

The difficulty of the problem must be easily _tuneable_ with a parameter.

Requirement 1 has been explained above. Requirement 2 is an important
requirement for the continued health of the blockchain network over time. As
the computational power of miners increases, this parameter needs to be re-
tuned to keep PoW as a meaningful deterrent against rogue miners.

In the following section we will explore the quantum computational advantage
in PoW as described here. We will then explore the cybersecurity threat of
quantum attacks on blockchain networks. Finally, we will analyze the
possibility, and possible profit, of using this quantum advantage for the more
benign purpose of more efficient cryptocurrency mining.

##  III Quantum Advantage for PoW

When discussing quantum advantage for computational tasks, two main types of
algorithms are most often cited. The first is the subgroup-finding algorithms
based on Shor’s seminal workshor1994algorithms . These types of algorithm
provide a exponential advantage on problems including factoring and discrete
logarithm. Though this is only a relatively small set of problems, it covers a
large area of the cryptographic landscape. The other type are the quantum
search algorithms based on Grover’s algorithmgrover1996fast ; GroverOptical .
Whilst quantum search algorithms provide a more modest quadratic advantage
over classical, their very broad applicability makes them extremely versatile,
and central to our discussion.

The quantum search algorithm, as its name suggests, allows one to search _any_
(including unsorted and unstructured) data-set $S$, of cardinality $N=|S|$ for
certain items that fulfill some condition, or is an element of some subset
$C\subseteq S$. This condition is specified, in the quantum algorithm, as a
black box or oracle $O$ that takes as input one register containing an element
of $x\in S$, and an ancilla qubit, which is set to $1$ if $x\in C$ and $0$
otherwise. The importance of this algorithm is that it runs in _total time_
$O(\sqrt{N})$, and makes $O(\sqrt{N})$ queries to $O$. This oracle can be, and
in practical uses often is, replaced by a quantum circuit or subroutine
program $a$ that computes whether $x$ satisfies the required condition, or is
an element, of the subset $C$.

In particular, one may consider a decision problem $D$ that is NP-Complete.
Let $I$ be its input set, and $S\subseteq I$ the solution set. Given that the
problem is in NP, there exists an efficient (polynomial-time) algorithm $a$
that can compute, on input $x$, whether $x\in S$. This in turn implies that a
quantum search algorithm can solve $D$ in total time
$O(\sqrt{N})=O(\sqrt{2^{n}})$, where $n$ is the input size in bits. Because
$D$ is NP-Hard, there is _no_ (known) classical algorithm that can solve $D$
in time substantially better than $O(2^{n})$.

It should be now clear why the quantum search algorithm is of central
importance to any discussion of quantum advantage for PoW. As discussed
previously, most PoW systems today require the miner to find a SHA-x hash for
a pre-determined string, that is under a certain value. This problem is NP-
Complete. Hence, a quantum computer with a memory register large enough to run
Grover’s algorithm on the necessary hash size, would be able to gain a
quadratic advantage over any classical device—including purpose-built ASICs.

To illustrate this, we can consider a toy example in which a classical brute-
force search algorithm which runs in time precisely $2^{n}$, and a quantum
search one that runs in precisely time $\sqrt{2^{n}}$. On input size $n=2$,
the quantum algorithm is only twice as fast as the classical one. On input
size $n=256$ the quantum algorithm will run $3.4\times 10^{38}$ times faster.
Compare this to ASIC chips that typically provide a speed-factor advantage of
approximately $1\times 10^{4}$.

We can also perform a more realistic analysis. Running a quantum search
algorithm (assuming no error correction) on SHA-256 hashes requires roughly
512 qubits. Estimates by major quantum computer manufacturer predict such
quantum computers will be available in 2023gambetta_2020 . At today’s reported
quantum computer clock-speedsarute_et_al._2019  (barring any major
improvements) we can thus expect the equivalent of $4\times 10^{7}$
calculations performed per second which, using Grover’s algorithm, leads to
the equivalent of $1.6\times 10^{15}$ hashes computed per second (H/s).

Fig. 1 plots the Bitcoin network hash rate using the most current value of
$130\times 10^{18}H/s$BitcoinHashRate  against a quantum computing technology
that starts at 40 MHzgambetta_2020 , and both increasing over time at the same
rate, as dictated by Moore’s Law. This gives an estimated timeframe of
approximately 27 years until a _single_ quantum computer will be capable of
completely out-mining the rest of the network, and hence be able to take over
complete control of it (a successful $51\%$ attack).

Figure 1: Bitcoin network hash rate _vs._ single quantum computer. The graph
shows the hash rate growth over time of the entirety of the Bitcoin network,
compared to that of a _single_ quantum computer. Future data-points are
extrapolated from current hash-rates, and assumes growth-rates for both
quantum and classical technologies in line with current Moore’s Law trends.
See the main text for further details.

This prediction, however, is perhaps overly conservative for a couple of
reasons. The first is that we consider the speed-increase in clock-rate for
both quantum computers and classical computers to be the same. In reality,
classical computers are known to be at the tail-end of Moore’s
Law’smoore1965cramming  logistic-curve rate-of-growthshalf2020future .
Meanwhile, we can expect quantum computers, which are in their infancy, to
over-achieve this rate-of-growthghose_2019 .

Furthermore, this comparison has been made on the Bitcoin network, which has,
by far, the largest hashing power of all blockchains coinmetrics_2020 . Other
comparatively smaller blockchain networks would be vulnerable far sooner than
suggested here. For example, if network hash rates of blockchains such as
Monero (1.28 Giga-Hashes per Second ($GH/s$))klemens_2020  or Ethereum Classic
(6.43 Tera-Hashes per Second ($TH/s$))ethereumclassichashratechart  do not
improve in the coming years, we could expect them to be vulnerable to a
quantum 51% attack as soon as there is a quantum computer with sufficient
quantum memory, which is predicted to happen roughly in 2023gambetta_2020 .

In short, not only do quantum computers provide an _asymptotic quadratic_
efficiency increase for current PoW systems, they do so for any likely
possible PoW system as well. Compare this to custom-built ASIC chips which
also provide a speed increase in mining crypto-currencies, but are however
limited to constant-factor speed-increases. This results in a single quantum
computer being able to launch devastating attacks on the cryptocurrency
network, in the foreseeable future.

Of course, this _‘single quantum computer’_ attack would only work against a
cryptocurrency network that is, at least for the most part, composed of
classical miners. If a sizable portion of a cryptocurrency’s miners were to
move to quantum hardware, this would protect the entire network from quantum
51% attacks. In the next section we explore legitimate uses of quantum
technology for PoW-based cryptocurrency mining. As we shall see, there may
also be definite profit motives for individual cryptocurrency miners to invest
in and adopt quantum technologies.

##  IV The Profitability of Quantum Cryptocurrency Mining

In previous sections we studied the cybersecurity threat posed by quantum-led
51% attacks on blockchain networks. These attacks, while largely inevitable,
are time-wise a bit far off—at least for the larger cryptocurrencies such as
Bitcoin. The reason for this is that for a successful attack a quantum
computer must have as much (or more) PoW computational power as the rest of
the network combined.

Here, we will study the viability of using a quantum computer for the purpose
of legitimately mining a cryptocurrency such as Bitcoin. In order to do _this_
effectively and profitably, a quantum computer doesn’t have to be more
powerful than the whole network, it only needs to be more efficient (in terms
of resource-cost per block approved by the network) than a single classical
miner. Hence, we can expect quantum supremacy, in the field of cryptocurrency
mining, to be achieved much sooner than the previously discussed dates given
for 51% quantum attack viability.

We will first set out to derive a general equation that can be used to
calculate the potential profitability of quantum-assisted cryptocurrency
mining. We will then apply this equation to various credible scenarios, and
give estimates of near-future profitability.

###  IV.1 Profitability Calculation

In this section we will be setting out an equation to calculate whether mining
on a classical or a quantum entity is more profitable. The primary element to
be considered when making this calculation is the income from any device
mining blocks on a blockchain. This is based on the probability of mining a
block during the time it takes for a new block to be generated. This exact
value varies among blockchains with a new block being generated on average
every 600 seconds within Bitcoin project_2009  and approximately every 15
seconds within Ethereum io_2015 . However, this value can be generalized,
since the relation between block generation and the probability of mining a
specific block will be the same across all PoW based blockchains. This block
time is controlled by the difficulty of a particular blockchain in relation to
the hash size in bits defined by the blockchain’s architecture
garay2015bitcoin . This is changed periodically in order to maintain a
consistent block time and so, across a larger timescale, the time taken to
generate a new block can be averaged dependent on blockchain. Based on these
values and the given hash rate of any considered classical miner, we can say
that the probability of mining a block is defined as:

$P_{C}=\frac{H_{C}t}{\frac{\eta D}{t}}$ (2)

Where $P_{C}$ is the probability of mining a block from a classical device,
$H_{C}$ is the hash rate of the classical device, $t$ is the block time, $D$
is the difficulty of the blockchain network and $\eta$ is the hash size.

The denominator of 2 is the calculation for the total network hash rate of any
one network. This can then be simplified to:

$P_{C}=\frac{H_{C}t^{2}}{\eta D},$ (3)

as derived from the hash rate of any one device divided by the total network
hash rate BitcoinHashRate . As discussed in Sections II and III, as blockchain
technologies utilize NP-Hard problems for PoW and as $D$ determines the
complexity of said problems, $D$ is the value where the quadratic increase in
efficiency can be applied. Due to this advantage the probability of mining a
block on any quantum device based on a given equivalent hash rate can then be
defined as:

$P_{Q}=\frac{H_{Q}t^{2}}{\eta\sqrt{D}}$ (4)

Where $P_{Q}$ is the probability of mining a block from a quantum device and
$H_{Q}$ is the equivalent hash rate of that device.

These probabilities, when taken across any given operational timespan can then
be used to calculate the overall income across said timespan for any given
blockchain, taking into account a conversion into fiat currency, defined as a
function $f$. As the exact conversion between cryptocurrencies and real world
fiat currency can vary, this has been abstracted to a single function. The
exact reward gained per block mined is another element which varies based on
the cryptocurrency being considered and duration of the operating period. When
performing the profitability calculations, this needs to be taken into careful
consideration as, for some cryptocurrencies, the block reward can change
across the lifespan of any particular cryptocurrency. For example, Bitcoin
halves its block reward every 210,000 blocks, meaning that though it
originally rewarded 50 bitcoins (BTC) per block mined meynkhard2019fair , the
current value is 6.25 BTC. The reward is expected to approach 0 by
approximately 2140 controlled_supply .

Taking these elements into account, the total income over the given timespan
can be calculated as the following for classical miners:

$I_{C}=f\left(\frac{T}{t}\cdot P_{C}B\right),$ (5)

where $I_{C}$ is the income for a classical miner across the timespan $T$, and
$B$ is the block reward for the considered blockchain. The following holds for
quantum miners:

$I_{Q}=f\left(\frac{T}{t}\cdot P_{Q}B\right),$ (6)

where $I_{Q}$ is the income for a quantum miner across $T$.

Following this, we can bring in the initial cost of any particular device in
order to calculate the point at which the given device becomes profitable
whilst operating on the network across $T$. Once this value becomes greater
than 0, it is then deemed to be profitable to run the miner on the blockchain
network. As discussed in Section II, miners are required to expend energy (in
the form of computation) to ensure honesty between parties. This is considered
here as the operational costs of any given device. From this, the profit
returns for classical miners can be determined as:

$R_{C}=I_{C}-(T\cdot O_{C})-S_{C},$ (7)

where $R_{C}$ is the profit, $O_{C}$ is the operating costs and $S_{C}$ is the
setup costs for the classical device. The profit calculation for quantum
miners is as follows:

$R_{Q}=I_{Q}-(T\cdot O_{Q})-S_{Q},$ (8)

where $R_{Q}$ is the profit, $O_{Q}$ is the operating costs and $S_{Q}$ is the
setup costs for the quantum device.

From these two equations, we can then calculate a profit ratio ($G$):

$G=\frac{R_{C}}{R_{Q}}.$ (9)

The above equation is particularly important: $G=1$ is the inflection point at
which quantum and classical technologies are equally feasible. Values of $G$
less than 1 imply that the quantum miner in question is more profitable than a
classical one, even after factoring in initial investment costs considered in
the calculation.

Eq. 9 can be expanded, using the previous equations, to:

$G=\frac{f\left(T\cdot\frac{H_{C}t}{\eta D}\cdot B\right)-(T\cdot
O_{C})-S_{C}}{f\left(T\cdot\frac{H_{Q}t}{\eta\sqrt{D}}\cdot B\right)-(T\cdot
O_{Q})-S_{Q}}$ (10)

The above equation has many practical uses. For one, it allows one to _‘plug
in’_ various known values, like research and development and other initial
investments necessary to jump-start a quantum crypto-currency mining
operation, along with running costs for both classical and quantum mining, and
decide whether the investment in quantum mining can pay off. It can also be
used—as we do below—to estimate the timescales at which quantum cryptocurrency
mining can become a profitable enterprise.

An important fact to emphasize is that Eq. 9 takes into account the
introduction of further quantum computing machines onto the network. This is
because difficulty is defined at the protocol level of a blockchain as a
mechanism to ensure that the block time stays within certain bounds. For
example the Bitcoin blockchain’s difficulty operates so that over a period of
time, if the block time exceeds or is less than 10 minutes, the difficulty of
the PoW problem is corrected to bring the block time back in line with the
pre-defined desirable time. This means that the introduction of quantum
computers onto the network will in fact decrease the block time as they have a
quadratic advantage over their classical peers. The Bitcoin protocol will
thereby increase the difficulty of the PoW algorithm. This is then taken into
account within our equation. Introduction of quantum computers into the mining
ecosystem could potentially cause a dramatic increase in the difficulty. This
means that the equation presented here will take into account new quantum
computers mining the network as their inclusion will factor into difficulty.

The above is important for various reasons, but of particular import is the
_first mover vs. second mover advantages._ Being a first mover, that is, being
the first to enter a market (in this case with a quantum miner) has definite
advantages and is of particular interest to entrepreneurs and investors. A
common concern among potential investors is that of making a large investment,
only to arrive _late_ to a market, potentially ruining return-on-investment
prospects. As we shall discuss in the last section of this paper, quantum
mining has the peculiar property that the more quantum mining _‘competitors’_
one has, however, the more profitable it may become for one to do quantum
mining.

###  IV.2 Scenarios and Forecasts

Using the equation derived earlier, we can analyze some possible near-future
scenarios. The general goal will be to determine the profitability of quantum-
based cryptocurrency mining. The cryptocurrency which shall be used for this
investigation will be Bitcoin as this is currently the blockchain with the
highest comparative market valueCoinMarketCap . This shall be performed
utilizing the denominator of Eq. 10 which can be formalized with the target as
such:

$f\left(T\cdot\frac{H_{Q}t}{\eta\sqrt{D}}\cdot B\right)-(T\cdot
O_{Q})-S_{Q}\leq 1$ (11)

For our case-analysis scenario, let us consider using a cloud quantum
computing service. IBMibmquantumexperience , amongst others, have announced
for-profit cloud-based quantum computing services. This is a natural scenario
to consider since most quantum computation in the near future is likely to
involve cloud-based servicesdevitt2016performing ; castelvecchi2017ibm . This
scenario has a composite advantage as well: it obviates the need for an
initial investment, requiring instead only that the potential miner pay the
rolling costs of renting quantum CPU time from the cloud provider. It will
allow us, within this analysis, to set $S_{Q}=0$.

Next, let us consider a time-frame. According to the roadmap set out by IBM, a
quantum computer which can run a quantum search algorithm on Bitcoin’s hashing
function can be expected by roughly 2023gambetta_2020 . To be conservative, we
consider 2025 to be an estimated ‘year zero’ in which a quantum computer can
run a quantum search on hash-based PoW and so 01/01/2025 shall be used
whenever a given date is required.

For our case scenario we are focusing on Bitcoin. This sets some further
variables in our equation. These are $t=600s$,
$\eta=2^{32}$antonopoulos2014mastering ; nakamoto2019bitcoin  and
$B=3.125BTC$meynkhard2019fair ; buybitcoinworldwide . As an additional part of
the blockchain architecture, the difficulty is calculated and adjusted every
210,000 blocks in order for the block period to remain relatively constant. To
provide a difficulty for this scenario, we plotted the historical difficulties
and then the appropriate difficulty was extrapolated to our given date using
polynomial curve of best fit. This provided a difficulty of $D=4.2903\times
10^{18}$. Though there are varying opinions of the future of Bitcoin
difficultykraft2016difficulty , this matches the current trends.

The value of Bitcoin has had a general increasing trend year-on-year, however
due to the volatile nature of cryptocurrencies, no single prediction can be
made. Therefore the values shown in table 1 will account for various BTC to
USD conversion rates including the current price (as of 17/12/2020 this is
$23,536.12)CoinMarketCap , the average price over the last 12 months (taken as
the average closing price from 01/01/2020 until 17/12/2020, $10,385.49), a
predicted conservative price ($31,000) and a predicted high-end price
($100,000).

The final element of the equation to be assigned is the hash rate equivalent
of the quantum computer. How the hashing power will increase as the
development of quantum computers continues is not known. Thus, we consider two
possibilities. In the first scenario, we take the clock-speed of (one of)
Google’s current quantum computers of $H_{Q}=40MHz/s$arute_et_al._2019 , and
keep that value constant throughout time. In the second, more plausible,
scenario we increase the quantum computer’s clock-speed according to Moore’s
Law. After four doubling cycles, we arrive at a clock-speed of
$H_{Q}=640MHz/s$.

Table 1 collects the calculations made for the various scenarios.

$H_{Q}(MHz/s)$ | $f(USD)$ |  $O_{Q}$
---|---|---
40 | 23,536.12 |  6,258.27
40 | 10,385.49 |  2,761.51
40 | 31,000.00 |  8,242.92
40 | 100,000.00 |  26,590.06
640 | 23,536.12 |  100,132.28
640 | 10,385.49 |  44,184.12
640 | 31,000.00 |  131,886.68
640 | 100,000.00 |  425,440.90
Table 1: This table shows the income generated over the period of a year in
USD related to specified quantum computer clock speed and fiat currency
conversions. In the third column $O_{Q}$ is calculated with $I_{Q}=1(USD)$

From these results, the best case scenario can be found when $H_{Q}=640MHz/s$
and the market conversion result is $f=\$100,000$. In this case, as long as
the operational cost of the quantum device (_i.e._ the quantum cloud CPU time
charged by the provider) is below $O_{Q}=\$425,440.90$ a year, a quantum miner
would still be able to turn a profit.

###  IV.3 The Effects of Introducing Quantum PoW Technology

Finally, presented in Figure 2 is a cascading _virtuous cycle_ that will
propagate upon the introduction of quantum computers to a PoW based blockchain
network. This will happen as they become profitable when compared to classical
alternatives, according to Equation 10. Firstly, introducing quantum computers
into a PoW based blockchain, as discussed, will consequently increase the
hash-rate of the entire network, thereby shortening the average time it takes
for the network to calculate a block. According to a blockchains protocol this
will cause an increase in the PoW difficulty parameter in order to recalibrate
the block-time to the prescribed value.

Figure 2: Self-propagating cycle of increasing quantum advantage on PoW
networks. Adding quantum miners to the cryptocurrency network increases the
network’s hash-rate. An increased hash-rate will raise the difficulty
parameter. An increased difficulty parameter increases the relative quantum-
advantage. This, in turn, increases the profitability of quantum-mining, which
in turn motivates the introduction of more quantum miners.

Increasing the difficulty parameter of PoW has been shown to solidify the
quadratic advantage of quantum computers as miners. This advantage means that
there will be greater incentive for investment into quantum mining
technologies as the profit margin when compared with their classical
counterparts will increase. This greater incentive will once again increase
the number of quantum miners on the network, thereby decreasing the block-time
and increasing the PoW difficulty in turn. This creates cycle within which
quantum computing technologies will, eventually, completely replace classical
miners, as the later cease to be cost-effective.

This cascading effect also has a security benefit for the network itself. As
soon as the majority (roughly) of the miners are quantum, the network itself
become impervious to 51% attacks based on quantum advantage _alone_. It would
still be technically possible to mount such an attack, but such an attack
would only succeed by using _other_ methods such as miner-collusion, rather
than by merely leveraging quantum advantage.

Over time the increased difficulty parameter of PoW will lead to classical
miners being made obsolete. The increase in difficulty will cause the PoW
problem to become exponentially harder for both classical and quantum devices.
However, the impact to classical miners is quadratically worse, over time,
than the impact to quantum miners. Eventually, this will lead to all quantum
miners being more cost-effective than classical miners (regardless of their
initial setup costs).

##  V Conclusion

In closing, quantum computation gives a definite advantage over classical
computation for the purpose of calculating PoW for blockchains. As we have
seen, in Sec. III, this quantum advantage can be used by an adversarial party,
in order to attempt what are called 51% attacks, on the cryptocurrency. The
possibility of these types of attacks is, however, in the reasonably distant
future.

On the other hand, it is very unlikely that there ever will be a quantum-
secure—or _post-quantum_ —alternative to hashing for the purposes of PoW. Not
only is hashing-based PoW susceptible to quantum advantage, but so are other
well-known PoW systems such as Zcash’s use of the Birthday Paradox-based
computational problemhopwood2016zcash .

Moreover, it is unlikely that any PoW system can be derived is not susceptible
to some form of quantum advantage. This is because PoW, by definition,
requires a problem whose solution is hard to _compute_ (to ensure miners are
required to do meaningful _work_ for their PoW), while being fairly easy to
_verify_ (to ensure any third party can verify that the work has been
performed). And these are exactly the type of problems where quantum search
algorithms provide definite advantage over classical.

This means that once a quantum computer _does_ exist that can attack the
network in this way, there will be very little that can be done to safeguard
the blockchain network against said attacks.

One possible avenue is to drop the use of PoW by the blockchain completely,
and move to another consensus mechanism entirely—such as _Proof of
Space_dziembowski2015proofs , or other alternativesbentov2014proof ;
alwen2017scrypt .

Another safeguarding mechanism would be to move the entire cryptocurrency from
ASIC miners to quantum miners. In Sec. IV, we discussed the possibility of
doing this. We showed that mining cryptocurrency, using quantum computation,
can quickly become a profitable proposition. In Sec. IV.1 we gave a precise
formula that allows one to calculate a potential profit of using quantum
computation for PoW.

How profitable this is will clearly depend on considerations such as the
running cost of a quantum computer, and the initial costs of setting one up.
This latter cost can be removed if one chooses to use cloud quantum
computation. We calculated the precise revenue that one can expect from mining
bitcoin in 2025 across the period of a year using predicted available cloud
quantum computing at that time to be between $44,184.12 and $425,440.90,
depending on whether the most conservative or optimistic parameters are used.
This variable is based on the conversion rate of Bitcoin and the exact hashing
power of the quantum device at the time. Whether this is profitable will
depend on how much quantum cloud CPU time is charged for at that time. The
existence of secure remote quantum computing protocols such as _blind quantum
computation_barz2012demonstration , means that a client can safely use a cloud
quantum server for the purposes of mining Bitcoin, or other cryptocurrencies,
without any interference from the server. In short, this shows a very likely
profitable use of quantum computational resources in the coming decades. As
shown in Fig. 2, and described more generally in Sec. IV.3, the introduction
of quantum computers into a mining ecosystem will make subsequent use of
quantum computers even more profitable, as compared to classical
computers—which in turn will become less profitable over time.

In closing, we’ve introduced the mathematical machinery necessary to
understand, accurately, the impact of introducing quantum PoW technology into
cryptocurrency ecosystems—used both by malicious, and non-malicious actors. A
clear next step is to branch out the analysis we have done here to other
blockchain consensus mechanisms that were outside the scope of this work.

Another clear next step is to take the work we have developed here, as well as
real-world economic data, and use both together to create accurate,
predictive, models. Several useful predictive models could be developed to
help inform, say, investment strategies into quantum technologies, hedging
strategies for cryptocurrency investors and miners, etc. We have made some
simple predictions here, in Sec. IV.3. These simple models are meant, mostly,
to showcase the power of the mathematical machinery we have introduced—and to
hopefully motivate their use in creating more accurate, powerful, predictive
models. Even our very simplistic models already suggest a trend however: we
expect all PoW-based cryptocurrency mining to move to quantum platforms in the
coming decades.

## References

  * (1) M. Crosby, P. Pattanayak, S. Verma, V. Kalyanaraman, et al., “Blockchain technology: Beyond bitcoin,” Applied Innovation, vol. 2, no. 6-10, p. 71, 2016.
  * (2) L. M. Bach, B. Mihaljevic, and M. Zagar, “Comparative analysis of blockchain consensus algorithms,” in 2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2018.
  * (3) A. Anand, M. McKibbin, and F. Pichel, “Colored coins: Bitcoin, blockchain, and land administration,” in Annual World Bank Conference on Land and Poverty, 2016.
  * (4) C. M. Cap, “Cryptocurrency prices, charts and market capitalizations,” 2020.
  * (5) J. Kearney and C. Perez-Delgado, “Blockchain technologies vulnerability to quantum attacks,” 2020.
  * (6) D. Aggarwal, G. K. Brennen, T. Lee, M. Santha, and M. Tomamichel, “Quantum attacks on bitcoin, and how to protect against them,” arXiv preprint arXiv:1710.10377, 2017.
  * (7) R. Van Meter and C. Horsman, “A blueprint for building a quantum computer,” Communications of the ACM, vol. 56, no. 10, pp. 84–93, 2013.
  * (8) M. Mosca, “Cybersecurity in an era with quantum computers: Will we be ready?,” IEEE Security Privacy, vol. 16, pp. 38–41, Sep. 2018.
  * (9) C. Ye, G. Li, H. Cai, Y. Gu, and A. Fukuda, “Analysis of security in blockchain: Case study in 51%-attack detecting,” in 2018 5th International Conference on Dependable Systems and Their Applications (DSA), pp. 15–24, IEEE, 2018.
  * (10) A. M. Antonopoulos, Mastering Bitcoin: unlocking digital cryptocurrencies.  " O’Reilly Media, Inc.", 2014.
  * (11) S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” tech. rep., Manubot, 2019.
  * (12) A. Back et al., “Hashcash-a denial of service counter-measure,” 2002.
  * (13) L. Ren, “Analysis of nakamoto consensus.,” IACR Cryptol. ePrint Arch., vol. 2019, p. 943, 2019.
  * (14) P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th annual symposium on foundations of computer science, pp. 124–134, Ieee, 1994.
  * (15) L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212–219, 1996.
  * (16) P. G. Kwiat, J. R. Mitchell, P. D. D. Schwindt, and A. G. White, “Grover’s search algorithm: An optical approach,” Journal of Modern Optics, vol. 47, no. 2-3, pp. 257–266, 2000.
  * (17) J. Gambetta, “Ibm’s roadmap for scaling quantum technology,” Nov 2020.
  * (18) F. Arute and et al., “Quantum supremacy using a programmable superconducting processor,” Oct 2019.
  * (19) Blockchain.com, “Hash-rate in bitcoin,” 2020.
  * (20) G. E. Moore et al., “Cramming more components onto integrated circuits,” 1965.
  * (21) J. Shalf, “The future of computing beyond moore’s law,” Philosophical Transactions of the Royal Society A, vol. 378, no. 2166, p. 20190061, 2020.
  * (22) T. Ghose, “Forget moore’s law - quantum computers are improving according to a spooky ’doubly exponential rate’,” Jun 2019.
  * (23) CoinMetrics, “Coin metrics bitcoin charts,” Sep 2020.
  * (24) S. Klemens, “Monero mining hardware comparison 2020 (recently updated),” Aug 2020\.
  * (25) bitinfocharts, “Ethereum classic hash rate chart,” December 2020.
  * (26) https://bitcoin.org/, “Bitcoin,” 2009.
  * (27) https://etherscan.io/, “Ethereum (eth) blockchain explorer,” 2015.
  * (28) J. Garay, A. Kiayias, and N. Leonardos, “The bitcoin backbone protocol: Analysis and applications,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 281–310, Springer, 2015\.
  * (29) A. Meynkhard, “Fair market value of bitcoin: Halving effect,” Invest. Manag. Financ. Innov, vol. 16, pp. 72–85, 2019.
  * (30) en.bitcoin.it/wiki/, “Controlled supply.”
  * (31) IBM, “Ibm quantum experience,” 2020.
  * (32) S. J. Devitt, “Performing quantum computing experiments in the cloud,” Physical Review A, vol. 94, no. 3, p. 032329, 2016.
  * (33) D. Castelvecchi, “Ibm’s quantum cloud computer goes commercial,” Nature News, vol. 543, no. 7644, p. 159, 2017.
  * (34) B. B. Worldwide, “Bitcoin clock,” https://www.buybitcoinworldwide.com/bitcoin-clock/.
  * (35) D. Kraft, “Difficulty control for blockchain-based consensus systems,” Peer-to-Peer Networking and Applications, vol. 9, no. 2, pp. 397–413, 2016.
  * (36) D. Hopwood, S. Bowe, T. Hornby, and N. Wilcox, “Zcash protocol specification,” GitHub: San Francisco, CA, USA, 2016.
  * (37) S. Dziembowski, S. Faust, V. Kolmogorov, and K. Pietrzak, “Proofs of space,” in Annual Cryptology Conference, pp. 585–605, Springer, 2015.
  * (38) I. Bentov, C. Lee, A. Mizrahi, and M. Rosenfeld, “Proof of activity: Extending bitcoin’s proof of work via proof of stake [extended abstract] y,” ACM SIGMETRICS Performance Evaluation Review, vol. 42, no. 3, pp. 34–37, 2014.
  * (39) J. Alwen, B. Chen, K. Pietrzak, L. Reyzin, and S. Tessaro, “Scrypt is maximally memory-hard,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 33–62, Springer, 2017\.
  * (40) S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsimons, A. Zeilinger, and P. Walther, “Demonstration of blind quantum computing,” science, vol. 335, no. 6066, pp. 303–308, 2012.