Received August 10, 2020; revised September 28, 2020; accepted October 7,
2020; date of publication October 13, 2020; date of current version November
5, 2020. 10.1109/TQE.2020.3030314

Jakub Marecek, who has performed the present work while at IBM, is currently
with the Department of Computer Science, Faculty of Electrical Engineering,
Czech Technical University, 121 35, Prague, Czech Republic.

Corresponding author: Andrea Simonetto (email: andrea.simonetto@ibm.com).

# Quantum Computing for Finance: State of the Art and Future Prospects

DANIEL J. EGGER 1, CLAUDIO GAMBELLA 1, JAKUB MARECEK 1, SCOTT MCFADDIN 1,
MARTIN MEVISSEN 1, RUDY RAYMOND 1  ANDREA SIMONETTO 1  STEFAN WOERNER 1, ELENA
YNDURAIN 1  IBM Quantum

###### Abstract

This paper outlines our point of view regarding the applicability, state of
the art, and potential of quantum computing for problems in finance. We
provide an introduction to quantum computing as well as a survey on problem
classes in finance that are computationally challenging classically and for
which quantum computing algorithms are promising. In the main part, we
describe in detail quantum algorithms for specific applications arising in
financial services, such as those involving simulation, optimization, and
machine learning problems. In addition, we include demonstrations of quantum
algorithms on IBM Quantum back-ends and discuss the potential benefits of
quantum algorithms for problems in financial services. We conclude with a
summary of technical challenges and future prospects.

###### Index Terms:

Financial management, Machine learning algorithms, Optimization, Quantum
computing, Simulation

=-15pt

##  I Introduction

In the financial services industry there are many computationally challenging
problems arising in applications across asset management, investment banking
and retail & corporate banking. Quantum computing holds the promise of
revolutionizing how we solve such computationally challenging problems. With
the first, noisy quantum devices - leveraging the principles of quantum
mechanics - available publicly today (see e.g., [1, 2]), the applicability of
quantum computing for problems in finance and demonstrating Quantum Advantage
in first applications are active topics of current research [3, 4, 5, 6, 7, 8,
9, 10, 11, 12].

In this paper, we provide an introduction to quantum computing and the
necessary foundational concepts to understand this new technology and its
implications to the financial services industry [13]. We extend previous
summaries [3, 14, 15] in multiple directions, as follows. First, we review the
main algorithms, the benefits they bring as well as the technical challenges
they pose, and how to approach problems from a quantum perspective. We then
also highlight the economic benefits that applying quantum computing may bring
to financial institutions in improving operations, revenues, and quality.
Algorithms are categorized based on the type of problems they solve and mapped
to the financial solutions they can be applied to. We showcase real-life
examples of using quantum computing algorithms, explaining how the problems
are solved and the solutions obtained. Overall, we offer a holistic, practical
guide to quantum computing and its applicability to financial problems for
financial institutions in Banking, Financial Markets and Insurance.

All computing systems rely on a fundamental ability to store and manipulate
information. Today’s classical computers manipulate individual bits, which
store information as binary 0 and 1 states. Millions of bits work together to
process and display information with a speed that everyone is familiar with on
smart phones, laptops, and the servers in the cloud. Quantum computers use the
physical phenomena of nature to manipulate information via quantum mechanics.
At this fundamental level we have quantum bits, or qubits. Unlike a bit that
has to be a 0 or a 1 (or, their probabilistic combination), a qubit can be in
a complex-value-weighted combination of states called a superposition.
Multiple qubits may be purposefully entangled into linear combinations of
(complex-valued-weighted) states across the qubits, which ”correlates” them so
their quantum state cannot be described independently, i.e., entangled states.
And quantum interference allows us to bias the measurement of a qubit toward a
desired state, thus, controlling the probability a system of qubits collapses
into particular measurement states. Quantum computers are not a replacement
for classical ones. They complement the traditional systems by possibly being
able to solve some forms of intractable problems that blow up, or become
extremely large or time-consuming during computation. Remarkable progress in
the control and construction of quantum computing hardware in recent years has
led to the development of systems with 10’s of physical qubits, that in the
absence of quantum error correction are dubbed noisy quantum processors [16].
This has sparked strong interest in the pursuit of Quantum Advantage – the
exploration of computational tasks which a quantum computer solves faster than
a classical one. An example of a task for which Quantum Advantage has been
proven was introduced in [4] This is also a step on the way to the development
of Fault-Tolerant Universal Quantum Computers (FTQC), which require error
correction [17, 18, 19] and which will allow for arbitrary quantum algorithms
backed by theory that proves quantum speedup compared to classical algorithms.

The quantum computing hardware pursued by IBM involves superconducting quantum
circuits [20]. The fundamental building blocks of the hardware are Josephson
junction-based qubits called transmons. When cooled to ca. 10mK these
transmons behave as artificial atoms, where the two lowest energy levels may
be employed as the computational 0 and 1 states. Over the last two decades,
progress with superconducting qubit technology has been driven by tremendous
improvements in coherence, control and fabrication capabilities. A metric that
has been proposed and employed by IBM to measure progress in development in
quantum computing is Quantum Volume [21]. Quantum Volume indicates the
relative complexity of a problem that can be solved on a quantum computer, and
it depends on a number of factors such as number of qubits, coherence time,
measurement errors, device cross talk, circuit compiler efficiency, and
others. IBM currently has more than 20 superconducting processors available
via the cloud with up to 65 qubits, and put forward a roadmap for scaling
quantum technology in the years ahead [22].

In the near-term future, quantum computers will continue to rely on noisy
qubits with relatively high error rates and limited coherence times. In this
era of noisy quantum devices [16], we will be confidently in the realm of
Quantum Advantage once we are able to solve a good number of significant real-
world problems more efficiently with the help of quantum devices than compared
with solving them on a classical computers only. The problem classes where we
expect to demonstrate advantage first include (i) modelling physical processes
of nature, (ii) obtaining better solutions to optimization problems, and (iii)
finding better patterns within machine learning processes, since first
promising proposals for near-term compatible quantum heuristics exist [23, 24,
25].

At a basic level, any solution built on a quantum computer will comprise three
fundamental steps:

#### The Loading Step

The solution must load its data from a classical computer into the quantum
computer in a small number of steps. This results in a superposition which
combines the fundamental states described above in a way that reflects the
data set being loaded. While loading data into a computer is often ignored as
a triviality in classical computing, quantum data loading can be a substantial
aspect of solution design. While there are loading techniques which are linear
in the size of the data set, this can often eclipse the coherence times of the
physical superposition, and techniques are often employed to reduce the input
data before loading or encode the data into the computational steps.

#### The Compute Step

Once data is loaded, the solution must rapidly perform a computation on the
loaded data within the quantum computer. This involves manipulation of the
qubits in a manner that changes the fundamental states in a way that reflects
the outcome of a desired computation. There is an increasing body of research
into quantum algorithms that solve problems that are considered
computationally difficult or intractable classically. Quantum computations
often compute their results as an approximation to an optimal value within a
high dimensional search space, and often exploit the nature of quantum
superpositions to simultaneously consider vast numbers of possibilities. The
computed ”output” superposition reflects a probabilistic distribution of
possible outcomes, with the preferred outcomes associated with higher
probabilities in the distribution.

#### The Measurement Step

The measurement step makes an observation of the computed ”output”
superposition and reports it back to a classical computer. However, the act of
observation “snaps” the superposition back to a basis state, so the
computation step must be designed in such as way that the solution is often
encoded in a narrow decision space. Quantum algorithms are often repeated
multiple times, with each repetition called a shot. Each shot reports an
output among the distribution of possible outputs from the compute step. With
multiple repetitions, a probabilistic picture emerges of which output has
received the highest probability within the superposition, and an “answer” may
be read. Typically hundreds or thousands of shots are used. It should be noted
that the higher the number of qubits, the higher requirements on precision,
and hence the higher the requirements on the number of measurements.

##  II Problems in Financial Services

Financial services are a forward-looking industry that has always been in the
lookout to leverage new technologies to increase profits. Broadly, this
industry covers three vertical sectors (c.f. also Table I for segments):

  * •

Banking: Banking products are mainly bank accounts, investments, loans for
commercial and retail customers. Their main challenges are to balance cash
with interest rates, while controlling threats related to liquidity, fraud,
money laundry, or non-performing loans.

  * •

Financial Markets: Focused mainly on future gains and the marketplace to sell
and buy assets by dealers, exchanges, brokers, or clearing houses. Their main
challenges are to manage geographic time-zones, immediacy needs, and counter-
party risk.

  * •

Insurance: Health insurance, automobile & property, life insurance & annuity
and re-insurance. The main challenge here is to maximize premiums and manage
threats related to unplanned risks such as catastrophes or market crashes.

TABLE I: Segments of the financial services industry Banking | Financial Markets | Insurance
---|---|---
Monetary Authorities | Commodities | Health Insurance
Retail Banking | Stock Exchanges | Property &
|  | Casualty Insurance
Commercial | Bond Markets | Life Insurance
Banking |  | & Annuity
Investment Banking | Money Markets | Reinsurance
Non-Banking FIs | Derivatives |

The digital financial services revolution is full blast disrupting the
industry and opening the door to new players threatening the current status
quo [26]: FinTechs and InsurTechs with new digital-style offerings, RegTech
with automatized regulation processes, and new competition from other industry
corporations that can now offer digital financial services to their customers.
In addition, clients are demanding customized offerings based on their
behavioral data, for example, personalized insurance premiums based on their
life-events or targeted loan offers for smaller customer segments. The
regulatory environment poses an operational challenge by requiring risk
mitigation and strict compliance. All these trends have created new financial
services experiences: Smooth global supply-chains for trade finance asset
management, AI augmentation with trusted decision making for investment
banking, and banking platforms that become finance ‘as-a-service’.

In this paper, we consider the regulatory framework given by the Basel III
rules, which is being implemented by regulators world-wide. Under Basel III, a
key performance indicator for both the regulator and regulated entities is
capital adequacy ratio (CAR), which is a ratio of the combined tier-1 and
tier-2 capital and risk-weighted holdings. In particular, the minimum is 8%,
while the required ratio is 10.5%.

Moreover, the Liquidity Coverage Ratio (LCR) reform [27], with the aim of
improving short-term resilience, promotes the holding of unencumbered high-
quality liquid assets (HQLA), whose amounts are tested in the so-called 30
calendar day liquidity stress scenario. By January 1st, 2019, the LCR, i.e.,
the proportion of the value of the stock of HQLA in stressed conditions to
total net cash outflows in the same scenario, has risen to 100%. Within HQLA,
“Level 1” assets include cash and certain state-backed securities, as well as
select other safe assets. “Level 2” include further state-backed securities
and bonds of non-state and non-bank entities with long-term rating AA- or
better. “Level 2” assets can only comprise up to 40% of the stock of HQLA.
Further, the same LCR reform introduced diversification requirements on the
stock of HQLA. These extensions complicate both risk assessment and portfolio
management problems considerably.

Figure 1: Transformative technologies in support of digital themes in
financial services [28]. Figure 2: Finance industry transformation in waves
driving to a digital future [28].

Indeed, many problems, such as risk management and portfolio management, rely
on various risk measures that we now introduce for future reference.
Volatility captures the risk in a portfolio of assets. It is the standard
deviation of the returns which can be calculated from the variance
$\omega^{\intercal}\Sigma\omega$. Here, $\omega$ is a (column) vector made of
the weights of each asset in the portfolio and $\Sigma$ is the covariance
matrix of the returns of the assets.

Risk management often uses Value at Risk (VaR) as a risk measure.
$\rm{VaR}_{\alpha}$ of a random variate $X$ is the $1-\alpha$ quantile of the
loss distribution $Y=-X$. VaR is, therefore, the minimal $\gamma$ such that
the probability that $X$ exceeds $\gamma$ is $\alpha$, i.e.,

$\displaystyle{\rm VaR}_{\alpha}(X):=-{\inf}\\{\gamma~{}{\rm
such~{}that}~{}F_{X}(\gamma)>\alpha\\},$ (1)

where $F_{X}(x)$ is the cumulative distribution function of $X$. Since VaR is
a quantile it has the short-coming that it is not sensitive to extreme losses
in the tail of $X$. The conditional value at risk CVaR is, therefore, often
used as an additional risk metric. $\rm{CVaR}_{\alpha}$, sometimes also called
expected shortfall, is the expectation value of all losses up to the
$\rm{VaR}_{\alpha}$. In the financial services challenges discussed in the
remainder of this paper, we are assuming a market environment operating under
the Basel III regulations.

Planned updates to the framework, upcoming under Basel IV, focus on the
approach to calculate Risk weighted assets (RWA) regardless of risk type.
Banks will need to change their projection models towards forward-looking
statements which are statements that are not solely based on historical facts
and therefore have more assumptions. This will require more scenario building
to comply with the new requirements for Capital lower limits (72.5% “output
floor”), credit risk with common approach rather than internal, market risk
sensitivity-driven analysis as a standard, and operational risk measured by
“unadjusted business indicator” leveraging historical loss data. Overall Basel
IV will reshape banks’ trading activities and portfolio structures.

In this paper, the focus is in three areas of financial services, where
problems challenging for classical computers arise today:

  1. 1.

Asset Management;

  2. 2.

Investment Banking;

  3. 3.

Retail and Corporate Banking.

A few examples of transformative technologies leveraged in these areas
include, the use of AI for Asset Management through bots as the new user
interfaces, the adoption of algorithmic trading that changed the stock market
with High Frequency Trading for Investment Banking, and the increased use of
mobile devices for payments impacting financial transactions in Retail
Banking, see also Figure 1.

The adaption of new technologies and evolution of financial services can be
traced in waves leading to a digital future. The first wave focused on mobile
adoption to engage customers. This was followed by the exploration of new
business models to leverage new data sources and the threat from technology
providers. The third, current wave is driven by a combination of challenges
including cost pressures, technology disruptions and regulatory changes, see
Fig. 2. This is causing a fundamental redefinition of the financial
institution, its internal operations, and how it engages externally. Further
background is provided in Ref. [28]. Within this context, the future benefits
of quantum computing for businesses could be measured across a set of key
business metrics:

  * •

Reduce regulatory penalty costs or avoidable human labor.

  * •

Improve customer satisfaction and brand perception.

  * •

Increase customer interaction and financial activity.

  * •

Reduce capital levels and improve cash-flow.

In the following sections, we group specific problems arising in the financial
services where classical computers face challenges or are insufficient, in
three classes, Simulation, Optimization and Machine learning, we introduce the
quantum algorithms applicable to them, and discuss results obtained on IBM
Quantum back-ends for some specific problems. Each quantum algorithm is
applied on tasks and calculations that affect one or more phases of the
customer life cycle, shown in Fig. 3, and we describe the specific business
benefits it may bring.

Figure 3: Customer life cycle conceptual design. Here, a customer can be a
corporation, fund, financial institution, government, or individual.

##  III Simulation

In this section we discuss simulation problems, where quantum computing may be
beneficial. There are simulation problems at each stage of the customer life
cycle (see Figure 3):

  1. 1.

Customer identification Obtain new revenue sources for value-added services
such as derivative pricing using sophisticated quantum computing algorithms.
This offering can help compensate for the monetary losses of MiFIDII new
transparency measures in trading, estimated to cost $ 240 Million [29].

  2. 2.

Financial products Better manage Value at Risk and the Economic Capital
Requirement providing more accurate estimates to improve liquidity management
by actively managing the balance sheet, increase capital to maintain a 7%
equity capital ratio to its riskier assets and avoid Basel III related
compliance fines [30] that are up to 10% of Bank’s turnover (revenue).

  3. 3.

Monitor transactions Allow for a more precise approach to incorporating market
volatility into an institution’s Tier 1 reporting [31], optimizing risk
weighted assets results through a much more accurate/precise calculation
process.

  4. 4.

Customer retention Improve risk analysis for the new Net Stable Funding Ratio
time-frames requirements that will impact the cost of doing business for Prime
Brokers and hedge funds. The stable funding for securities Lending
Transactions shifts from 0% to 10% for Level 1 collateral and to 15% for other
collateral [32].

Overall, Basel regulation implementation and the new needs of risk management
is of mandatory interest for financial institutions, with an estimated
technology cost between EUR 45 million and EUR 70 Million [33].

Simulation focuses on creating scenarios of potential outcomes, such as the
impact of volatility on risk, evaluating asset values for pricing, or
monitoring economic system impacts in the market.

One key task in the finance industry where simulation is crucial is the
pricing of financial instruments and estimating their risk. For example, the
buyers and sellers of complex financial instruments gain a competitive
advantage when they can price such instruments with a better accuracy than
their competition. Regulations such as Basel III require banks to perform
stress tests and to hold an amount of capital that depends on their risk-
weighted assets. However, pricing and estimating the risk of many financial
instruments is computationally intensive. Analytical models are often too
simplistic to capture the complex dependencies between financial instruments
or cannot take into account some of their features such as path-dependency.
Monte Carlo (MC) simulations are, therefore, used to estimate risk metrics, to
price financial instruments, and to perform scenario analysis that can be used
in stress tests. In a MC simulation $M$ samples are drawn from the model input
distributions and are used to construct an estimation of a quantity of
interest. The confidence interval of this estimation scales as
$\mathcal{O}(1/\sqrt{M})$ making MC computationally intensive. For instance,
decreasing the size of the confidence interval by an order of magnitude
requires increasing the computational cost by a factor of 100. In this
section, we briefly discuss MC for option pricing (see Sec. III) and risk
calculations (see Sec. III) and then discuss how such tasks can be performed
on quantum computers using amplitude estimation (see Sec. III-A).

#### Option Pricing

Options are financial derivative contracts that give the buyer the right, but
not the obligation, to buy (call option) or sell (put option) an underlying
asset at an agreed-upon price (strike) and time-frame (exercise window). In
their simplest form, the strike price is a fixed value and the time-frame is a
single point in time, but exotic variants may be defined on more than one
underlying asset, the strike price can be a function of several market
parameters and could allow for multiple exercise dates [34]. Options provide
investors with a vehicle to profit by taking a view on the market or exploit
arbitrage opportunities and are core to various hedging strategies. As such,
understanding their properties is a fundamental objective of financial
engineering. Due to the stochastic nature of the parameters options are
defined on, calculating their fair value can be an arduous task. Analytical
models exist for the simplest types of options [35] but the simplifying
assumptions on the market dynamics required for the models to provide closed-
form solutions often limit their applicability [36]. Hence, more often than
not, numerical MC simulations are employed for option pricing since they are
flexible and can generically handle stochastic parameters [37, 38]. Option
pricing with MC generally proceeds by simulating many paths of the time
evolution undergone by the underlying assets to build a distribution of the
option payoff at maturity. The option price is then obtained by discounting
the expected value of this distribution. Classical MC methods require
extensive computational resources to provide accurate option price estimates,
particularly for complex options. Because of the widespread use of options in
the finance industry, accelerating the methodology to price them can
significantly impact the operations of a financial institution.

#### Risk Management

Risk management plays a central role in the financial system. It allows
companies, institutions, and individuals to avoid monetary losses and grow
their business. Financial risk, which comes in many forms such as credit risk,
liquidity risk, and market risk, is often estimated using models and
simulations. The accuracy of these models has a direct impact on the
operations of the entity using them. For instance, the capital requirements
imposed on banks under the Basel accords depend on the accuracy of risk models
[39]. Therefore, banks with more accurate models can make better use of their
capital. Value at risk (VaR) [40], a quantile of the loss distribution, is a
widely used risk metric. For example, the Basel III regulations require banks
to perform stress tests using VaR [41]. Monte Carlo simulations are the method
of choice to determine VaR and CVaR. They are done by building a model and
computing the loss/profit distribution for $M$ different realizations of the
model input parameters. Many different runs are needed to achieve a
representative distribution of the loss/profit distribution. Classical
attempts to improve the performance are variance reduction or Quasi-Monte
Carlo techniques [42, 38, 43]. The first aims at reducing the constants while
not changing the asymptotic scaling; whereas, the latter improves the
asymptotic behavior, but only works well for low-dimensional problems.

In Section III-A we discuss how Quantum Amplitude Estimation can provide a
quadratic speed-up over classical Monte Carlo (MC) simulations and highlight
the steps needed to calculate value at risk in Section III-B. We then employ
these methods in the context of credit risk as already discussed in [5] and
summarized here in Section III-C. For a detailed discussion on how Quantum
Amplitude Estimation can provide an advantage for options pricing, we refer to
[6, 7, 44].

###  III-A Quantum Amplitude Estimation

Amplitude estimation (AE) is a quantum algorithm that can estimate a parameter
$a$ with a convergence rate $\mathcal{O}(1/M)$ where $M$ is the number of
quantum samples. This corresponds to a quadratic speed-up compared to
classical MC. AE is based on a unitary operator $\mathcal{A}$ acting on a
register of $(n+1)$ qubits such that
$\mathcal{A}\ket{0}_{n+1}=\sqrt{1-a}\ket{\psi_{0}}_{n}\ket{0}+\sqrt{a}\ket{\psi_{1}}_{n}\ket{1}$
for some normalized states $\ket{\psi_{0}}_{n}$ and $\ket{\psi_{1}}_{n}$,
where $a\in[0,1]$ is unknown. AE allows the efficient estimation of $a$, i.e.,
the probability of measuring $\ket{1}$ in the last qubit [45]. This is done
using an operator $Q$ defined as

$Q\\!=\\!\mathcal{A}(\mathbb{I}-2\ket{0}_{n+1}\bra{0}_{n+1})\mathcal{A}^{\dagger}(\mathbb{I}-2\ket{\psi_{0}}_{n}\ket{0}\bra{\psi_{0}}_{n}\bra{0}),$

where $\mathbb{I}$ denotes the identity operator, and Quantum Phase Estimation
[46] to approximate certain eigenvalues of $Q$. AE requires $m$ additional
qubits and $M=2^{m}$ (controlled) applications of $Q$. The $m$ qubits are
first put into equal superposition, i.e. $\ket{0}_{m}\to
1/\sqrt{M}\sum_{k=0}^{M-1}\ket{k}_{m}$, by applying Hadamard gates which are
single-qubit gates that perform $\ket{0}\to(\ket{0}+\ket{1})/\sqrt{2}$. Then,
the $m$ qubits are used to control the applied power of $Q$, which leads to
the state

$\displaystyle
1/\sqrt{M}\sum_{k=0}^{M-1}\ket{k}_{m}Q^{k}\mathcal{A}\ket{0}_{n+1},$ (2)

where each $Q^{k}$ imparts the phase $e^{-2ik\theta_{a}}$ and
$e^{+2ik\theta_{a}}$, respectively, to the two eigenstates of $\mathcal{Q}$
that lie in the span of the states $\ket{\psi_{0}}_{n}\ket{0}$ and
$\ket{\psi_{1}}_{n}\ket{1}$. Next, the inverse Quantum Fourier Transform

$\displaystyle\mathcal{F}_{M}^{\dagger}:\ket{k}_{m}\to\frac{1}{\sqrt{M}}\sum_{y=0}^{M-1}e^{-2\pi
iyk/M}\ket{y}_{m}$ (3)

is applied to interfere these phases. Last, measuring the $m$ qubits results
in an integer $y\in\\{0,\ldots,M-1\\}$ which corresponds to the states for
which the phases interfered constructively, i.e., $y\simeq M\theta_{a}/\pi$,
see the circuit in Fig. 4. The integer $y$ is then classically mapped to the
estimator $\tilde{a}=\sin^{2}(y\pi/M)\in[0,1]$. The estimator $\tilde{a}$
satisfies

$\displaystyle|a-\tilde{a}|$ $\displaystyle\leq$
$\displaystyle\frac{2\sqrt{a(1-a)}\pi}{M}+\frac{\pi^{2}}{M^{2}}$ (4)
$\displaystyle\leq$
$\displaystyle\frac{\pi}{M}+\frac{\pi^{2}}{M^{2}}\;=\;O\left(M^{-1}\right),$

with probability of at least $8/\pi^{2}$. This represents a quadratic speedup
compared to the $O\left(M^{-1/2}\right)$ convergence rate of classical Monte
Carlo methods [40].

Figure 4: Quantum circuit for amplitude estimation as introduced in [45]. $H$
is the Hadamard gate and $\mathcal{F}_{m}^{\dagger}$ denotes the inverse
Quantum Fourier Transform on $m$ qubits.

Recently, several variants of AE have been proposed that simplify the required
quantum circuits [8, 47, 48]. They leverage the same underlying structure, but
allow to remove the $m$ additional qubits as well as the Quantum Fourier
Transform. For a comparison of available AE variants, we refer to [48].

###  III-B Estimating value at risk with AE

The discussion above shows that to efficiently estimate a parameter $a$ we
need the corresponding operator $\mathcal{A}$. We make use of AE in finance by
building the $\mathcal{A}$ operator for each quantity of interest, such as a
risk measure, of a random variate $X$. We represent the distribution of $X$ as
an $n$-qubit quantum state

$\displaystyle\ket{\psi}_{n}=\sum_{i=0}^{N-1}\sqrt{p_{i}}\ket{i}_{n}$ (5)

by discretizing the outcomes of $X$ and mapping them to $i\in\\{0,...,N-1\\}$
where $N=2^{n}$. Here, $p_{i}\in[0,1]$ is the probability of measuring the
state $\ket{i}_{n}$ which is a binary representation of $i$. By adding an
ancilla qubit to the $n$-qubit register and applying the operator

$\displaystyle
F:\ket{i}_{n}\ket{0}\to\ket{i}_{n}\left(\sqrt{1-f(i)}\ket{0}+\sqrt{f(i)}\ket{1}\right),$
(6)

for some function $f(i)$, to the state $\ket{\psi}_{n}\ket{0}$ results in the
quantum state

$\displaystyle\sum_{i=0}^{N-1}\sqrt{p_{i}}\sqrt{1-f(i)}\ket{i}_{n}\ket{0}+\sum_{i=0}^{N-1}\sqrt{p_{i}}\sqrt{f(i)}\ket{i}_{n}\ket{1}.$
(7)

By comparing this state to
$\mathcal{A}\ket{0}_{n+1}=\sqrt{1-a}\ket{\psi_{0}}_{n}\ket{0}+\sqrt{a}\ket{\psi_{1}}_{n}\ket{1}$
we find that the probability of measuring $\ket{1}$ in the ancilla qubit is
$a=\sum_{i=0}^{N-1}p_{i}f_{i}$. We can therefore obtain an estimate for ${\rm
VaR}_{\alpha}(X)$ by choosing

$\displaystyle f(i)=\left\\{\begin{array}[]{cc}1&i\leq l\\\
0&\text{otherwise}\end{array}\right.$ (10)

for some level $l$. With this definition of $f(i)$ the probability of
measuring $\ket{1}$ in the ancilla qubit is
$\sum_{i=0}^{l}p_{i}=\mathbb{P}[X\leq l]$. With a binary search over $l$ we
find the smallest $l_{\alpha}$ such that $\mathbb{P}[X\leq l_{\alpha}]\geq
1-\alpha$. The smallest $l_{\alpha}$ corresponds to the value at risk. This
estimation of ${\rm VaR}_{\alpha}(X)$ has accuracy $\mathcal{O}(M^{-1})$, i.e.
a quadratic speed-up compared to classical Monte Carlo methods (omitting the
additional logarithmic complexity of the bisection search) – where
$\mathcal{O}(\cdot)$ indicates the big-$\mathcal{O}$ notation. Here, we
assumed a one-dimensional probability distribution. Probability distributions
with more then one random variable can be loaded into a corresponding number
of qubit registers [9]. Correlations between the random variables are then
introduced by suitably entangling these qubit registers.

###  III-C Credit risk

The quantum method to calculate value at risk, outlined in the previous
sections, can be applied in the context of credit risk to determine the
economic capital requirement (ECR) associated to holding a portfolio of $K$
loans [5]. The ECR is the amount of capital that needs to be held on the
balance sheet to protect against unexpected losses. It is therefore defined as
the value at risk less the expected value of the loss distribution
$\mathcal{L}$, i.e.

$\displaystyle{\rm ECR}_{\alpha}(\mathcal{L})={\rm
VaR}_{\alpha}(\mathcal{L})-{E}(\mathcal{L})$ (11)

where $\alpha$ is the confidence level. Estimating the value at risk is often
a computationally intensive task requiring classical MC simulation. However,
quantum amplitude estimation can achieve the same result with a quadratic
speed-up. We illustrate amplitude estimation for a portfolio of $K$ assets for
which the multivariate random variable $(L_{1},...,L_{K})\in\mathbb{R}_{\geq
0}^{K}$ denotes each possible loss associated to each asset. The expected
value of the total loss $\mathcal{L}=\sum_{k=1}^{K}L_{k}$ is
$\mathbb{E}[\mathcal{L}]=\sum_{k=1}^{K}\mathbb{E}[L_{k}]$. The value at risk
for a given confidence level $\alpha\in[0,1]$ is defined as the smallest total
loss that still has a probability greater than or equal to $\alpha$, i.e.,

$\displaystyle\text{VaR}_{\alpha}[\mathcal{L}]$ $\displaystyle=$
$\displaystyle\inf_{x\geq 0}\left\\{x\mid\mathbb{P}[\mathcal{L}\leq
x]\geq\alpha\right\\}.$ (12)

Common values of $\alpha$ for ECR found in the finance industry are around
$99.9\%$. We assign a Bernoulli random variable $X_{k}$ to each asset to
indicate if it is in a default state such that $L_{k}=\lambda_{k}X_{k}$ where
$\lambda_{k}>0$ is the loss given default (LGD). The probability that
$X_{k}=1$, i.e., a loss for asset $k$, is $p_{k}$. The expected loss of the
portfolio $\mathbb{E}[\mathcal{L}]=\sum_{k=1}^{K}\lambda_{k}p_{k}$ is easier
to evaluate than $\text{VaR}_{\alpha}[\mathcal{L}]$, which usually requires a
Monte Carlo simulation. The defaults $X_{k}$ are usually correlated which we
model following a conditional independence scheme [49]. Given a realization
$z$ of a latent random variable $\mathcal{Z}$, the Bernoulli random variables
$X_{k}\mid\mathcal{Z}=z$ are assumed independent, but their default
probabilities $p_{k}$ depend on $z$. We follow [49] and assume that
$\mathcal{Z}$ has a standard normal distribution and that

$\displaystyle p_{k}(z)$ $\displaystyle=$
$\displaystyle\Phi\left(\frac{\Phi^{-1}(p_{k}^{0})-\sqrt{\rho_{k}}z}{\sqrt{1-\rho_{k}}}\right),$
(13)

where $p_{k}^{0}$ denotes the default probability for $z=0$, $\Phi$ is the
cumulative distribution function (CDF) of the standard normal distribution,
and $\rho_{k}\in[0,1)$ determines the sensitivity of $X_{k}$ to $\mathcal{Z}$.
This scheme is similar to the one used for regulatory purposes in the Basel II
(and following) Internal Ratings-Based (IRB) approach to credit risk [50, 41],
and is called the _Gaussian conditional independence model_ [49].

To estimate VaR, we use AE to efficiently evaluate the CDF of the total loss,
i.e., we will construct $\mathcal{A}$ such that $a=\mathbb{P}[\mathcal{L}\leq
x]$ for a given $x\geq 0$, and apply a bisection search to find the smallest
$x_{\alpha}\geq 0$ such that $\mathbb{P}[\mathcal{L}\leq
x_{\alpha}]\geq\alpha$, which implies
$x_{\alpha}=\text{VaR}_{\alpha}[\mathcal{L}]$ [9].

Mapping the CDF of the total loss to a quantum operator $\mathcal{A}$ requires
three steps. Each step corresponds to a quantum operator. First, $\mathcal{U}$
loads the uncertainty model. Second, $\mathcal{S}$ computes the total loss
into a quantum register with $n_{S}$ qubits. Last, $\mathcal{C}$ flips a
target qubit if the total loss is less than or equal to a given level $x$
which is used to search for $\text{VaR}_{\alpha}$. Thus, we have
$\mathcal{A}=\mathcal{CSU}$ and the corresponding circuit is illustrated in
Fig. 5 on a high level.

Figure 5:  High level circuit of the operator $\mathcal{A}$ used to evaluate
the CDF of the total loss: the first qubit register with $n_{Z}$ qubits
represents $\mathcal{Z}$, the second qubit register with $K$ qubits represents
the $X_{k}$, the third qubit register with $n_{S}$ qubits represents the sum
of the losses, i.e., the total loss, and the last qubit is flipped to
$\ket{1}$ if the total loss is less than or equal to a given $x$. The
operators $\mathcal{U}$, $\mathcal{S}$, and $\mathcal{C}$ represent the
loading of uncertainty, the summation of losses, and the comparison to a given
$x$, respectively.

We now discuss the operators $\mathcal{U}$, $\mathcal{S}$, and $\mathcal{C}$
in more detail. The loading operator $\mathcal{U}$ loads the distribution of
$\mathcal{Z}$ and prepares the $X_{k}$ of each asset. To include correlations
between the default events we represent $\mathcal{Z}$ in a register with
$n_{Z}$ qubits. We use a truncated and discretized approximation with
$2^{n_{Z}}$ values, where we consider an affine mapping $z_{i}=a_{z}i+b_{z}$
from $i\in\\{0,...,2^{n_{Z}}-1\\}$ to the desired range of values of
$\mathcal{Z}$. Since $\mathcal{Z}$ follows a standard normal distribution we
can efficiently load it to a quantum register with controlled rotations [51].
We encode the $X_{k}$ of each asset in the state of a corresponding qubit by
applying to qubit $k$ a $Y$-rotation $R_{Y}(\theta_{p}^{k})$, controlled by
the qubit register representing $\mathcal{Z}$, with angle
$\theta_{p}^{k}(z)=2\arcsin(\sqrt{p_{k}(z)})$. For simplicity, we use a first
order approximation111Higher order approximations of $\theta_{p}^{k}(z)$ can
be implemented using multi-controlled rotations. Furthermore, by using quantum
arithmetic one could also compute $\theta_{p}^{k}(z)$ directly [9]. of
$\theta_{p}^{k}(z)$ and include the affine mapping from $z$ (a value of the
normal distribution) to $i$ (an integer represented by $n_{Z}$ qubits), i.e.,
$\theta_{p}^{k}(z_{i})\approx a_{k}i+b_{k}$. This prepares qubit $k$ in the
state $\sqrt{1-p_{k}}\ket{0}+\sqrt{p_{k}}\ket{1}$ for which the probability to
measure $\ket{1}$ is $p_{k}$. The $\ket{1}$ state of qubit $k$ thus
corresponds to a loss for asset $k$.

Next, we need to compute the resulting total loss for every realization of the
$X_{k}$. Therefore, we use a weighted sum operator

$\displaystyle\mathcal{S}:$
$\displaystyle\ket{x_{1},\cdots,x_{K}}_{K}\ket{0}_{n_{S}}$ (14)
$\displaystyle\mapsto$
$\displaystyle\ket{x_{1},\cdots,x_{K}}_{K}\ket{\lambda_{1}x_{1}+\cdots+\lambda_{K}x_{K}}_{n_{S}},$

where $x_{k}\in\\{0,1\\}$ denote the possible realizations of $X_{k}$. We set
the size of the sum register to
$n_{S}=\lfloor\log_{2}(\lambda_{1}+\cdots+\lambda_{K})\rfloor+1$ qubits to
represent all possible values of the sum of the losses given default
$\lambda_{k}$, assumed to be integers. To implement $\mathcal{S}$ we apply a
divide and conquer approach and first sum up pairs of assets, then pairs of
the resulting sums and so on until we computed the total sum. This implies
that we start with a weighted-sum operator, discussed in detail in [7], and
then continue with adder circuits [52] to iteratively combine the intermediate
results.

Last, we need an operator that compares a particular loss realization to a
given $x$ and then flips a target qubit from $\ket{0}$ to $\ket{1}$ if the
loss is less than or equal to $x$. This operator is defined by

$\displaystyle\mathcal{C}:\ket{i}_{n_{S}}\ket{0}\mapsto\begin{cases}\ket{i}_{n_{S}}\ket{1}&\text{if
$i\leq x$},\\\ \ket{i}_{n_{S}}\ket{0}&\text{otherwise.}\end{cases}$ (15)

A fixed value comparator, i.e., a comparator that takes a fixed value to
compare to as a classical input, can be based on adder circuits [53]. Here, a
logarithmic scaling can be achieved by adding a linear number of ancilla
qubits.

We now show the performance of the quantum algorithm for an illustrative
example with $K=2$ assets. Each asset is defined by the triplet
$(\lambda_{k},p_{k}^{0},\rho_{k})$, i.e. the loss given default, the default
probability for $z=0$, and the sensitivity of $X_{k}$ to $\mathcal{Z}$,
respectively. We chose $(1,\,0.15,\,0.1)$ and $(2,\,0.25,\,0.05)$ for asset
one and two, respectively, which results in the loss distribution shown in
Fig. 6. This distribution is naturally encoded into the four states of two
qubits, indicated by the state labels in Fig. 6 which illustrates how a qubit
register can encode the exponential number of portfolio states as a quantum
superposition. From the chosen $\lambda_{k}$’s it follows that the sum
register requires $n_{S}=2$ qubits to represent all possible losses. We
represent $\mathcal{Z}$ with $n_{Z}=2$ qubits. Thus, $\mathcal{A}$ is
operating on seven qubits that represent this problem on a quantum computer,
including the objective qubit.

Figure 6: Loss distribution of the two-asset portfolio. The green and orange
dashed lines show the expected value and the 95% value at risk of the
distribution, respectively.

To simulate our algorithm we input the circuit for $\mathcal{A}$ to the AE
sub-routine implemented in _Qiskit_ [54] and perform the bisection search
using the result to find $x_{\alpha}$. We use $m=4$ evaluation qubits giving
us 16 quantum samples. Our implementation requires one additional ancilla
qubit to create $\mathcal{Q}$. Therefore, this experiment requires a total of
12 qubits that we simulate on classical computers using the
statevector_simulator back-end provided by _Qiskit Aer_. Since $n_{S}=2$, the
bisection search requires at most two steps, as shown in Fig. 7. To ensure
that the entire probability distribution is captured by the initial lower and
upper bounds of the bisection search we set them at losses of -1$ and 3$,
respectively. The simulations, shown in Fig. 7, properly identify the 95%
value at risk, located at a loss of 2$, on the first iteration of the
bisection search. We expect that the number of iterations needed in the
bisection search will scale linearly with the number of assets in the
portfolio.

Figure 7: Cumulative distribution function (left) of the total loss
$\mathcal{L}$ (blue), shown in Fig. 6, for a two-asset portfolio. The red
dashed line is the target value at risk level $\alpha=95\%$. Bisection search
to compute VaR (middle and right) using $m=4$ sampling qubits, i.e. 16 quantum
samples: orange and blue represent the lower and upper bounds of the search
interval, respectively, and green is the resulting midpoint. The red dashed
line shows the exact value.

We have investigated in Ref. [5] the quantum resources required for $K=2^{20}$
assets, i.e. a portfolio of approximately one million assets. With $n_{Z}=10$,
$n_{S}=30$, and $m=10$, a fault tolerant universal quantum computer would
require approximately 37 million T/Toffoli gates. If we assume that error-
corrected T/Toffoli-gates can be executed in $10^{-4}$ seconds [55] and that
the quantum phase estimation can be removed [8], which reduces the circuit
depth by a factor of two, we estimate a runtime of 30 minutes to estimate the
value at risk for a one-million-asset portfolio [5]. This estimate may change
as quantum computing technology advances.

###  III-D Distribution loading

Replacing a MC simulation with AE requires efficiently loading the
distributions of the random variables in the model to the quantum computer to
avoid diminishing the potential Quantum Advantage. This is feasible, e.g. for
efficiently integrable probability distributions such as log-concave
distributions for which the loading operator can be built from controlled
rotations [51]. The loading of arbitrary states into quantum systems, however,
requires exponentially many gates [56], making it inefficient to model
arbitrary distributions as quantum gates. Since the distributions of interest
are often of a special form, the limitation may be overcome by using quantum
Generative Adverserial Networks (qGAN). These networks allow us to load a
distribution using a polynomial number of gates [57].

###  III-E Summary

We have shown how AE can be used to estimate the ECR for a portfolio of loans.
This results in a quadratic speed-up (omitting the logarithmic cost of the
bisection search in VaR) over classical MC simulations. The example also shows
that the quantum circuit needed to implement $\mathcal{A}$ depends on the task
at hand. Therefore, extending this work to other financial simulation tasks
requires task specific quantum circuits to implement $\mathcal{A}$.

##  IV Optimization

In this section we discuss optimization problems, where quantum computing may
be beneficial. As in the case of simulation, there are optimization problems
at each stage of the customer life cycle (see Figure 3):

  1. 1.

Customer identification (and assesment) Improve Financial Supply Chain
Efficiency [58] in procurement and payment focusing on customers and suppliers
to increase to reduce working capital levels, enhance liquidity, minimize risk
and avoid late payments (47% of suppliers are paid late [59]).

  2. 2.

Financial products Accelerate trade settlement capacity [60, 10] (i.e. from
45% transactions to 90%) to reduce associated capital requirements, systemic
risk, and operational costs.

  3. 3.

Monitor transactions Keep investment portfolios relevant by re-balancing
aligned to market changes [61], while handling all the associated fees (taxes,
commissions, etc.). This can reduce transaction costs by 50% and lead to $
600k savings in trading costs for an example of 4 asset $ 1billion portfolio
[62].

  4. 4.

Customer retention Improve the process of matching companies to potential
buyers to avoid current customer churn towards automated investment banking.
This can reduce current work losses, in 2015, 26% of the $1B+ merger and
acquisitions were done without involvement of financial advisors [63].

Overall, investment banks are increasingly applying technology to automate the
trading pipeline, hiring technologists, which are 20% to 40% job openings on
the main investment banks [64]. Also, JPMorgan spends the most a year on
technology with $ 10.8 billion [65].

Many financial services firms may want to take actions that result in the best
possible outcome for a given goal. In the language of mathematical
optimization, finding the best decision or action with respect to maximizing
or minimizing given goals or objectives, is cast as maximizing or minimizing
an objective function in a decision variable, subject to constraints, often
given again by functions of a decision variable. This has extensive
applications, e.g., finding the best supply-chain route for delivery,
determining the best investment strategy for a portfolio of assets, or
increasing productivity with a number of fixed resources in operations.

Optimization problems in finance may consider a single period, where all
information are available at time 0 and one takes a one-off decision, or their
generalizations. In multi-stage problems, information become available at
multiple points in time, and also the decisions can be made at multiple points
in time (stages). In optimal control problems, one optimizes over policies,
which drive the repeated decisions. Throughout, one can work with either
discrete decisions (e.g., yes/no, number of round lots), or real-valued
decisions (e.g., price). Throughout, one can enforce the constraints given by
the Basel III regulatory framework directly, or produce the decision that
would be optimal without the constraints, and test whether these constraints
are satisfied using simulation tools, as introduced above.

Correspondingly, there is a breadth of approaches, which model active and
passive investment management. Within active investment management, one often
tries to find the optimal investment strategy striking a balance between the
expected profit and some measure of risk involved. Within passive investment
management, one can imagine index-tracking funds and their “calibration
problems”, which are based on portfolio diversification, and aim at
representing a portfolio with a large number of assets by a smaller number of
representative assets. Within auction mechanisms, the clearing of so-called
combinatorial auctions, where bids on a subset of items are accepted, is an
example of a difficult discrete-valued optimization problem. In this section,
we introduce idealized versions of these problems, where only the decision in
the next period is considered, transaction costs are ignored, and Basel III
constraints are not enforced, and the corresponding quantum algorithms.

As we will discuss shortly, different quantum algorithms have been advocated
for different optimization problem classes, e.g., the algorithms for convex
problems are different from the ones for discrete problems. In discrete
problems, e.g., we will discuss variational approaches, such as VQE and QAOA.
While for other applications quantum computing offers more clear-cut benefits
with respect to classical computing (e.g., Shor’s algorithm), in the
application of optimization algorithms these benefits are still an active
research area, see for instance [11, 66, 67, 68, 69, 12, 70, 71, 72, 73, 16,
74]. What it is fair to say is that with the advance of technology, quantum
computing will play a major role in optimization and, in some problem classes,
one will see tangible benefits, either in terms of solution quality,
computational time, or both.

TABLE II: An overview of recently proposed quantum algorithms for convex optimization. See Section IV-A for the notation, but note that $\tilde{O}$ hides polylogarithmic terms in the upper bound. Ref. | Quantum run-time |  Comment
---|---|---
[75] | $\tilde{O}(\sqrt{mn}s^{2}\mathsf{P}^{32}/\delta^{18})$ |  to error $1\pm\delta$, where $\mathsf{P}$ is linear in $n$ in general
[76] | $\tilde{O}(s^{2}\textrm{poly}(\mathsf{P}\mathsf{D}/\epsilon)(\sqrt{m}/\epsilon^{10}+\sqrt{n}/\epsilon^{12})$ |
[77] | $\tilde{O}(\sqrt{mn}s^{2}(\mathsf{P}\mathsf{D}/\epsilon)^{8})$ |  where $\mathsf{P}$ is linear in $n$ in general
[78] | $\tilde{O}((\sqrt{mn}s(\mathsf{P}\mathsf{D}/\epsilon)^{4})$ |  where $\mathsf{P}$ is linear in $n$ in general, and quantum-read/classical-write
|  |  RAM can be accessed in constant time
[79] | $\tilde{O}(n^{2.5}\mu\kappa^{3}\log{1/\epsilon})$ |  where $\kappa$ goes to infinity for all instances

###  IV-A Problem classes: convex problems

First, we consider convex optimization, which encompasses linear programming
(LP), quadratic programming (QP), and semidefinite programming (SDP). Convex
optimization [80] is a sub-class of continuous optimization problems, where
the decision variables are continuous, and it has been advocated for a large
variety of applications, among which finance problems [81].

Not surprisingly, much of the recent interest in quantum algorithms for
continuous optimization has focused on approaches to solving convex
optimization problems, and in particular semidefinite programming (SDP). A SDP
can be mathematically modelled as:

$\displaystyle\operatorname{inf}\ \langle C,X\rangle\textrm{ s.t.
}\mathcal{A}X=b,X\succeq_{\mathcal{K}}0$ (16)

where cone $\mathcal{K}$ is the cone of positive semidefinite symmetric
$n\times n$ matrices $\mathcal{S}_{+}^{n}$, i.e.,
$\\{X=X^{\intercal}\in\mathbb{R}^{n\times n}|\ X\text{ is positive
semidefinite}\\}$, and $\mathcal{A}\colon\mathcal{S}^{n}\to\mathbb{R}^{m}$ is
a linear operator between $\mathcal{S}_{+}^{n}$ and $\mathbb{R}^{m}$:

$\displaystyle X$ $\displaystyle\mapsto\begin{pmatrix}\langle
A_{1},X\rangle\\\ \dots\\\ \langle A_{m},X\rangle\end{pmatrix}$

This is a proper generalization of linear programming (LP), second-order cone
programming (SOCP), and convex cases of quadratically-constrained quadratic
programming (QCQP), and hence of considerable practical interest.

Within classical algorithms, there exist polynomial-time algorithms that can
solve SDP. In particular, there are classical upper bounds on the run time as

$\mathcal{O}(m(m^{2}+n\omega+m\mathrm{nz})\textrm{polylog}(m,n,\mathsf{P},1/\epsilon)),$

where, as said, $\mathcal{O}(\cdot)$ indicates the big-$\mathcal{O}$ notation,
$n$ is the dimension of the problem, $\omega\in[2,2.373)$ is the exponent for
matrix multiplication, $m$ is the number of constraints, and $\mathrm{nz}$ is
the maximal number of non-zero entries per row of the input matrices.
$\mathsf{P}$ is an upper bound on the trace of an optimal primal solution of
an SDP, which could be seen as bound on a diameter of a ball outscribed to
feasible solutions, in a suitable norm. This bound shows that SDPs can be
approximated to any $\epsilon$ in polynomial time classically.

As for quantum algorithms, the early papers of [75] and [77] and [78]
quantized the so-called multiplicative-weight-update (MWU) algorithm of Arora
and Kale and variants by Hazan. As it has been shown in [77, Appendix E], in
the MWU algorithm, $\frac{\mathsf{P}\mathsf{D}}{\epsilon}$ should be seen as
an important parameter ($\mathsf{D}$ being the dual counterpart of
$\mathsf{P}$), as one can trade-off dependence on one of the three individual
parameters for the dependence on the others.

Subsequently, the work in [79] attempted a translation of primal-dual
interior-point methods to quantum computers, but due to their reliance on
solving linear systems, ended up with a bound dependent on the condition
number $\kappa$ of the Karush-Kuhn-Tucker (KKT) system, which goes to infinity
for all instances, by the design of the method, which may be not ideal in
practice.

Finally, in [82], the authors study the relationship of several oracles useful
in subgradient algorithms, but do not claim a run-time of a particular
algorithm for SDPs.

The key results are summarized in Table II. As it can be observed, some of the
quantum algorithms listed report scaling with $O(\sqrt{mn})$ [75] or even
$O(\sqrt{m}\ \textrm{poly}(\log(m),\log n))$ [76]. However, these these upper
bounds hide the diameters of balls outscribed to the primal and dual
solutions. That is: these upper bounds assume that parameters $\mathsf{P}$ and
$\mathsf{D}$ are constants independent of dimension, which could be however
hard to satisfy in practice.

In fact, if ones assumes that $\mathsf{P}$ and $\mathsf{D}$ are dependent on
the dimension of the problem, then lower bounds on the run-time of quantum
algorithms can be derived, e.g., for continuous Markowitz portfolio
optimization problems in Section IV-B.

Before moving on to an actual finance application, it is useful to briefly
outline the quantum part of a quantum SDP algorithm. We focus here on the one
of [75], since it seems to be the one that has spurred much of the following
research. As said, the authors in [75], quantize the classical MWU algorithm
for solving SDPs. In particular, they replace two steps of the classical
algorithm by quantum subroutines that are more efficient than classical ones.
Consequently, the quantum SDP algorithm is not purely quantum, which is also
the case for VQE in combinatorial optimization. The steps that are replaced
are as follows. First, it turns out that one can use a “Gibbs sampler” to
prepare the new primal candidate as a $log(n)$-qubit quantum state in much
less time than needed to compute it as an $n\times n$ matrix. Second, one can
efficiently implement an oracle that is needed in the algorithm based on a
number of copies of the quantum state, and using those copies to estimate
trace operations. The resulting oracle is weaker than what is used
classically, in the sense that it outputs a sample rather than the whole
vector (as typical in quantum computing). However, such sampling still
suffices to make the algorithm work. The interested reader is referred to [77,
73] for more technical details.

###  IV-B Modern Portfolio Management - Active Investment Management:
continuous case

Let us now consider modern portfolio management, and develop lower bounds on
the run-time of any quantum algorithm in the quantum query model of Beals et
al. [83], where quantum computation with $T$ queries is a sequence
interleaving $T$ unitary and $T$ query (oracle) transformations, with a
measurement at the end. These lower bounds on the run-time are generally based
on lower bounds on parameters
$\mathsf{P},\mathsf{D}=\Theta(\min\\{n,m\\}^{2})$, as discussed in Section
IV-A, and suggest that the quantum speed-up of MWU algorithms [75, 77, 78] may
be limited in practice.

In modern portfolio theory, one often assumes that there are $n$ possible
assets, and a number $m$ of forecasts of their returns
$b_{i}\in\mathbb{R}^{n}$, $1\leq i\leq m$ based on some historical returns
$c\in\mathbb{R}^{n}$, with a known covariance matrix
$\Sigma\in\mathbb{R}^{n\times n}$ of the returns. Minimization of the risk
subject to lower bounds $\mu_{i}$ on the forecast returns leads to:

$\displaystyle\min_{w\in\mathbb{R}_{+}^{n}}w^{\intercal}\Sigma w\quad\textrm{
s.t. }b_{i}^{\intercal}w\geq\mu_{i},\quad\forall\,1\leq i\leq m$ (17)

possibly with normalization such as $\sum_{j=1}^{n}w_{i}=1$ or similar. In the
spirit of Markowitz, one may consider a linear combination of the returns and
the risk:

$\displaystyle\max_{w\in\mathbb{R}_{+}^{n}}c^{{\intercal}}w-qw^{\intercal}\Sigma
w\quad\textrm{ s.t. }b_{i}^{\intercal}w\geq\mu_{i},\quad\forall\,1\leq i\leq
m.$ (18)

One can also formulate a Lagrangian of the Markowitz model above and maximize
$c^{\intercal}w-qw^{\intercal}\Sigma w$, where the higher $q\geq 0$, the more
risk-averse the portfolio will be.

In any case, due to the general result that there exist problem instances for
which complexity of every quantum LP-solver (and hence also SDP-solver) is the
same as classical [77], there are instances of Markowitz Portfolio Management
(18) with $n$ assets and $m$ forecasts of the returns, for which a quantum
algorithm has the same complexity of a classical one. This has to be taken as
an understanding that quantum algorithms may help in some instances of
Markowitz Portfolio Management but not in others, depending on the actual
input data.

###  IV-C Problem classes: combinatorial problems

We move now to overview combinatorial problems and quantum algorithms that
have been advocated for them. Combinatorial optimization problems are the ones
for which the decision variables can be also discrete. Combinatorial problems
are in general non-convex and not solvable with polynomial-time algorithms,
classically. In the quantum domain, variational algorithms for general mixed-
binary constrained optimization problems have been studied, and we will
overview them as well as apply them for financial problems [84]. Firstly, we
will look at Quadratic Binary Unconstrained Optimization (QUBO), where
VQE/QAOA heuristic approaches have been advocated on noisy quantum devices
[12, 24]. VQE stands for variational quantum eigensolver, while QAOA stands
for quantum approximate optimization algorithm. Then, we will explore how the
classical alternating direction method of multipliers (ADMM) can help solving
certain classes of mixed-binary constrained optimization problems [11]. We
note that, currently, there is no theoretical guarantee that variational
algorithms on quantum devices can achieve significant speed-ups for QUBOs and
the algorithms reported in this section are used as heuristics. On the other
hand, variational algorithms do have non-trivial provable guarantees and they
are not efficiently simulatable by classical computers. They are thus
appealing algorithms to explore on near-term quantum machines [70].

###  IV-D Variational approaches for Quadratic Binary Unconstrained
Optimization (QUBO)

The attempts to solve mathematical optimization problems on early generation
of universal quantum computers have mainly focused on variational approaches
[85, 86, 87]. In broad terms, a variational approach works by choosing a
parametrization of the space of quantum states that depends on a relatively
small set of parameters, then using classical optimization routines to
determine values of the parameters corresponding to a quantum state that
maximizes or minimizes a given utility function. Typically, the utility
function is given by a Hamiltonian encoding the total energy of the system, to
be minimized. The variational theorem then ensures that the expectation value
of the Hamiltonian is greater than or equal to the minimum eigenvalue of the
Hamiltonian. A large problem class tackled by such variational approaches is
that of quadratic unconstrained binary optimization problems (QUBO):

$\displaystyle\min_{x}$ $\displaystyle c^{\intercal}x+x^{\intercal}Qx$ s.t.:
$\displaystyle x\in\\{0,1\\}^{n},$ with
$c\in\mathbb{R}^{n},Q\in\mathbb{R}^{n\times n}$

Each QUBO can be transformed into an Ising model with Hamiltonian constituted
as a summation of weighted tensor products of $Z$ Pauli operators, i.e.,
$Z=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$, by mapping the binary variables
$x$ to spin variables $y\in\\{-1,1\\}$, i.e., $x=\frac{y+1}{2}$. In case
equality constraints $Ax=b$ are present in the mathematical programming
formulation, a QUBO can still be devised by adding a quadratic penalization
$\alpha\lVert Ax-b\rVert^{2}$ to the objective function, as a soft-constraint
in an Augmented Lagrangian fashion [88, 89, 12].

A typical variational approach on quantum devices, such as VQE [23] would
involve the following two key steps in solving a QUBO, given its Ising
Hamiltonian $H\in\mathbb{C}^{n\times n}$. First, one would parametrize the
quantum state via a small set of rotation parameters $\theta$: each state can
then be expressed as $|\psi(\theta)\rangle=U(\theta)|0\rangle$, where
$U(\theta)$ is the parametrized quantum circuit applied to the initial state
$|0\rangle$. The variational approach would then aim at solving
$\min_{\theta}\langle\psi(\theta)|H|\psi(\theta)\rangle$. Such optimization
can be performed in a setting that uses a classical computer running an
iterative algorithm to select $\theta$, and a quantum computer to compute
information about $\langle\psi(\theta)|H|\psi(\theta)\rangle$ for given
$\theta$ (e.g., its gradient). The algorithm outline of VQE is reported in
Algorithm 1.

Algorithm 1 Outline of VQE

0: Hamiltonian $H$. Set $\theta=\theta_{0}$

1: while Error tolerance is unmet: do

2: Quantum part:

  * •

Form variational state $\ket{\psi({\theta})}=U(\theta)\ket{0}$

  * •

Compute information about $\lambda=\langle\psi(\theta)|H|\psi(\theta)\rangle$

3: Classical part:

  * •

Update $\theta$ via a classical optimization algorithm (e.g., COBYLA, SPSA,
etc.)

  * •

Compute the error metric

4: end while

5: return $\lambda,\theta$

Another variational approach on quantum devices is QAOA (or Quantum
Approximate Optimization Algorithm) [70], which can be seen as a
generalization of VQE. First, one would define rotation parameters
$\theta=[\theta_{1},\ldots,\theta_{d}]$ and
$\beta=[\beta_{1},\ldots,\beta_{d}]$ together with the Ising Hamiltonian
$H\in\mathbb{C}^{n\times n}$, and a mixing Hamiltonian
$H_{X}\in\mathbb{C}^{n\times n}$ defined as a summations of $X$ Pauli
operators. Then, one would construct the quantum state as

$\ket{\psi(\theta,\beta)}=\exp(-i\beta_{d}H_{X})\exp(-i\theta_{d}H)\cdots\\\
\exp(-i\beta_{1}H_{X})\exp(-i\theta_{1}H)\ket{0}=U(\theta,\beta)\ket{0}.$ (19)

The variational approach would then aim at solving
$\min_{\theta,\beta}\langle\psi(\theta,\beta)|H|\psi(\theta,\beta)\rangle$.
Such optimization can be performed in a setting that uses a classical computer
running an iterative algorithm to select $\theta,\beta$, and a quantum
computer to compute information about
$\langle\psi(\theta,\beta)|H|\psi(\theta,\beta)\rangle$ for given
$\theta,\beta$ (e.g., its gradient). The algorithm outline of QAOA is reported
in Algorithm 2.

Algorithm 2 Outline of QAOA

0: Hamiltonian $H$, mixer Hamiltonian $H_{X}$. Set $\theta=\theta_{0}$,
$\beta=\beta_{0}$

1: while Error tolerance is unmet: do

2: Quantum part:

  * •

Form variational state $\ket{\psi({\theta,\beta})}=U(\theta,\beta)\ket{0}$

  * •

Compute information about
$\lambda=\langle\psi(\theta,\beta)|H|\psi(\theta,\beta)\rangle$

3: Classical part:

  * •

Update $\theta,\beta$ via a classical optimization algorithm (e.g., COBYLA,
SPSA, etc.)

  * •

Compute the error metric

4: end while

5: return $\lambda,\theta,\beta$

###  IV-E Combinatorial Application 1: Active Investment Management, Portfolio
Optimization

To illustrate the VQE and the QAOA in the context of portfolio optimization we
solve a combinatorial optimization problem in which we seek to allocate
capital to a subset of $B=3$ assets selected from a larger investment universe
with size $n=6$ [87]. In particular, we will solve the combinatorial problem:

$\min_{x\in\\{0,1\\}^{n}}qx^{\intercal}\Sigma
x-\mu^{\intercal}x,\quad\textrm{subject to: }1^{\intercal}x=B,$ (20)

where we use the following notation:

  * •

$x\in\\{0,1\\}^{n}$ denotes the vector of binary decision variables, which
indicate which assets to pick ($x_{i}=1$) and which not to pick ($x_{i}=0$);

  * •

$\mu\in\mathbb{R}^{n}$ defines the expected returns for the assets;

  * •

$\Sigma\in\mathbb{R}^{n\times n}$ specifies the covariances between the
assets;

  * •

$q>0$ controls the risk appetite of the decision maker;

  * •

and $B$ denotes the budget, i.e. the number of assets to be selected out of
$n$.

We also assume the following simplifications: _i)_ all assets have the same
price (normalized to 1), _ii)_ the full budget $B$ has to be spent, i.e. one
has to select exactly $B$ assets. With these assumptions the portfolio
optimization problem corresponds to building a portfolio by selecting a subset
of $B$ assets from the available $n$ assets and equally allocating capital to
the $B$ assets. To map the problem (20) to a QUBO, the equality constraint
$1^{\intercal}x=B$ is mapped to a penalty term $(1^{\intercal}x-B)^{2}$ which
is scaled by a parameter and subtracted from the objective function. The
resulting problem can be mapped to a Hamiltonian whose ground state
corresponds to the optimal solution.

We use the statevector simulator in Qiskit Aer [54] as backend and compare the
results to a diagonalization of the Ising Hamiltonian which encodes the
portfolio optimization problem. The VQE and the QAOA both produce variational
states, which, when sampled from, result with high probability in an asset
selection that respects the budget constraint as shown by the fact that the
three most probable states all select three assets, see Tab. III. Furthermore,
the selected states are either optimal or near optimal as seen by comparing
them with the state resulting from the diagonalization in Tab. III. The
probability to sample near optimal states with QAOA are lower than for VQE,
see Tab. III, which may indicate that deeper QAOA variational forms are needed
[90] or that the COBYLA optimizer we used was trapped in a local minimum [91,
68]. For such a small problem size the diagonalization runs in less time than
simulations of the VQE and the QAOA. Performing VQE and QAOA on quantum
hardware would require even more time. However, such classical brute force
approach scales exponentially in the number of assets and, even for a few tens
of assets ($n\sim 30-40$), we expect it not to be a practically viable
approach.

TABLE III: Comparison of the VQE solution, obtained with an $R_{y}$ variational form of depth 3, a depth $p=4$ QAOA solution, and a diagonalization of the Hamiltonian of the portfolio optimization problem. Assets selected shows the candidate solution where a $1$ in position $i$ indicates that asset $i$ was selected. The energy is the energy of the selected state and the probability shows the likelihood of sampling the selected assets from the quantum state created by the quantum algorithm. Assets selected | Energy | Probability
---|---|---
Diagonalization
$[1\,0\,1\,0\,1\,0]$ | -0.0036 | 1.0000
VQE
$[0\,1\,0\,0\,1\,1]$ | -0.0021 | 0.4431
$[0\,1\,0\,1\,1\,0]$ | -0.0021 | 0.3660
$[1\,1\,0\,0\,1\,0]$ | -0.0036 | 0.1154
QAOA
$[1\,1\,0\,0\,1\,0]$ | -0.0036 | 0.0487
$[1\,0\,1\,0\,1\,0]$ | -0.0036 | 0.0486
$[1\,0\,0\,1\,1\,0]$ | -0.0031 | 0.0485

In a second example, we optimize the portfolio for different values of the
risk-return trade-off parameter $q$ without the budget constraint. We compare
solutions obtained with VQE and solutions obtained from a classical exhaustive
search. The most probable asset selections obtained from the state of the VQE
closely follow the efficient frontier, therefore maximizing return and
minimizing risk, see Fig. 8.

Figure 8: Reconstruction of the efficient frontier using an exhaustive search
with exponential scaling (blue line) and the VQE (green triangles). Both
methods find the optimal portfolios, i.e. which maximize return and minimize
risk, out of the 64 possible asset combinations (black dots). Both quantum and
classical algorithms are run several times with different risk-return trade-
off values $q$ to find the efficient frontier.

###  IV-F Combinatorial Application 2: Passive Investment Management,
Portfolio Diversification

In passive investment management one of the main challenges is to build a
diverse portfolio with a relatively small number of assets that track the
dynamics of a portfolio with a much larger number of assets. This portfolio
diversification makes it possible to mimic the performance of an index (or a
similarly large set of assets) with a limited budget, at limited transaction
costs. The purchase of all assets in the index may be impractical for a number
of reasons: the total of even a single round lot per asset may amount to more
than the assets under management, the large scale of the index-tracking
problem with integrality constraints may render the optimization problem
difficult, and the transaction costs of the frequent rebalancing to adjust the
positions to the weights in the index may render the approach expensive. Thus,
a popular approach is to select a portfolio of $q$ assets that represent the
market with $n$ assets, where $q$ is significantly smaller than $n$, but where
the portfolio replicates the behavior of the underlying market. To determine
how to group assets into $q$ clusters and how to determine which $q$ assets
should represent the $q$ clusters amounts to solving a large-scale
optimization problem.

As discussed in [81], we describe a mathematical model that clusters assets
into groups of similar ones and selects one representative asset from each
group to be included in the index fund portfolio. The model is based on the
following data, which we will discuss in more detail later:

$\rho_{ij}=\textrm{similarity}\,\textrm{between}\,\textrm{stock}\,i\,\textrm{and}\,\textrm{stock}\,j.$

For example, $\rho_{ii}=1$, $\rho_{ij}\leq 1$ for $i\neq j$ and $\rho_{ij}$ is
larger for more similar stocks. An example of this is the correlation between
the returns of stocks $i$ and $j$. It allows for similarity measures between
time-series beyond the covariance matrix. Consider, for instance, a company
listed both in London and New York. Although both listings should be very
similar, only parts of the time series of the prices of the two listings will
overlap, because of the partial overlap of the times the markets open. Instead
of covariance, one can consider, for example, dynamic time warping of [92] as
a measure of similarity between two time series, which allows for the fact
that for some time periods, the data are captured by only one of the time
series, while for others, both time series exhibit the similarity due to the
parallel evolution of the stock price.

The problem that we are interested in solving is:

$(M)\quad
f=\max_{x_{ij},y_{j}}\,\,\sum_{i=1}^{n}\sum_{j=1}^{n}\rho_{ij}x_{ij}$

subject to the clustering constraint:

$\sum_{j=1}^{n}y_{j}=q,$

to consistency constraints:

$\displaystyle\displaystyle\sum_{j=1}^{n}x_{ij}=1,$
$\displaystyle\forall\,i=1,\ldots,n,$ $\displaystyle x_{ij}\leq y_{j},$
$\displaystyle\forall\,i=1,\ldots,n;\,j=1,\ldots,n,$ $\displaystyle
x_{jj}=y_{j},$ $\displaystyle\forall\,j=1,\ldots,n,$

and integral constraints:

$\quad x_{ij},y_{j}\in\\{0,1\\},\,\forall\,i=1,\ldots,n;\,j=1,\ldots,n.$

The variables $y_{j}$ describe which stocks $j$ are in the index fund
($y_{j}=1$ if $j$ is selected in the fund, $0$ otherwise). For each stock
$i=1,\dots,n$, the variable $x_{ij}$ indicates which stock $j$ in the index
fund is most similar to $i$ ($x_{ij}=1$ if $j$ is the most similar stock in
the index fund, $0$ otherwise).

The first constraint selects $q$ stocks in the fund. The second constraint
imposes that each stock $i$ has exactly one representative stock $j$ in the
fund. The third and fourth constraints guarantee that stock $i$ can be
represented by stock $j$ only if $j$ is in the fund. The objective of the
model maximizes the similarity between the $n$ stocks and their
representatives in the fund. Different cost functions can also be considered.

From $(M)$ one can construct a binary polynomial optimization with equality
constraints only, by substituting the $x_{ij}\leq y_{j}$ inequality
constraints with the equivalent equality constraints $x_{ij}(1-y_{j})=0$. Then
the problem becomes:

$\displaystyle\max_{x_{ij},y_{j}}$
$\displaystyle\,\,\displaystyle\sum_{i=1}^{n}\displaystyle\sum_{j=1}^{n}\rho_{ij}x_{ij}$
(21a) s. t.: $\displaystyle\displaystyle\sum_{j=1}^{n}x_{ij}=1,$
$\displaystyle\forall\,i=1,\ldots,n$ (21c) $\displaystyle x_{ij}(1-y_{j})=0,$
$\displaystyle\forall\,i=1,\ldots,n,$ $\displaystyle\forall\,j=1,\ldots,n,$
$\displaystyle x_{jj}=y_{j},$ $\displaystyle\forall\,j=1,\ldots,n.$ (21d)

We can now construct the Ising Hamiltonian (QUBO) by penalty methods
(introducting a penalty coefficient $A$ for each equality constraint) as

$\\!\\!\\!H=\sum_{i=1}^{n}\sum_{j=1}^{n}\rho_{ij}x_{ij}+A\Big{(}\sum_{j=1}^{n}y_{j}-q\Big{)}^{2}+\sum_{i=1}^{n}A\Big{(}\sum_{j=1}^{n}x_{ij}-1\Big{)}^{2}\\\
+\sum_{j=1}^{n}A(x_{jj}-y_{j})^{2}+\sum_{i=1}^{n}\sum_{j=1}^{n}A\left(x_{ij}(1-y_{j})\right).$
(22)

For the simulation in Qiskit, we use three assets ($n=3$) and two clusers
($q=2$), this leads to a $12$-qubit Hamiltonian. We solve the problem
classical with CPLEX and on the quantum computer with VQE (with depth 7 and
full entanglement).

In Figure 9, we report the results that we obtain conveniently (and
arbitrarily) displayed in a two dimensional graph for visualization purposes.
Solution shows the selected stocks via the stars and in green the links (via
similarities) with other stocks that are represented in the fund by the linked
stock. As we see, both for classical and quantum, we can find a feasible
solution for our diversification (clustering and selecting two stocks, while
associating the third to a selected one), although the classical algorithm
here finds a slightly better solution (the classical benefit fares at $2.001$,
while the quantum one at $2.000$). This is reasonable for such small problem
instance, since the classical solver can be run to find the exact solution,
while VQE is a heuristic and may find less optimal solutions, but this might
not be the case when the classical solver will not be able to run at
optimality for larger size problems.

Figure 9: Portfolio selection for classical and quantum algorithm. The stocks
are represented in an arbitrary two dimensional plane for viualization
purposes. The selected stocks are indicated with red stars, while the green
link indicates the association of the unselected stock to a selected one.
Classical and quantum solution are different but fare very similarly in terms
of benefit.  Algorithm 3 $3$-ADMM-H mixed-binary heuristic

0: Initial choice of $x_{0},\bar{x}_{0},y_{0},\lambda_{0}$. Choice of
$\varrho,\beta,c>0$, tolerance $\epsilon>0$, and maximum number of iterations
$K_{\text{max}}$.

1: while $k<K_{\text{max}}$ and
$\|A_{0}x_{k}-A_{1}\bar{x}_{k}-y_{k}\|<\epsilon,$ do

2: First block update (QUBO) on the quantum device:  $\displaystyle x_{k}=$
$\displaystyle\operatorname*{arg\,min}_{x\in\\{0,1\\}^{n}}\,\,q(x)+\frac{c}{2}\|Gx-b\|^{2}_{2}+$
$\displaystyle+\lambda_{k-1}^{\intercal}A_{0}x+\frac{\varrho}{2}\|A_{0}x+A_{1}\bar{x}_{k-1}-y_{k-1}\|^{2}$
(23)

3: Second block update (Convex) on the classical device:
$\displaystyle\bar{x}_{k}$
$\displaystyle=\operatorname*{arg\,min}_{\bar{x}\in\mathbb{R}^{m}}\,\,f_{1}(\bar{x})+\lambda_{k-1}^{\intercal}A_{1}\bar{x}+$
$\displaystyle\frac{\varrho}{2}\|A_{0}x_{k}+A_{1}\bar{x}-{y}_{k-1}\|^{2}$ (24)

4: Third block update (Convex+quadratic) on the classical device:
$y_{k}=\operatorname*{arg\,min}_{y\in\mathbb{R}^{n}}\,\,\frac{\beta}{2}\|y\|^{2}_{2}-\lambda_{k-1}^{\intercal}y+\frac{\varrho}{2}\|A_{0}x_{k}+A_{1}\bar{x}_{k}-{y}\|^{2}$

5: Dual variable update on the classical device:
$\lambda_{k}=\lambda_{k-1}+\varrho(A_{0}x_{k}+A_{1}\bar{x}_{k}-y_{k})$

6: Compute merit value:  $\displaystyle\eta_{k}$
$\displaystyle=q(x_{k})+\phi(\bar{x}_{k})+$
$\displaystyle+\mu(\max(g(x_{k}),0)+\max(l(x_{k},\bar{x}_{k}),0))$ (25)

7: end while

8: return $x_{{k}^{*}},\bar{x}_{{k}^{*}},y_{{k}^{*}},$ with
${{k}^{*}}=\min_{k}\eta_{k}.$

Figure 10: Illustration diagram of the $3$-ADMM-Happroach. There are two
nested loops for the selected implementation, specifically the outer ADMM
loop, and the inner VQE loop (Note VQE can be substituted via QAOA
seamlessly).

###  IV-G Multi-block ADMM heuristic for Mixed-Binary Optimization

We move on to Mixed-Binary Optimization (MBO) formulations. In a general MBO
problem, the decision maker faces binary and continuous decisions, subject to
equality and inequality constraints. MBO formulations enable to tackle finance
problems, such as the combinatorial auction problem, which is the scope of the
Section IV-H.

In order to introduce solvers for MBO, we consider the following reference MBO
problem $(P)$:

$\displaystyle\min_{x\in\mathcal{X},u\in\mathcal{U}\subseteq\mathbb{R}^{l}}\ $
$\displaystyle q(x)+\varphi(u)$ (26a) $\displaystyle\mathrm{s.t.:~{}}$
$\displaystyle Gx=b,\quad g(x)\leq 0$ (26c) $\displaystyle\ell(x,u)\leq 0,$

with the corresponding functional assumptions.

######  Assumption 1.

The following assumptions hold:

  * •

Function $q:\mathbb{R}^{n}\to\mathbb{R}$ is quadratic, i.e.,
$q(x)=x^{\intercal}Qx+a^{\intercal}x$ for a given symmetric squared matrix
$Q\in\mathbb{R}^{n}\times\mathbb{R}^{n},Q=Q^{\intercal}$, and vector
$a\in\mathbb{R}^{n}$;

  * •

The set $\mathcal{X}=\\{0,1\\}^{n}=\\{x_{(i)}(1-x_{(i)})=0,\forall i\\}$
enforces the binary constraints;

  * •

Matrix $G\in\mathbb{R}^{n}\times\mathbb{R}^{n^{\prime}}$, vector
$b\in\mathbb{R}^{n^{\prime}}$, and function $g:\mathbb{R}^{n}\to\mathbb{R}$ is
convex;

  * •

Function $\varphi:\mathbb{R}^{l}\to\mathbb{R}$ is convex and $\mathcal{U}$ is
a convex set;

  * •

Function $\ell:\mathbb{R}^{n}\times\mathbb{R}^{l}\to\mathbb{R}$ is _jointly_
convex in $x,u$.

In order to solve MBO problems, [11] proposed heuristics for $(P)$ based on
the Alternating Direction Method of Multipliers (ADMM) [93]. ADMM is an
operator splitting algorithm with a long history in convex optimization, and
it is known to have residual, objective and dual variable convergence
properties, provided that convexity assumptions are holding [93].

The method of [11] (referred to as $3$-ADMM-H, and displayed in Figure 10)
leverages the ADMM operator-splitting procedure to devise a decomposition for
certain classes of MBOs into:

  * •

a QUBO subproblem to be solved by on the quantum device via variational
algorithms, such as VQE or QAOA, described in Section IV-D;

  * •

a continuous convex constrained subproblem, which can be efficiently solved
with classical optimization solvers [80].

Algorithm 3 reports the $3$-ADMM-H algorithm, along with stopping criteria and
evaluation metrics. A comprehensive discussion on the conditions for
convergence, feasibility and optimality of $3$-ADMM-H is out of the scope of
the present document and can be found in [11]. Combinatorial auction (A)
belongs to the class of MBOs represented by (P) and can be solved by
$3$-ADMM-H. Simulations on representative instances are conducted in Section
IV-H.

###  IV-H Combinatorial Application 3: Auctions

Both governments and private issuers finance its activities, in part, by the
sale of marketable securities. The issuer often uses an auction process to
sell such marketable securities and determine their parameters (such as
yield). For example, the United States (U.S.) treasury issued over $10T (ten
trillion U.S. dollars) in securities in 2018. Many further auction mechanisms
abound in electrical energy markets, pollution management, and within airport
operations (airport landing slots). Some of these auctions may be
combinatorial, in the sense that the value that a bidder has for a set of
items may not be the sum of the values that he has for individual items. It
may be more or it may be less.

Combinatorial auctions allow the bidders to submit bids on subsets
(combinations) of items. Specifically, let $M=\\{1,2,\ldots,m\\}$ be the set
of items that the auctioneer has to sell. A bid is a pair
$B_{j}=(S_{j},p_{j})$ where $S_{j}\subseteq M$ is a non empty set of items and
$p_{j}$ is the price offer for this set. Suppose that the auctioneer has
received $n$ bids $B_{1},B_{2},\ldots,B_{n}$. How should the auctioneer
determine the winners in order to maximize his revenue? This can be formulated
as an integer program. To render the problem a bit more interesting, we
consider the case in which (as in some auctions) there are multiple
indistinguishable units of each item for sale. A bid in this setting is
defined as
$B_{j}=(\lambda_{1}^{j},\lambda_{2}^{j},\ldots,\lambda_{m}^{j};p_{j})$ where
$\lambda_{i}^{j}$ is the desired number of units of item $i$ and $p_{j}$ is
the price offer. Let $x_{j}$ be a binary variable that takes the value $1$ if
bid $B_{j}$ wins, and $0$ if it loses. The auctioneer maximizes his revenue by
solving the integer program (A):

$\displaystyle\max_{x_{j}}$ $\displaystyle\quad\sum_{j=1}^{n}p_{j}x_{j}$ (27)
s.t.: $\displaystyle\sum_{j:i\in S_{j}}\lambda_{i}^{j}x_{j}\leq
u_{i},\quad\textrm{for }i=1,\ldots,m$ (29) $\displaystyle
x_{j}\in\\{0,1\\},\quad\textrm{for }j=1,\ldots,n,$

where $u_{i}$ is the number of units of item $i$ for sale [81].

The presence of inequality constraints (29) makes a reformulation of (A) into
a QUBO not possible, hence the VQE algorithm described in Section IV-D is not
directly applicable. We here report results obtained by solving (A) with the
$3$-ADMM-H heuristic described in Section IV-G.

For simulation purposes, an instance with $m=3$ items and $n=16$ bids with
randomly generated profits has been created. For each item, $6$ units are
available. The number of units of the items in each bid has been randomly
sampled from the interval $[1,6]$. This means that not all bids are
necessarily feasible if more than one object is in the bid. Because the
decision of accepting a bid $j$ is a binary decision $x_{j}$, the number of
bids is the number of qubits the algorithm $3$-ADMM-H necessitates. The
optimal solution, found by solving Problem (A) via the classical optimization
solver IBM ILOG CPLEX, consist of accepting bids
$B_{0}=\\{0\\},B_{1}=\\{1\\},B_{4}=\\{1,2\\}$ with a profit of $24$. The
$3$-ADMM-H algorithm has been tested on the instance by choosing VQE as
quantum solver in Qiskit Aqua and Constrained Optimization By Linear
Approximation (COBYLA) [94] as classical VQE optimizer with $20$ maximum
iterations. The qasm_simulator has been used as Qiskit Aer backend for the
simulations on quantum devices. The ADMM parameters $\rho$ and $\beta$ have
been set to $12$ and $11$ respectively: this is to leverage the convergence
properties described in [11] for $\rho>\beta$. When run on classical devices,
the first block update is performed with the CPLEX solver.

The $3$-ADMM-H solution with CPLEX as QUBO solver is
$B_{1}=\\{1\\},B_{3}=\\{0,2\\},B_{4}=\\{1,2\\},$ with a profit of $27$, and a
violation of constraints (29) of $2$. Setting VQE as QUBO solver makes
$3$-ADMM-H converge to the same solution in $43$ iterations. The residuals
$r_{k}=A_{0}x_{k}-A_{1}\bar{x}_{k}-y_{k}$ are reported for the classical and
quantum simulations, in Figures 11(a) and 11(b). Residuals are not guaranteed
to decrease in each $3$-ADMM-H iteration. The convergence guarantees of
$3$-ADMM-H are not valid for inexact QUBO solvers, such as the currently
available quantum algorithms. However, the convergence curves show that
$3$-ADMM-H terminates in a finite number of iterations, even when the QUBO
solver is inexact. Hence, $3$-ADMM-H exhibits a certain degree of tolerance to
inexact computations. This corroborates the empirical findings of [11] on
packing problems.

(a)

(b)

Figure 11: Convergence of the residuals for $3$-ADMM-H algorithm, in the
classical (a) and quantum (b) simulations. The simulation with quantum QUBO
solver shows that, even with an inexact QUBO solver, $3$-ADMM-H can reach
convergence in a finite, and relatively low, number of iterations.

The $3$-ADMM-H algorithm proposes a decomposition of a mixed-binary
optimization problem, in which the most computationally demanding part is
solving the QUBO subproblem (23). The advantage of using $3$-ADMM-H algorithm
over classical optimization solvers, such as CPLEX, lies in leveraging quantum
algorithm to tackle QUBO subproblems.

##  V Machine Learning

Finally, in this section we discuss machine learning problems where quantum
algorithms may demonstrate an advantage.

Machine learning focuses on finding relations in data and building assumptions
around them for (i) prediction by anticipating future events from historic
data, or to (ii) classify data by dividing an end result into different
categories, or to (iii) find patterns by the discovery of regularities or
anomalies in data. In finance, such approaches are important in many financial
problems that deal with uncertainty in the future evolution of asset prices
and risk. For example, the investment management strategies and optimization
in the previous section make use of the estimation of future risks and asset
prices that can be obtained from the output of machine learning algorithms.
Banks can estimate the risk level of their customers’ loans by credit scoring
which can be formulated as classification [95] and/or regression problem based
on the rich features of customers, such as, age, salary, historical payment,
micro and macro economic indicators and so on. Financial institutions can also
detect frauds by finding patterns that deviates greatly from normal behavior
by classification and/or anomaly detection [96, 97]. Such machine learning
tasks are known to face the curse of dimensionality as there are much more
features available to model customers. Principal component analysis (PCA) and
variational autoencoder (VAE) [98] are some of the popular methods for
dimensionality reduction when dealing with high-dimensional features.

To summarize machine learning problems at each stage of the customer life
cycle (see Figure 3):

  1. 1.

Customer identification (and scoring) Refine customer rating and segmentation
to improve KYC (Know Your Customer) and avoid non-compliance annual penalties,
that have grown to $ 8.3 Million annually by 2018 [99].

  2. 2.

Financial products Increase credit scoring realism to improve customer
targeting and align product offering:

     * •

Avoid NPL (Non-Performing Loan) costs that are still increasing in many
European economies [100].

     * •

Increase customer interaction with the bank resulting in more profits.

     * •

Improve recommendation techniques to target customers prone to accept them.

  3. 3.

Monitor transactions Improve suspicious transaction signals to decrease false
alerts, that today cost $ 4 trillion due to 75% to 90% false positives in AML
(Anti Money Laundering) and credit card fraud alerts.

  4. 4.

Customer retention Maximize engagement to avoid customer churn rates to new
entrants, 25% of SMBs (Small-Medium Business) are turning to FinTech companies
for ease and speed of completing loan applications [101].

Overall, Artificial Intelligence (AI) and Machine Learning (ML) are of deep
interest for financial institutions, with a current global spending in the
banking industry worth of $ 3.3 Billion in 2018[102] with the hopes to build
better classification models that will improve customer service in external
facing and internal activities. IDC reported that of global spending on AI
worth $ 50.1 Billion in 2020, which is expected to double in four years,
Banking is one of the largest industries spending the most in AI/ML solutions
for fraud analysis, investigation, program advisors and recommendation systems
[103].

In the following, we discuss how quantum-enhanced feature space can be used in
a simple task of binary classification that can be applied to financial
applications, such as, fraud detection (for transaction monitoring) and credit
risk scoring (for customer identification). There are many other tasks
addressable by quantum machine learning techniques, e.g., see [3, 104] for
more tasks and applicable quantum techniques. We focus in supervised learning
using Support Vector Machine (SVM): we have access to labeled training data
$\mathit{S}$ to classify test data $\mathit{T}$ and labels of unseen future
data (with assumption that all data come from the same underlying
distribution).

Assume that we are given the training data
$\mathit{S}=\left\\{(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{m_{S}},y_{m_{S}})\right\\}$,
where each $x_{i}\in\mathbb{R}^{d}$ and $y_{i}\in\\{-1,1\\}$. The goal of
learning a binary classifier from $\mathit{S}$ is to construct a function
$f(x)$ so that $f(x)y_{i}>0$. The simplest form of such function is a linear
classifier $f(x)=w^{\intercal}x+b$, where $(w,b)\in\mathbb{R}^{d+1}$.
$\mathit{S}$ is called linearly separable if there is a
$(w,b)\in\mathbb{R}^{d+1}$ satisfying $f(x)y_{i}>0$. Such function, if exists,
can be found by solving an optimization problem known as Hard-SVM.

In general, the dataset may not be linearly separable. In such case we can
still find a classifier that predicts the training dataset with some error
margin. The fomulation is know as Soft-SVM, as shown below, and can be solved
efficiently by techniques such as Stochastic Gradient Descent (SGD).

$\displaystyle(w_{0},b_{0})$ $\displaystyle=$
$\displaystyle\operatorname*{arg\,min}_{(w,b)}\|w\|^{2}+C\sum_{i=1}^{m_{S}}\epsilon_{i}$
subject to $\displaystyle:$ $\displaystyle y_{j}~{}(w^{\intercal}x_{j}+b)\geq
1-\epsilon_{j}~{}\mbox{for}~{}j\in[m_{S}]$ $\displaystyle\epsilon_{j}\geq
0~{}\mbox{for}~{}j\in[m_{S}]$

The slack variables $\\{\epsilon_{i}\\}$ determine the quality of the
classifier: the closer they are to zero the better the classifier. For this
purpose, we can embed the data $\\{x_{j}\\}$ into a larger space by pre-
processing the data, namely, by finding a map $x:\Phi(x)\in\mathbb{R}^{n}$ for
$n>d$. The classifier $f(x)$ is now defined as
$f(x)=w^{\intercal}{\Phi(x)}+b$. When $\Phi(x)$ is an embedding of data non-
linearly to quantum state $\left|\Phi(x)\right>$ then we can use quantum-
enhanced feature space for the classifier. There are two techniques to
construct such a quantum-enhanced feature space that may lead to a Quantum
Advantage: Variational Quantum Classification (VQC) and Quantum Kernel
Estimation (QKE).

The VQC is similar to SGD for finding the best hyperplane $(w,b)$ that
linearly separates the embedded data. At VQC, the data $x\in\mathbb{R}^{d}$ is
mapped to (pure) quantum state by the feature map circuit $U_{\Phi(x)}$ that
realizes $\Phi(x)$. This means, that conditioned on the data $x$, we apply the
circuit $U_{\Phi(x)}$ to the $n$-qubit all-zero state $\left|0_{n}\right>$ to
obtain the quantum state $\left|\Phi(x)\right>$. A short-depth quantum circuit
$W(\theta)$ is then applied to the quantum state, where $\theta$ is the
hyperparameter set of the quantum circuit that can be learned from the
training data. Finding the circuit $W(\theta)$ is akin to finding the
separating hyperplane $(w,b)$ in the Hard-SVM and Soft-SVM, with the path to
Quantum Advantage stems from the fact that there is no efficient classical
procedure to realize the feature map $\Phi(x)$. While the size of the
hyperparameter set $\theta$ is polynomial in the number of qubits and can be
tuned with variational methods similar to Algorithm 1 and 2, it controls an
exponentially large space of the feature map. The binary decision is obtained
by measuring the quantum state in the computational basis to obtain
$z\in\left\\{0,1\right\\}^{n}$, and linearly combining the measurement
results, say with
$g=\sum_{z\in\left\\{0,1\right\\}^{n}}g(z)\left|z\right>\left<z\right|$, where
$g(\cdot)\in\\{-1,1\\}$.

A quantum circuit that realizes the quantum feature map as well as the
variational classifier is shown in Fig. 12. We can see that the probability of
observing $z$ is given as

$\left|\left<z\right|W(\theta)\left|\Phi(x)\right>\right|^{2}=\left<\Phi(x)\right|W^{\dagger}(\theta)\left|z\right>\left<z\right|W(\theta)\left|\Phi(x)\right>.$

By linear combination of the measurement results $z$ with $g$, we can obtain
the function $f(x)$ as below, which resembles the linear classifier
$f(x)=w^{\intercal}\Phi(x)+b$:

$f(x)=\left<\Phi(x)\right|W^{\dagger}(\theta)~{}g~{}W(\theta)\left|\Phi(x)\right>+b.$

The predicted label of $f(x)$ is then simply its sign. The hyperplane $(w,b)$
is now parametrized by $\theta$. The $i$-th element of $w(\theta)$ is
$w_{i}(\theta)=\tr\left(W^{\dagger}(\theta)gW(\theta)P_{i}\right)$, where
$P_{i}$ is a diagonal matrix whose elements are all zeros except at the $i$-th
row and column which is $1$, and the $i$-th element of $\Phi(x)$ is
$\Phi_{i}(x)=\left<\Phi(x)\right|P_{i}\left|\Phi(x)\right>$.

Learning the best $\theta$ can be obtained by minimizing the empirical risk
$R(\theta)$ with regards to the training data
$\mathit{S}=\left\\{(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{m_{S}},y_{m_{S}})\right\\}$.
Namely, the empirical risk (or, cost function) to be minimized is

$R(\theta)=\frac{1}{|S|}\sum_{i\in[m_{\mathit{S}}]}\left|f(x_{i})-y_{i}\right|.$
(30)

The above empirical risk can then be approximated with a continuous function
using sigmoid function as detailed in [25]. This enables applying variational
methods as in Algorithm 1 and 2 with stochastic gradient descent algorithms
(such as, COBYLA or SPSA) for tuning $\theta$ to minimize the cost function.

The binary classification with VQC now follows from first training the
classifier to learn the best $\theta^{*}$, that minimizes the empirical risk
$R(\theta)$, to obtain $(w(\theta^{*}),b^{*})$. This can be done with
Algorithm 1 with the Hamiltonian replaced by the empirical risk. The
classification against unseen data $x$ is then performed according to the
classifier function $f(x)$ with $(w(\theta^{*}),b^{*})$. Both training and
classification need to be repeated for multiple times (or, shots) due to the
probabilistic nature of quantum computation. The former may need significant
number of shots proportional to the size of $\mathit{S}$ but it can be
performed in batch offline. One the other hand, the latter needs much less
number of shots, and may be performed online (or, near real time) as long as
the quantum feature map for non-linear embedding can be computed efficiently.

Figure 12: Quantum circuit for Variational Quantum Classifier (VQC) that
consists of fixed quantum feature mapping $\mathcal{U}_{\Phi(x)}$ and the
separator $W(\theta)$ trained with variational methods.

In the conventional SVM, there are many known methods of non-linear embedding
of data $x:\Phi(x)\in\mathbb{R}^{n}$ for $n>d$, such as, Polynomial-SVMs. For
example, in a Polynomial-SVM, the 2-dimensional data $(x_{1},x_{2})$ can be
embedded into a 3-dimensional $(z_{1},z_{2},z_{3})$ such that,
$z_{1}=x_{1}^{2}$, $z_{2}=\sqrt{2}x_{1}x_{2}$, and $z_{3}=x_{2}^{2}$. On the
other hand, in the quantum-enhanced SVM, the embedding of data to $n$-qubit
feature space can be performed by applying the unitary
$\mathcal{U}_{\Phi(x)}=U_{\Phi(x)}H^{\otimes n}U_{\Phi(x)}H^{\otimes n}$,
where $H$ is the Hadamard gate, and $U_{\Phi(x)}$ denotes a diagonal gate in
the Pauli-Z basis as below

$\displaystyle U_{\Phi(x)}$ $\displaystyle=$
$\displaystyle\exp\left(i\sum_{S\subseteq\left[n\right]}\phi_{S}(x)\prod_{k\in
S}Z_{k}\right),$ (31)

where the coefficients $\phi_{S}(x)\in\mathbb{R}$ are fixed to encode the data
$x$. For example, for $n=d=2$ qubits, $\phi_{i}(x)=x_{i}$ and
$\phi_{1,2}(x)=(\pi-x_{1})(\pi-x_{2})$ were used in [25]. In general the
$U_{\Phi(x)}$ can be any diagonal unitary that can be implemented efficiently
with short-depth quantum circuits. In total, one needs at least $n\geq d$
qubits to construct such quantum-enhanced feature map. There are other
proposed methods promising Quantum Advantage for non-linear embedding of data
into quantum feature space, such as, squeezing in continuous quantum systems
[105] that guarantees linear separability, or amplitude encoding [106] that
can exploit tensorial feature map, or density-operator encoding [107]. A
recent paper studies the embedding in the context of metric learning [108].

Classification models in real-world datasets often also depend on binary
features, such as, gender and yes-no answers to questions, in addition to
(discrete) categorical and qualitative features, such as, zip code, age, and
color. Such discrete features have to be encoded into continuous features
before they can be used effectively in machine learning models that rely on
continuity of their inputs, such as VQCs. There have been many proposed
encodings, with one-hot encoding as one of the most populars, for such
purposes [109]. It is known that the encodings can heavily impact the
performance of the learning models. Efficient mapping of such discrete
features into quantum-enhanced feature space is very important in finance
models with structured data. A recent study [110] reports the possibility of
using Quantum Random Access Coding(QRAC) [111] to map discrete features into
the quantum-enhanced feature space resulting in faster training and better
classification accuracy due to using less number of qubits and hence less
hyperparameters in the VQC models. The idea is to split the encoding of $x$
into that for the discrete and continuous parts, each represented as
$x^{(b)}$, and $x^{(r)}$. The discrete parts $x^{(b)}$ are obtained from the
encoding of categorical features into binary strings using determined
techniques such as one-hot encoding, or into integer numbers for ordinal
features. Fig. 13 depicts a VQC with QRAC for encoding discrete features.

Figure 13: Quantum Circuits for Variational Quantum Classifier with Quantum
Random Access Coding for encoding discrete features. Latent qubits may be
included to add the dimension of the embedding in the Hilbert space.

In particular, let us consider the case of classifying credit card
transactions into fraudulent or not from a synthesized dataset from [112],
that was generated with state machines in simulated world to be representative
for the US customers. For our purpose, the synthesized credit card transaction
data was prepared to contain 100 records of purchase transactions. The $i$-th
transaction $x_{i}$ contains the transaction time, the transaction amount, the
transaction method, the transaction location (in ZIP code), and the Merchant
Category Code (MCC). The first two are in real numbers, and the rest are
categorical; there are 3 types of transaction methods, 10 different locations,
and 10 different MCCs. Each $i$-th transaction is labeled as either fraudulent
($y_{i}=-1$), or normal ($y_{i}=1$). A similar study on the same data set has
also been carried out using _Variational Quantum Boltzmann Machines_ , an
alternative approach to VQC or QKE, and we refer to [113] for more details.

TABLE IV: The average and standard deviation of accuracy of classifiers on 5-fold Cross Validations of the synthetic credit-card transaction dataset. LR, SVC1, and SVC2, are respectively, the Logistic Regression, the SVC with Linear, and RBF Kernel. VQC and VQCwQRAC are quantum-enhanced SVMs with the latter using QRAC for encoding the transaction method. | LR | SVC1 | SVC2 | VQC | VQCwQRAC
---|---|---|---|---|---
train | $0.79\pm 0.02$ | $0.80\pm 0.03$ | $0.87\pm 0.02$ | $0.74\pm 0.05$ | $0.85\pm 0.03$
test | $0.77\pm 0.06$ | $0.81\pm 0.07$ | $0.82\pm 0.07$ | $0.64\pm 0.09$ | $0.83\pm 0.06$

We applied the VQC as in Fig. 12 by regarding all features as real values to
use the feature mapping in Eq. 31 with second-order expansion. On the other
hand, we applied the VQC as in Fig. 13 by the QRAC of the one-hot encoding of
the transaction method, and the rest similar to the VQC. The latter is denoted
as VQCwQRAC. Both models used 5 qubits and were trained with variational
circuits $W(\theta)$ defining the separating hyperplanes that consists of the
RXRY variational gates and 1 layer of full-connected entangler as implemented
in Qiskit[54]. Both classification models were run on qiskit simulators and
tested with 5-fold Cross Validation of the dataset. The average training
losses, where Eq. 30 is approximated with the cross entropy, are shown in Fig.
14. We can see that using QRAC for encoding binary features can result in
better training losses. The accuracy of VQCwQRAC is better than the VQC using
real-valued quantum feature mapping as shown in Table IV, and is comparable to
Support Vector Classifier with RBF kernel (SVC2 in the Table).

Figure 14: Comparison of the training loss of VQC against that with QRAC
(VQCwQRAC) for encoding discrete features on a synthetic credit-card
transaction dataset.

Finally, we note that the possible Quantum Advantage for machine learning task
is somewhat speculative; there is no known theoretical proof that the quantum
feature map, which is hard to compute classically, can result in better
accuracy than any classical classifiers. Also, the underlying variational
methods, as in Algorithm 1 and 2, are heuristics that may only find local
optima instead of the global one, and thus can lower the accuracy of the
resulting quantum-enhanced SVM.

##  VI Technical challenges in quantum computing

In the following section we outline some of the technical challenges to
address when solving computationally challenging problems on a quantum
computer.

###  VI-A Loading data

To understand constraints on quantum computing both near-term and long-term,
it may be useful to contrast quantum computers against classical computers.
Classical computing utilises the well-known von Neumann model: there is a
central processing unit (CPU), which performs non-reversible computation,
including branching, and this is connected by a system bus to volatile memory
(RAM) and non-volatile memory (such as a hard drive). Loading data from the
non-volatile memory to RAM and accessing the data in RAM from the CPU is taken
for granted. In contrast, there are no quantum (memory) hard drives at the
current level of hardware technology, most blueprints do not involve any RAM,
and all of the computations are reversible without branching (excepting post-
selection).

The key difference lies in the time complexity of “loading data”. A quantum
state can be seen as a volatile memory of substantial capacity, but with non-
trivial issues in addressing it. With $k$ qubits, we work with $2^{k}\times
2^{k}$ density matrices 222A density matrix is a representation of a quantum
state. A density matrix can represent both pure states (i.e. states
represented by a state vector $\ket{\psi}$) and mixed quantum states (i.e. a
statistical ensemble of pure states)., but working with these matrices is
limited to a certain set of one- and two-qubit gates (unitary matrices applied
to the quantum state). The quantum circuit complexity of state preparation,
i.e., minimum number of gates required in order to “load” a given arbitrary
quantum state $U$ using any sequence of one- and two-qubit gates, is greater
or equal than $4^{k}$ for almost all $U$. Notice that this is not a worst-case
result: this holds generically for all states and it applies to the best
possible sequence of one- and two-qubit gates. Consider a dimension-counting
argument. There are also explicit constructions showing that this is tight.

While this means theoretically that a $4^{k}$-dimensional state can be
prepared into a quantum machine having $k$ qubits via a quantum loader having
$O(4^{k})$ circuit complexity – which is linear in the data dimension – it is
also exponential in the number of qubits $k$. Whereas in classical computing,
we usually assume that we can load the data in time linear in the number of
bits and then worry about the run-time (circuit complexity of processing) on
the loaded data, in quantum computing, preparation of a quantum state may
require a quantum circuit complexity exponential in the number of qubits. The
complexity of generic state preparation can impede a potential Quantum
Advantage, as the loading time may eclipse coherence times for the physical
quantum state and also for some algorithms, loading the data can become
computationally as expensive as using a classical algorithm to solve the
problem [114].

There are multiple ways of circumventing this issue. One is to allow $j$-qubit
gates, where $j$ may grow with $k$, which poses a major challenge in quantum
optimal control. One is to “split” the state preparation into an independent
system, such as circuitry of some potential qRAM [115], and utilise quantum
optimal control there, perhaps across all of the $k$ qubits. Given the
(quantum circuit complexity) equivalence [116] of state preparation and an
arbitrary circuit, it seems unlikely that it would be possible to implement
one way of circumventing the quantum circuit complexity without being able to
implement the other, and without being able to utilise the same quantum
optimal control in the execution of the quantum circuit. Indeed, it is
believed the physical realization of qRAM model may be even much more
difficult than the fault-tolerant quantum computers [104, 114].

In some cases, the problem can also be circumvented because the data to be
loaded has structure or properties that can be exploited for efficient
loading, e.g., if the data can be described by a log-concave probability
distribution [51]. Alternatively, and depending on the application, we may
drop the goal of loading the data exactly and try to prepare a quantum state
that at least is close to our original data. This enables approximate data
loading schemes which have some potential to work around this problem [57]. It
is also possible to exploit periodic properties in certain data sets, for
example. time series data which exhibits periodic properties. By extracting
periods in the data via classical techniques such as FFT, we may then load
only the dominant periods via a small number of steps onto the quantum
machine, then recover an approximation of the original data in the quantum
machine via an inverse quantum Fourier transform (QFFT-1) algorithm.

###  VI-B Quantum error correction

As has been suggested in Section I, a key watershed between noisy quantum
computers and universal fault-tolerant quantum computers is the availability
of quantum error correction (QEC).

The key technical challenge within QEC is the trade-off between the overhead
of the QEC and the so-called error threshold. The overhead is, essentially,
the number of physical qubits required to protect a certain number of logical
qubits against errors. The error threshold comes from the famous (quantum)
threshold theorem [17, 18], which shows that if the errors on individual
qubits are not correlated and the error of the physical qubits falls below a
certain threshold, QEC schemes can correct the remainder of the error, at a
cost of the overhead. Actually, the dissertation of Gottesman [17] shows that
there is a simple construction, starting with classical error correcting
codes, which makes it possible to estimate the threshold. For one of the best-
known classes of QEC, it is sometimes assumed [19] that a 0.1% probability of
a depolarizing error would require more than 1,000 physical qubits per
protected qubit – although the details of the calculation are also often
disputed. There is a substantial interest in further classes of QEC (e.g.,
hyperbolic surface codes), which could perform substantially better.

For the same QEC mentioned above [19], one should notice that there need not
be a substantial increase in the depth of the circuit: for gates within the
Clifford algebra, which includes the Hadamard gate (H), controlled not (CNOT),
and $S=\textrm{diag}(1,e^{i\pi/2})$, we can apply the gate to all the physical
qubits in order to apply the same gate to the protected qubit. The increase in
depth of the circuit is hence only due to gates outside of the Clifford
algebra.

In Sec. III we showed that AE can replace Monte Carlo based simulations. The
resulting quantum circuits are too deep for quantum computers without error
correction due to the controlled $\mathcal{Q}^{2^{j}}$ operators, see Fig. 4.
We therefore anticipate that AE-based applications will require fault-tolerant
quantum computers. By contrast, the optimization and machine learning
applications discussed in Sec. IV and V that are based on variational quantum
circuits as in the VQE and the QAOA could be executed on near-term noisy
quantum computers. However, these heuristic algorithms do not provide a
theoretical guarantee as does AE. Further research is thus needed to fully
understand under what conditions they will outperform their classical
counterparts.

###  VI-C Precision and sample complexity

Generally, the higher probability of outputting the correct answer is
required, the more “shots”, or repetitions of the execution of quantum circuit
followed by measurement, are needed. In some cases (e.g., HHL), because the
solution is encoded in the probability amplitudes of the quantum states, one
may need to perform quantum state tomography to obtain the complete solution.
The quantum state tomography requires exponential number of shots in the
number of qubits involved, and hence can diminish the exponential advantages
of the subroutines. In many algorithms, the error also depends on the number
of qubits used in the output register.

For example for the phase estimation mentioned in Section III-A, the
probability of not determining phase angle to an accuracy of $s$ bits, i.e.,
up to error $2^{-s}$, using $s+p$ qubits for the output is:

$\displaystyle\epsilon(s,p)=1-\frac{1}{2^{2(p+s)-2}}\sum_{l=1}^{2^{p-1}}\frac{1}{1-\cos\frac{\pi(2l-1)}{2^{p+s}}}$
(32)

While the expression may be difficult to read, it is essentially positive, in
that it suggests that the error rate decays exponentially with the extra $p$
qubits. Especially when many instances of phase estimation are used
sequentially, the error propagation may still be a cause for concern, though,
and it may get progressively more difficult to analyze the error. Still,
estimates of forward error of more complex algorithms [117] are available.

TABLE V: Algorithms can improve computational efficiency, accuracy, and
addressability for defined use case.

Quantum Algorithm Description Impact Needs Simulation Optimization ML VQE
Variational Quantum Eigensolver Use energy states to calculate the function of
the variables to optimize Procedure to assign compute-intensive functions to
quantum and those of controls to classical Qubit number increases
significantly with problem size x QAOA Quantum Approximate Optimization
Optimize combinatorial style problems to find solutions with complex
constraints Simplify analysis clauses for constraints and provide robust
optimization in complex scenarios Uncertain ability to expand to more
optimization classes x AE Quantum Amplitude Estimator Create simulation
scenarios by estimating an unknown property, Monte Carlo style Handle random
distributions directly, instead of only sampling, to solve dynamic problems
quadratically speeding up simulations High Quantum Volume required for good
efficiency x x x QSVM Quantum Support Vector Machines Supervised machine
learning for high dimensional problem sets Map data to quantum-enhanced
feature space to enable separation and better separate data points to achieve
more accuracy Runtime can be slowed by kernel computation and data structure x
HHL Harrow, Hassidim, and Lloyd Estimate the resulting measurement of large
linear systems Solve high dimensional problems speeding up exponentially
calculations Hard to satisfy prerequisites and high measurement costs to
recover solutions x x QSDP Quantum Semidefinite Programming Optimize a linear
objective over a set of positive semidefinite matrices Estimate quantum system
states with less measurements to exponentially speedup in terms of dimension
and constraints High Quantum Volume required for good efficiency x

TABLE VI: Financial services focus areas and algorithms.

Financial Services Example Problems Solution Approach Quantum Algorithm Asset
Management Option Pricing Simulation AE Portfolio risk Investment Portfolio
Optimization Optimization Combinatorial: VQE, QAOA Banking Portfolio
Diversification Continuous: QSDP Issuance: Auctions AE Retail & Corporate
Financial Forecasting Machine Learning QSVM Banking Credit Scoring (e.g. SME
Banking) HHL Financial Crimes: Fraud + AML AE

##  VII Conclusion

There are a number of computationally challenging problems in financial
services that are demanding in terms of required precision or run-time. For
these we have outlined three problem classes:

  * •

One class are optimization problems that scale exponentially limiting their
resolution in a given time frame. The holistic problem-solving approach to
optimization problems of quantum computers, raises the potential to find
better solutions in a smaller number of steps.

  * •

A second class are machine learning problems, where one faces complex data
structures that hinder classification or prediction accuracy. The multi-
dimensional data modeling capacity of quantum computers may allow to find
better patterns, with increasing accuracy.

  * •

A third class are simulation problems, where there are time-limits to perform
sufficient scenario tests to find the best potential solution. Efficient
sampling methods leveraging quantum computers may require less samples to
reach a more accurate solution faster.

For each of them we have introduced quantum algorithms, which can be applied
to specific problems in there. Table V summarizes the quantum algorithms
introduced, their applicability for the three problem classes, their
advantages and challenges. In addition, for the three initial focus areas in
financial services, Asset Management, Investment Banking, Retail & Corporate
Banking, example problems and applicable quantum algorithms are summarized in
Table VI.

Quantum computers and the algorithms that leverage them may help to solve
hurdles and challenges arising in the financial industry given increasing
demand for more sophisticated risk analysis, dynamic client management,
constant updates to market volatility, and faster transaction speeds.

Finally, we have also demonstrated the performance of quantum algorithms on
IBM Quantum backends for three specific applications. In general, simulation,
optimization and machine learning are among the areas where we may demonstrate
an advantage of quantum computing over classical computing for certain
applications first.

## Acknowledgements

RR would like to acknowledge Erik Altman of IBM Research for providing the
credit-card transaction dataset, and Hiroshi Yano of Keio University for his
help in analyzing the dataset.

IBM, the IBM logo, and ibm.com are trademarks of International Business
Machines Corp., registered in many jurisdictions worldwide. Other product and
service names might be trademarks of IBM or other companies. The current list
of IBM trademarks is available at https://www.ibm.com/legal/copytrade.

## References

  * [1] R. LaRose, Overview and Comparison of Gate Level Quantum Software Platforms, Quantum 3 (2019) 130.  doi:10.22331/q-2019-03-25-130.
  * [2] Wikipedia, Cloud-based quantum computing (2020).
URL https://en.wikipedia.org/wiki/Cloud-based-quantum-computing

  * [3] R. Orús, S. Mugel, E. Lizaso, Quantum computing for finance: Overview and prospects, Reviews in Physics 4 (2019) 100028.  doi:10.1016/j.revip.2019.100028.
  * [4] S. Bravyi, D. Gosset, R. Koenig, Quantum advantage with shallow circuits, Science 362 (6412) (2018) 308–311.  doi:10.1126/science.aar3106.
  * [5] D. J. Egger, R. G. Gutiérrez, J. C. Mestre, S. Woerner, Credit risk analysis using quantum computers (2019).  arXiv:1907.03044.
  * [6] P. Rebentrost, B. Gupt, T. R. Bromley, Quantum computational finance: Monte Carlo pricing of financial derivatives, Physical Review A 98 (2) (Aug 2018).  doi:10.1103/physreva.98.022321.
  * [7] N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, S. Woerner, Option pricing using quantum computers, Quantum 4 (2020) 291.  doi:10.22331/q-2020-07-06-291.
  * [8] Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, N. Yamamoto, Amplitude estimation without phase estimation, Quantum Information Processing 19 (2) (Jan 2020).  doi:10.1007/s11128-019-2565-2.
  * [9] S. Woerner, D. J. Egger, Quantum risk analysis, npj Quantum Information 5 (15) (2019).  doi:10.1038/s41534-019-0130-6.
  * [10] L. Braine, D. J. Egger, J. Glick, S. Woerner, Quantum algorithms for mixed binary optimization applied to transaction settlement (2019).  arXiv:1910.05788.
  * [11] C. Gambella, A. Simonetto, Multi-block ADMM heuristics for mixed-binary optimization on classical and quantum computers (2020).  arXiv:2001.02069.
  * [12] G. Nannicini, Performance of hybrid quantum-classical variational heuristics for combinatorial optimization, Physical Review E 99 (1) (2019) 013304.  doi:10.1103/PhysRevE.99.013304.
  * [13] M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, UK, 2000.  doi:10.1017/CBO9780511976667.
  * [14] IBM, Getting your financial institution ready for the quantum computing revolution (2018).
URL https://www.ibm.com/thought-leadership/institute-business-
value/report/quantumfinancial#

  * [15] IBM, Exploring quantum computing use cases for financial services (2018).
URL https://www.ibm.com/thought-leadership/institute-business-
value/report/exploring-quantum-financial#

  * [16] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2 (2018) 79.  doi:10.22331/q-2018-08-06-79.
  * [17] D. E. Gottesman, Stabilizer codes and quantum error correction, Ph.D. thesis, California Institute of Technology (1997).  arXiv:quant-ph/9705052.
  * [18] D. Aharonov, M. Ben-Or, Fault-tolerant quantum computation with constant error rate, SIAM Journal on Computing 38 (4) (2008) 1207–1282.  doi:10.1137/S0097539799359385.
  * [19] E. T. Campbell, B. M. Terhal, C. Vuillot, Roads towards fault-tolerant universal quantum computation, Nature 549 (7671) (2017) 172–179.  doi:10.1038/nature23460.
  * [20] IBM Quantum, IBM Quantum systems overview (2020).
URL https://quantum-computing.ibm.com/docs/manage/backends/

  * [21] A. Cross, L. Bishop, S. Sheldon, P. Nation, J. Gambetta, Validating quantum computers using randomized model circuits, Phys.Rev.A. 100 (032328) (2019).  doi:10.1103/PhysRevA.100.032328.
  * [22] J. Gambetta, IBM’s Roadmap For Scaling Quantum Technology (2020).
URL https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadmap/

  * [23] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nature communications 5 (2014) 4213.  doi:10.1038/ncomms5213.
  * [24] E. Farhi, J. Goldstone, S. Gutmann, A quantum approximate optimization algorithm (2014).  arXiv:1411.4028.
  * [25] V. Havlicek, A. D. Corcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, J. M. Gambetta, Supervised learning with quantum-enhanced feature spaces, Nature 567 (7747) (2019) 209–212.  doi:10.1038/s41586-019-0980-2.
  * [26] J. Courbe and M. von Engel and C. O’Hara and J. Garvey and J. Lyons, Financial Services Technology 2020 and Beyond: Embracing disruption (2020).
URL https://www.pwc.com/gx/en/financial-
services/assets/pdf/technology2020-and-beyond.pdf

  * [27] The Basel Committee on Banking Supervision (BCBS), Basel III: The Liquidity Coverage Ratio and Liquidity Risk Monitoring Tools (2013).
URL https://www.bis.org/publ/bcbs238.htm

  * [28] K. Bhaskaran, R. Chang, P. Dey, J. Sanz, Financial services industry challenges and innovation opportunities, IEEE World Congress on Services 1 (2019) 224–229.  doi:10.1109/SERVICES.2019.00062.
  * [29] Reuters, Some banks risk usd 240 million research loss as mifid gives low-cost players a leg-up (June 26 2017).
URL https://www.reuters.com/article/uk-banks-research/some-banks-
risk-240-million-research-loss-as-mifid-gives-low-cost-players-a-leg-up-
idUKKBN19H0C0

  * [30] Reuters, EU banks face fines if they fall short on capital (July 20 2011).
URL https://www.reuters.com/article/us-eu-banks/eu-banks-face-fines-if-they-
fall-short-on-capital-idUSTRE76J21I20110720

  * [31] VOB, The consequences of Basel IV - a quantitative impact study (May 25 2018).
  * [32] Nomura, The net stable funding ratio (NSFR) - what does it mean for you (2014).
URL https://www.nomura.com/primefinance/assets/documents/nsfr.pdf

  * [33] McKinsey, Basel III and European banking: Its impact, how banks might respond, and the challenges of implementation (2010).
URL
https://www.mckinsey.com/~/media/mckinsey/industries/financial%20services/our%20insights/basel%20iii%20now%20the%20hard%20part%20for%20european%20banks/26_basel_iii_and_european_banking.ashx

  * [34] J. Hull, Options, futures, and other derivatives, 6th Edition, Pearson Prentice Hall, 2006.
  * [35] F. Black, M. Scholes, The pricing of options and corporate liabilities, Journal of Political Economy 81 (3) (1973) 637–654.  doi:10.1086/260062.
  * [36] B. Dupire, Pricing with a smile, Risk Magazine (1994) 18–20.
URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.320.5063

  * [37] P. P. Boyle, Options: A Monte Carlo approach, Journal of Financial Economics 4 (3) (1977) 323–338.  doi:10.1016/0304-405X(77)90005-8.
  * [38] P. Glasserman, Monte Carlo Methods in Financial Engineering, Springer-Verlag New York, 2003.  doi:10.1007/978-0-387-21617-1.
  * [39] Basel Committee on Banking Supervision, Minimum capital requirements for market risk (2019).
URL https://www.bis.org/bcbs/publ/d457.htm

  * [40] P. Glasserman, P. Heidelberger, P. Shahabuddin, Efficient Monte Carlo Methods for Value-at-Risk, Vol. 2, 2000.
URL https://www0.gsb.columbia.edu/faculty/pglasserman/Other/masteringrisk.pdf

  * [41] Basel Committee on Banking Supervision, Revisions to the Basel II market risk framework (2009).
URL https://www.bis.org/publ/bcbs158.htm

  * [42] C. Joy, P. P. Boyle, K. S. Tan, Quasi-monte carlo methods in numerical finance, Manag. Sci. 42 (6) (1996) 926–938.  doi:10.1287/mnsc.42.6.926.
  * [43] P. Glasserman, J. Li, Importance sampling for portfolio credit risk, Manag. Sci. 51 (2005) 11.  doi:10.1287/mnsc.1050.0415.
  * [44] A. Carrera Vazquez, S. Woerner, Efficient State Preparation for Quantum Amplitude Estimation (2020).  arXiv:2005.07711.
  * [45] G. Brassard, P. Hoyer, M. Mosca, A. Tapp, Quantum Amplitude Amplification and Estimation, Contemporary Mathematics 305 (2002).  doi:10.1090/conm/305.
  * [46] A. Y. Kitaev, Quantum measurements and the Abelian Stabilizer Problem (1995).  arXiv:9511026.
  * [47] S. Aaronson, P. Rall, Quantum approximate counting, simplified (2019).  arXiv:1908.10846.
  * [48] D. Grinko, J. Gacon, C. Zoufal, S. Woerner, Iterative Quantum Amplitude Estimation (2019).  arXiv:1912.05559.
  * [49] M. Rutkowski, S. Tarca, Regulatory capital modelling for credit risk, International Journal of Theoretical and Applied Finance 18 (5) (2015) 1550034\.  doi:10.1142/S021902491550034X.
  * [50] Basel Committee on Banking Supervision, International convergence of capital measurement and capital standards (2006).
URL https://www.bis.org/publ/bcbs128.htm

  * [51] L. Grover, T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions (2002).  arXiv:0208112.
  * [52] S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, A new quantum ripple-carry addition circuit (2004).  arXiv:0410184.
  * [53] T. G. Draper, S. A. Kutin, E. M. Rains, K. M. Svore, A logarithmic-depth quantum carry-lookahead adder, Quantum Information and Computation 6 (2006) 351–369.
URL https://dl.acm.org/doi/10.5555/2012086.2012090

  * [54] H. Abraham _et al._ , Qiskit: An Open-source Framework for Quantum Computing (2019).  doi:10.5281/zenodo.2562110.
  * [55] A. G. Fowler, C. Gidney, Low overhead quantum computation using lattice surgery (2018).  arXiv:1808.06709.
  * [56] M. Plesch, C. Brukner, Quantum-state preparation with universal gate decompositions, Phys. Rev. A 83 (2011) 032302.  doi:10.1103/PhysRevA.83.032302.
  * [57] C. Zoufal, A. Lucchi, S. Woerner, Quantum Generative Adversarial Networks for learning and loading random distributions, npj Quantum Information 5 (103) (2019).  doi:10.1038/s41534-019-0223-2.
  * [58] Treasury, An integrated approach to financial supply chain efficiency (2013).
URL https://www.treasury-management.com/article/4/270/2269/an-integrated-
approach-to-financial-supply-chain-efficiency.html

  * [59] KPMG, Financial supply chain management (2016).
URL https://assets.kpmg/content/dam/kpmg/pdf/2016/04/transforming-financial-
supply-chain.pdf

  * [60] DTCC, A different approach to accelerating settlement and reducing risk (2018).
URL http://www.dtcc.com/dtcc-connection/articles/2018/july/31/a-different-
approach-to-accelerating-settlement-and-reducing-risk

  * [61] CNBC, 5 mistakes to avoid when rebalancing a portfolio (2017).
URL https://www.cnbc.com/2017/02/14/5-mistakes-to-avoid-when-rebalancing-a-
portfolio.html

  * [62] IPE, Portfolio construction: A roadmap for portfolio rebalancing.
URL https://www.ipe.com/portfolio-construction-a-roadmap-for-portfolio-
rebalancing/41189.article

  * [63] CBInsights, Killing the i-bank: The disruption of investment banking.
URL https://www.cbinsights.com/research/report/disrupting-investment-banking

  * [64] Efinancialcareers, This is who goldman sachs will be mostly hiring in 2020 (2020).
URL https://news.efinancialcareers.com/us-en/3002977/goldman-sachs-technology-
hiring

  * [65] OutsideInsight, JPMorgan, Goldman Sachs and more double down on tech innovation.
URL https://outsideinsight.com/insights/jpmorgan-goldman-sachs-and-more-
double-down-on-tech-innovation/

  * [66] F. Brandao, M. Broughton, E. Farhi, S. Gutmann, H. Neven, For Fixed Control Parameters the Quantum Approximate Optimization Algorithm’s Objective Function Value Concentrates for Typical Instances (2018).  arXiv:1812.04170.
  * [67] C. Huang, M. Szegedy, F. Zhang, X. Gao, J. Chen, Y. Shi, Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design (2019).  arXiv:1909.02559.
  * [68] R. Shaydulin, Y. Alexeev, Evaluating quantum approximate optimization algorithm: A case study, 2019 Tenth International Green and Sustainable Computing Conference (IGSC) (Oct 2019).  doi:10.1109/IGSC48788.2019.8957201.
  * [69] G. G. Guerreschi, A. Y. Matsuura, QAOA for Max-Cut requires hundreds of qubits for quantum speed-up, Scientific Reports 9 (6903) (2019).  doi:10.1038/s41598-019-43176-9.
  * [70] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, M. D. Lukin, Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices (2018).  arXiv:1812.01041.
  * [71] G. E. Crooks, Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem (2018).  arXiv:1811.08419.
  * [72] A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization (2019).  arXiv:1912.04088.
  * [73] F. Brandao, R. Kueng, D. Stilck França, Faster quantum and classical SDP approximations for quadratic binary optimization (2019).  arXiv:1909.04613.
  * [74] S. Aaronson, Quantum Computing since Democritus, Cambridge University Press, 2013\.  doi:10.1017/CBO9780511979309.