# Explainable analysis of Deep Learning Methods
for SAR Image Classification

###### Abstract

Deep learning methods exhibit outstanding performance in synthetic aperture
radar (SAR) image interpretation tasks. However, these are black box models
that limit the comprehension of their predictions. Therefore, to meet this
challenge, we have utilized explainable artificial intelligence (XAI) methods
for the SAR image classification task. Specifically, we trained state-of-the-
art convolutional neural networks for each polarization format on OpenSARUrban
dataset and then investigate eight explanation methods to analyze the
predictions of the CNN classifiers of SAR images. These XAI methods are also
evaluated qualitatively and quantitatively which shows that Occlusion achieves
the most reliable interpretation performance in terms of Max-Sensitivity but
with a low-resolution explanation heatmap. The explanation results provide
some insights into the internal mechanism of black-box decisions for SAR image
classification.

Index Terms—  SAR Image Classification; Explainable Artificial Intelligence;
Deep Learning; Sentinel-1; OpenSARUrban

##  1 INTRODUCTION

Deep learning methods are playing an increasingly remarkable and irreplaceable
role in practical applications of various fields [1], including the field of
synthetic aperture radar (SAR) [2]. In order to fit complex data distribution
and obtain better performance, they generally have an intricate network
structure of opacity and extreme non-linearity. However, from a more rigorous
perspective, the application of deep learning models in many fields is still
limited, for lacking more reliable interpretability and explainability [3].

To circumvent these limitations, various explainable artificial intelligence
(XAI) methods have been proposed, which provide some detailed explanations for
the decision-making process of deep neural networks. The XAI methods could
analyze and reveal the internal mechanisms to some extent, so as to give
corresponding explanations and further evaluate the deep learning models [4].

In the field of Remote Sensing (RS), Ioannis et al. recently employed the XAI
methods to analyze the deep learning models for optical remote sensing image
classification based on the BigEarthNet and SEN12MS datasets [5].
Nevertheless, there is little work of explainable analysis of the deep neural
networks for SAR image classification, despite their success in it.

In this paper, we conducted an explainable analysis for deep convolutional
neural networks (DCNNs) for SAR image classification. Our contributions are:

  * •

We train a Residual Neural Network [6] ResNet101 on the OpenSARUrban dataset
[7], achieving state-of-the-art performance.

  * •

We employ eight XAI methods to explain the predictions of the ResNet101
network. We also evaluate these XAI methods qualitatively and quantitatively.

  * •

We conduct an in-depth analysis of the experimental results and draw some
inspiration from explainable SAR image classification.

##  2 methodology

Table 1: Results of quantitative metrics. XAI Method Quantitative Metrics | Max-Sensitivity | XAI entropy (KB)
---|---|---
VH | VV | VH | VV
Integrated Gradients | 0.0742 | 0.0952 | 28.663 | 30.841
Input × Gradient | 0.1362 | 0.1527 | 29.123 | 29.812
Guided Backpropagation | 0.0412 | 0.0392 | 24.34 | 24.099
Deconvolution | 0.0766 | 0.0754 | 29.638 | 30.058
Saliency | 0.1376 | 0.1534 | 52.624 | 52.14
Occlusion | 0.0178 | 0.0195 | 4.305 | 4.191
Guided Grad-CAM | 0.1819 | 0.1824 | 11.682 | 11.451
Grad-CAM | 0.4528 | 0.4942 | 15.107 | 14.916

###  2.1 XAI Methods

We firstly train a ResNet101[6] on the OpenSARUrban dataset[7] which achieves
state-of-the-art performance, and then apply eight XAI methods to understand
the internal behavior of the SAR image classifier, including Saliency [8],
Input × Gradient [9], Integrated Gradients [10], Guided Backpropagation [11],
Grad-CAM [12], Guided Grad-CAM [12] and Deconvolution [13] .

The Input × Gradient (InputXGrad) method multiplies the input with the
gradient by Equation 1. Compared with using the gradient alone, it shows more
reliability [5].

$\Phi_{\text{InputXGrad}}\left(f_{c},x\right)=x\odot\nabla f_{c}(x)$ (1)

The Guided Backpropagation method computes the gradient of the target output
with respect to the input, but only non-negative gradients are backpropagated
in that the gradients of ReLU functions are overridden.

The Integrated Gradients (IntGrad) method represents the integral of the
gradients along the straightline path from a base input $x^{\prime}$ to the
input $x$[10]. The base input can be a root point of the desired function,
which, for instance, can be the black image for the networks.

$\displaystyle\footnotesize\Phi_{\text{IG}}\left(f_{c},x\right)=\left(x-x^{\prime}\right)\times$
$\displaystyle\left.\int_{0}^{1}\frac{\partial
f_{c}(\tilde{x})}{\partial\widetilde{x}}\right|_{\tilde{x}=x^{\prime}+a\left(x-x^{\prime}\right)}da\quad$
(2)

The Occlusion is a perturbation based approach that replaces each rectangular
region with a given baseline / reference, and compares their output
differences.

$\displaystyle\Phi_{\text{Occlusion
}}^{p_{i}}\left(f_{c},x\right)=f_{c}(x)-f_{c}\left(x_{p_{i}}^{\prime}\right)$
(3)

###  2.2 Evaluating Metrics

In order to evaluate the performance of the XAI methods, quantitative
evaluation and qualitative evaluation were adopted by the metrics Max-
Sensitivity [14] and XAI entropy, namely,File Size[15].

The Max-Sensitivity [14] metric measures the stability on the basis of the
maximum explanation change with a subtle input disturbance, as in Equation 4.
The smaller Max-Sensitivity score indicates a more reliable explanation.

$\displaystyle\operatorname{SENS}_{MAX}\left(\Phi,f_{c},x,r\right)$
$\displaystyle=\max_{\left\|x^{\prime}-x\right\|\leq
r}\left\|\Phi\left(f_{c},x^{\prime}\right)-\Phi\left(f_{c},x\right)\right\|$
(4)

The XAI entropy metric is the auxiliary evaluation index that measures the
amount of information a XAI visualization image contains.

##  3 EXPERIMENTS

Fig. 1: Qualitatively evaluating the predictions of ResNet101 for the airport
class in the OpenSARUrban dataset. Max-Sensitivity score in parenthesis after
method’s name.

###  3.1 Experimental Setup

####  3.1.1 Dataset

Experiments were conducted on the OpenSARUrban dataset[7]. It is built on the
Sentinel-1 imagery and consists of 10 different urban categories, covering 21
major cities in China. Each image patch includes 2 kinds of polarization, VV
and VH polarization.

####  3.1.2 Implementation Details

Due to the different polarization modes, we divide the OpenSARUrban dataset
into two parts: one is the VH-polarized part and the other is the VV-polarized
part. We conduct the following experiments on these two parts separately.

We firstly adopt the ResNet101 mode[6] that achieves 83.44 percent
classification accuracy in VH-polarized part and 84.44 in VV-polarized part of
OpenSARUrban, by the data augmentation and integrating learning rate scheduler
strategies. In the following, the XAI methods are utilized to comprehend the
prediction of the trained models: Saliency, Input × Gradient, Integrated
Gradients, Guided Backpropagation, Grad-CAM, Guided Grad-CAM, Occlusion,
Deconvolution. We apply attribution analysis with visual examination and
visualized the attributions by generating the heat maps for each image for
every XAI method. At the same time, Max-Sensitivity and XAI entropy are
applied to quantitatively evaluate the performance of the above XAI methods.
The XAI experiments are implemented using the Captum library [16].

###  3.2 Results and Discussion

####  3.2.1 Quantitative Evaluation

Table 1 exhibits the experimental results of different XAI methods on the
urban scenes classification task in SAR images.

In terms of the Max-Sensitivity metric, it is worth noting that lower scores
indicate higher performance. Specifically, Occlusion, Guided Backpropagation
and Integrated Gradients are among the top three lowest scores in the VH-
polarized part while Occlusion, Guided Backpropagation and Deconvolution are
among the three lowest scores in the VV-polarized part. On the other hand,
Grad-CAM attains the highest score in both polarized data. For all cases,
Occlusion is the most prominent XAI method with a Max-Sensitivity score of
less than 0.05, while Grad-CAM performs the worst under Max-Sensitivity metric
in interpreting the SAR image classifier’s prediction result.

In terms of the XAI entropy metric, the ranking results are roughly the same
in both polarized datasets. Specifically, Occlusion, Guided Grad-CAM and Grad-
CAM obtain the top three lowest scores in both polarized data. In addition,
Occlusion ( 15 × 15 sliding window with 5 × 5 strides) provides us with more
low-resolution information and rough explanations in interpreting the SAR
image classifier’s prediction result, which possibly makes it easier for
humans to understand this model.

####  3.2.2 Qualitative Evaluation

A representative case that we visualize the attributions of the XAI methods is
presented in Fig. 1. Overall, after careful observation, all of the XAI
methods manage to analyze and reveal the internal mechanism in both VH- and
VV-polarized dataset.

Concerning visual examination, Occlusion, Integrated Gradients and Input ×
Gradient generally successfully mark the airstrip as an important area that
corresponds to the airport class in both VH- and VV-polarized dataset, which
is similar to our human cognition. However, it is worth mentioning that Grad-
CAM exhibits too much explanation of many details, resulting in poorer anti-
interference and higher Max-Sensitivity scores in the VH-polarized dataset. It
seemed that less attention was focused on the airstrip in the VV-polarized
dataset, leading to insufficient interpretability.

####  3.2.3 Discussion

Regarding the performance of XAI methods, on the one hand, Occlusion and
Integrated Gradients are the most interpretable XAI methods in both
quantitative evaluation and qualitative evaluation. They successfully
explained the SAR image classification task by targeting the most relevant
area of each image. Moreover, they achieved the lowest Max-Sensitivity scores,
which indicates that when the input slightly changes, the interpretation
result has no obvious difference, resulting in the highest reliability.

On the other hand, for quantitative evaluation, Grad-CAM performed worst,
which exhibited too much explanation of many details and ignored the main
relevant regions of each image, resulting in poorer anti-interference and
higher Max-Sensitivity scores. Additionally, for qualitative evaluation,
Deconvolution was the least interpretable XAI method, although it achieved
relatively low Max-Sensitivity scores. The reason is that the internal
mechanism of Deconvolution causes gradients of ReLU functions to be
overridden.

##  4 CONCLUSIONS

In this paper, we utilized eight XAI methods to explain the ResNet101’s
prediction of SAR image classification on OpenSARUrban and evaluate them
qualitatively and quantitatively. We observe that each method has its own
merits. Occlusion achieves the most reliable interpretation performance with
the lowest Max-Sensitivity score. However, it failed to provide high-
resolution information and detailed explanations. The XAI methods can reveal
the internal mechanism of deep learning methods and provide some insights into
SAR image classification tasks to some extent.

## References

  * [1] L. Deng and D. Yu, “Deep learning: Methods and applications,” _Found. Trends Signal Process._ , vol. 7, p. 197–387, jun 2014.
  * [2] Y. Zhou, H. Wang, F. Xu, and Y.-Q. Jin, “Polarimetric sar image classification using deep convolutional neural networks,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 13, no. 12, pp. 1935–1939, 2016.
  * [3] K. Cheng, N. Wang, and M. Li, “Interpretability of deep learning: A survey,” in _Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery_ , H. Meng, T. Lei, M. Li, K. Li, N. Xiong, and L. Wang, Eds. Cham: Springer International Publishing, 2021, pp. 475–486.
  * [4] S. Lapuschkin, S. Wäldchen, A. Binder, G. Montavon, W. Samek, and K.-R. Müller, “Unmasking clever hans predictors and assessing what machines really learn,” _Nature Communications_ , vol. 10, 03 2019.
  * [5] I. Kakogeorgiou and K. Karantzalos, “Evaluating explainable artificial intelligence methods for multi-label deep learning classification tasks in remote sensing,” _International Journal of Applied Earth Observation and Geoinformation_ , vol. 103, p. 102520, 2021.
  * [6] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2016.
  * [7] J. Zhao, Z. Zhang, W. Yao, M. Datcu, H. Xiong, and W. Yu, “Opensarurban: A sentinel-1 sar image dataset for urban interpretation,” _IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing_ , vol. 13, pp. 187–203, 2020.
  * [8] K. Simonyan, A. Vedaldi, and A. Zisserman, “Deep inside convolutional networks: Visualising image classification models and saliency maps,” in _In Workshop at International Conference on Learning Representations_ , 2014\.
  * [9] A. Shrikumar, P. Greenside, and A. Kundaje, “Learning important features through propagating activation differences,” in _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ser. ICML’17. JMLR.org, 2017, p. 3145–3153.
  * [10] M. Sundararajan, A. Taly, and Q. Yan, “Axiomatic attribution for deep networks,” in _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ser. ICML’17. JMLR.org, 2017, p. 3319–3328.
  * [11] J. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller, “Striving for simplicity: The all convolutional net,” 12 2014.
  * [12] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra, “Grad-cam: Visual explanations from deep networks via gradient-based localization,” in _2017 IEEE International Conference on Computer Vision (ICCV)_ , 2017, pp. 618–626.
  * [13] A. Mahendran and A. Vedaldi, “Salient deconvolutional networks,” in _Computer Vision – ECCV 2016_ , B. Leibe, J. Matas, N. Sebe, and M. Welling, Eds. Cham: Springer International Publishing, 2016, pp. 120–135.
  * [14] C.-K. Yeh, C.-Y. Hsieh, A. S. Suggala, D. I. Inouye, and P. Ravikumar, “On the (in)fidelity and sensitivity of explanations,” in _NeurIPS_ , 2019.
  * [15] W. Samek, G. Montavon, S. Lapuschkin, C. Anders, and K.-R. Müller, “Toward interpretable machine learning: Transparent deep neural networks and beyond,” 03 2020.
  * [16] N. Kokhlikyan, V. Miglani, M. Martin, E. Wang, B. Alsallakh, J. Reynolds, A. Melnikov, N. Kliushkina, C. Araya, S. Yan, and O. Reblitz-Richardson, “Captum: A unified and generic model interpretability library for pytorch,” 2020\.


# Intermediate Qutrit-based Improved Quantum Arithmetic Operations with
Application on Financial Derivative Pricing

Amit Saha, Turbasu Chatterjee, Anupam Chattopadhyay, and Amlan Chakrabarti A.
Saha is with ATOS, Pune, India
E-mail<EMAIL_ADDRESS>A. Saha, T. Chatterjee and A. Chakrabarti are
with A. K. Choudhury School of Information Technology, University of Calcutta,
India A. Chattopadhyay is with School of Computer Science and Engineering,
Nanyang Technological University, Singapore.

###### Abstract

In some quantum algorithms, arithmetic operations are of utmost importance for
resource estimation. In binary quantum systems, some efficient implementation
of arithmetic operations like, addition/subtraction, multiplication/division,
square root, exponential and arcsine etc. have been realized, where resources
are reported as a number of Toffoli gates or T gates with ancilla. Recently it
has been demonstrated that intermediate qutrits can be used in place of
ancilla, allowing us to operate efficiently in the ancilla-free frontier zone.
In this article, we have incorporated intermediate qutrit approach to realize
efficient implementation of all the quantum arithmetic operations mentioned
above with respect to gate count and circuit-depth without T gate and ancilla.
Our resource estimates with intermediate qutrits could guide future research
aimed at lowering costs considering arithmetic operations for computational
problems. As an application of computational problems, related to finance, are
poised to reap the benefit of quantum computers, in which quantum arithmetic
circuits are going to play an important role. In particular, quantum
arithmetic circuits of arcsine and square root are necessary for path loading
using the re-parameterization method, as well as the payoff calculation for
derivative pricing. Hence, the improvements are studied in the context of the
core arithmetic circuits as well as the complete application of derivative
pricing. Since our intermediate qutrit approach requires to access higher
energy levels, making the design prone to errors, nevertheless, we show that
the percentage decrease in the probability of error is significant owing to
the fact that we achieve circuit robustness compared to qubit-only works.

###### Index Terms:

Derivative pricing, Quantum arithmetic, Intermediate qutrit, Quantum resource
estimation, Qudit systems.

##  1 Introduction

Quantum computers are expected to outperform classical computers at certain
computational tasks with an asymptotic advantage [1]. While quantum algorithms
for computationally difficult tasks have favourable asymptotic improvement,
specific run-time estimates are frequently lacking due to the dearth of
efficient implementation of quantum arithmetic operations that are employed as
functions in quantum algorithms [2]. We have tried to address this issue by
designing advanced arithmetic circuits with the adoption of higher energy
level of quantum state. As an application, we consider financial derivative
pricing problem to demonstrate our efficient approach of synthesizing
arithmetic operations in quantum domain.

In this article, we shall be focusing on the usage of quantum algorithms
valuation or the pricing of these financial derivatives. Recently, it has been
shown that quantum approaches to derivative pricing might exhibit quantum
advantage with bounded error [3]. The pricing methodology with a strong focus
on the implementation of the algorithms in a gate-based quantum computer has
also been addressed in [4, 5]. According to the most recent work on the
decomposition of the solution of derivative pricing presented in [6], at the
granular level, one has to take into account the basic building blocks of the
algorithm: The arithmetic operations, which encompass addition, subtraction,
multiplication, square root, exponentiation, and the arcsine. An inefficient
implementation of these blocks can employ colossal noise in the system, hence,
derivative pricing algorithm may suffer with inappropriate outcome.

The goal of this paper is to disintegrate the quantum derivative pricing
algorithm presented in [6] into the arithmetic operations and put more
efficient algorithms for the same at its foundation. In doing so, the methods
prescribed in this paper do hope to carry out an asymptotic reduction of the
complexity prescribed in the paper and improve the error bounds of the
algorithm in its state-of-the-art form by decomposing Toffoli gates with the
adoption of intermediate qutrit approach [7]. All the generalized qutrit gates
[8, 9] have already been successfully implemented on superconducting [10],
trapped ion [11] and photonic systems [12] indicating it is possible to
consider higher level systems apart from qubit-only systems. The Toffoli gate
decomposition technique necessitates access to a higher energy level,
rendering the design vulnerable to errors. Nonetheless, we demonstrate that
the percentage reduction in the probability of error is significant because we
reduced both gate count and circuit depth compared to previous work [6].

Our specific contributions in a nutshell are as follows:

  * •

We employ intermediate qutrits to address basic quantum arithmetic operations
and estimate the resources to show that our approach supersedes the current
techniques on the basis of circuit depth and circuit robustness.

  * •

Since arithmetic operations are an integral aspect of derivative pricing,
hence we exhibit this as an example for application efficiently.

  * •

Our numerical analysis establishes that adoption of intermediate qutrit for
Toffoli decomposition is sublimer than the existing works by obtaining a
percentage increase in the probability of success.

The rest of this article is organized as follows: Section 2 exhibits relevant
preliminaries about Derivative pricing with arithmetic operations. Section 3
demonstrates our intermediate qutrit approach to quantum arithmetic
operations, and Section 4 analysis the resources required for proposed quantum
arithmetic operations. The performance of the Toffoli decomposition with
intermediate qutrit under various types of noise is presented in Section 5.
Section 6 captures our concluding remarks.

##  2 Derivative Pricing

In finance, the term ‘derivative’ refers to a contract that derives its
pricing from an underlying financial entity, such as, asset, index and
interest rate. A derivative contract is typically valid until its expiration
date and is issued between an issuer and a holder. History tells us that these
derivatives date way back to the time of Aristotle [13], and ever since then,
these financial instruments saw a massive boom in trade during the last fifty
years and have developed into complex financial instruments. The complexity of
pricing a derivative in the modern market scenario is due to the nature of the
underlying, on which they are being valued. Moreover, these financial
instruments can be subject to a broad spectrum of usage, e.g., valuation,
arbitrage, speculation and hedging. Calculating the fair value through
derivative pricing can be difficult due to the stochastic nature of the
parameters on which they are defined. Hence, many numerical approaches for
derivative pricing are frequently used, with Monte Carlo being one of the most
prominent due to its versatility and ability to handle stochastic parameters
generically [14]. Monte Carlo methods, despite their appealing qualities in
derivative pricing, typically demand a lot of computer resources to generate
reliable option price estimates, especially for complex options. It is evident
from the literature that a quantum computer may provide novel ways to solve
computationally intensive problems by leveraging quantum mechanical laws [1].
More specifically, there have been multiple approaches to derivative pricing
on the quantum frontier. We, however, focus our paper on the works of
Chakrabarti et. al. [6], wherein we come across rigorous resource estimates
for executing derivative pricing on a quantum computer.

The price of an underlying asset(s) is generally modeled as a stochastic
process under the pretext of ”no arbitrage,” which assumes that an underlying
asset(s) may not be priced differently in different markets, such that, there
are no profits from trading between markets. The Black-Scholes method is used
to model the evolution of the value of a financial asset as a geometric
Brownian motion. Therefore, let $\vec{S^{t}}\in\mathbb{R}^{d}_{+}$ be a vector
at time $t$ for $d$ underlyings. Let
$(\vec{S^{0}},\vec{S^{1}}\dots\vec{S^{T}})=\omega\in\bar{\Omega}$ be a path of
a discrete-time multivariate stochastic process describing the values of the
underlying assets. The probability density function is denoted by
$\bar{p}(\bar{\omega})$. Let
$\bar{f}(\bar{\omega})=f(\vec{S^{0}},\dots\vec{S^{T}})\in\mathbb{R}$ be the
discounted payoff of some derivative on those assets. In order to evaluate the
price of the derivative, we would calculate

$\mathbb{E}(f)=\int_{\bar{\omega}\in\bar{\Omega}}\bar{p}(\bar{\omega})\bar{f}(\bar{\omega})d\bar{\omega}.$
(1)

The pricing for a given derivative can be calculated analytically using a
variety of methods, notably the Black-Scholes model for path-independent
evaluations and Monte-Carlo methods for path-dependent evaluations, the likes
of autocallables and Target redemption forwards (TARFs). Computationally, it
has been noted that the path-independent derivative is less intensive, while
path-dependent evaluations still remain to be more intensive. Using Monte-
Carlo methods classically, given $M$ paths, the derivative pricing accuracy
converges as $O(1/\sqrt{M})$. This bound was improved upon by Montenaro and
was found to be $O(1/M)$ in the quantum realm using quantum algorithms based
on amplitude estimation, thus paving the way for investigations in derivative
pricing, risk analysis and overall, quantum finance.

In order to price the derivatives on a discrete variable quantum computer
(DVQC), the paths need to be discretized and then mapped onto quantum states.
Therefore the expectation now looks like

$\mathbb{E}(f)=\sum_{{\omega}\in{\Omega}}{p}({\omega}){f}({\omega}).$ (2)

For path-dependent derivatives, the paths are generated using the underlying
stochastic process and then the expected payoff is calculated using the
estimator:

$\mathbb{E}(f)\approx\frac{1}{N}\sum_{\omega=1}^{M}f(\omega),$ (3)

which converges to the true expected value with error $\epsilon=O(M^{-1/2})$
by the central limit theorem. This convergence has been shown to exhibit
quadratic speedup to $\epsilon=O(M^{-1})$ when using quantum amplitude
estimation [15] for Monte-Carlo processes [16, 3, 17]. Quantum amplitude
estimation takes a unitary operator $\mathcal{A}$, acting on $n+1$ qubits such
that,

$\mathcal{A}|0\rangle_{n+1}=\sqrt{1-a}|\psi_{0}\rangle_{n}|0\rangle+\sqrt{a}|\psi_{1}\rangle_{n}|1\rangle,$
(4)

where the parameter $a$ is unknown and the final qubit acts as a label and is
used to distinguish the $|\psi_{0}\rangle$ states from the $|\psi_{1}\rangle$
states.

The goal of the quantum amplitude estimation algorithm is to estimate the
unknown parameter $a$. This is done by repeatedly applying the Grover operator
$\mathcal{Q}=\mathcal{A}S_{0}\mathcal{A}^{\dagger}S_{\psi_{0}},$ where
$S_{0}=\mathbb{I}-2|0\rangle_{n+1}\langle 0|_{n+1}$ and
$S_{\phi_{0}}=\mathbb{I}-2|\psi_{0}\rangle_{n}|0\rangle\langle
0|\langle\psi_{0}|_{n}$ are reflection operators. The parameter $a$ can be
determined with an accuracy of $O(M^{-1})$ using quantum phase estimation and
quantum Fourier transform [1]. However, due to the use of the expensive
quantum Fourier transform, this method has undergone development [18, 19, 20,
21, 22, 23] and the Iterative Quantum Amplitude Estimation (IQAE) [20], which
has been regarded as the most efficient methods of the quantum amplitude
estimation has seen its use in [6].

The basic approach to the derivative pricing algorithm consists of the
following steps:

  1. 1.

Apply some operator $\mathcal{P}$ to the state $|0\rangle$, such that

$\mathcal{P}|0\rangle=\sum_{\omega}\sqrt{p(\omega}|\omega\rangle$

  2. 2.

Calculate $\delta(\omega)=\arcsin\sqrt{\tilde{f}(\omega)}$, such that

$\sum_{\omega}\sqrt{p(\omega)}|\omega\rangle|\delta(\omega)\rangle$

  3. 3.

Introduce an ancilla qubit and use controlled rotations to rotate the value of
$\tilde{f(\omega)}$ register into its amplitude, given by

$\sum_{\omega}\sqrt{p(\omega)(1-{\tilde{f}(\omega))}}|\omega\rangle|0\rangle+\sum_{\omega}\sqrt{p(\omega)({\tilde{f}(\omega))}}|\omega\rangle|1\rangle$

  4. 4.

Use quantum amplitude estimation and extract the probability of the ancilla
being $|1\rangle$

The output yields the discretized expected payoff,
$\mathbb{E}(\tilde{f})=\sum_{\omega}p(\omega)\tilde{f}(\omega)$, subsequently
rescaled to yield
$\mathbb{E}(f)=(f_{max}-f_{min})\mathbb{E}(\tilde{f})+f_{min}$.

In order for this algorithm to have a quantum advantage, one needs to take
into account, the costs for path loading for the payoff calculation. The
loading of general probability distributions have been proven to be
exponentially hard. Therefore, one needs to find an efficient path loading
operator $\mathcal{P}$. The Grover-Rudolph method is an efficient method for
loading distributions which are integrable. This however is not useful for
applications in derivative pricing as the probability distributions herein are
not integrable and the paths are calculated using quantum Monte Carlo
methodologies. Here, the author of [6] uses a variational method, termed as
the Re-parameterization method to tackle the problem of path loading.

The Re-parameterization method works by observing that probability
distributions may be loaded by preparing, in parallel, several standard normal
distributions, and applying affine transformations to shape them into the
desired distribution with the required mean and standard deviation. The steps
for the Re-parameterization method can be outlined as follows:

  1. 1.

Apply $dT$ Gaussian operators $\mathcal{G}$, to $ndT$ qubits, thereby
constructing:

$\bigotimes_{t=1}^{T}\bigotimes_{j=1}^{d}\mathcal{G}|0\rangle_{n}=\sum_{\omega_{\bar{R}}}\sqrt{p(\omega_{\bar{R}}})|\omega_{\bar{R}}\rangle_{ndT},$

where $\omega_{\bar{R}}$ runs over all $2^{ndT}$ different realizations of the
multivariate standard Gaussian, and $p(\omega_{\bar{R}})$ are the
corresponding probabilities.

  2. 2.

Given $\Sigma=LL^{T}$ is the Cholesky decomposition of the covariance matrix,
perform the affine transformation
$\vec{R}^{t}=\vec{\mu}^{t}+L^{T}\vec{\bar{R}}^{T}$ to adjust the mean and
standard deviation of each Gaussian. These will be used to calculate the asset
prices from the log-returns given by

$S_{j}^{t^{\prime}}=S_{j}^{t=0}e^{\mu_{j}t^{\prime}+\sum_{i=0}^{d}L_{ji}^{T}\bar{R_{i}}^{t^{\prime}}}=e^{lnS_{j}^{t=0}+\mu_{j}t^{\prime}+\sum_{i=0}^{d-1}L_{ji}^{T}\bar{R_{i}}^{t^{\prime}}}$

  3. 3.

If the payoffs can be calculated directly from the log-returns, then the
quantity $\delta(\omega_{R})=arcsine\sqrt{\tilde{f}(\omega_{R})}$ can be
calculated in the quantum register as follows:

$\sum_{\omega_{R}}\sqrt{p(\omega_{R})}|\omega_{R}\rangle|\delta(\omega_{R})\rangle,$

where $\omega_{R}$ are the paths and $p(\omega_{R})$ are the corresponding
probabilities. If the payoff is defined in terms of prices and not just log-
returns, then price path $\omega$ is calculated for each asset using

$\vec{S}^{t}=\vec{S}^{0}e^{\sum_{j=1}^{t}\vec{R}^{j}}.$

This can be done in parallel for each asset.

  4. 4.

An ancilla qubit is introduced and the value of $\tilde{f}(\omega_{R})$ is
rotated into its amplitude:

$\sum_{\omega}\sqrt{p(\omega)(1-{\tilde{f}(\omega))}}|\omega\rangle|0\rangle+\sum_{\omega}\sqrt{p(\omega)({\tilde{f}(\omega))}}|\omega\rangle|1\rangle$

  5. 5.

Quantum amplitude estimation is used to extract the probability of the ancilla
being $|1\rangle$

The above routine can be visualized in figure 1:

Figure 1: Circuit computing T registers containing cumulative log-returns
$\bar{R^{t^{\prime}}_{i}}$ for each timestep $t^{\prime}\in[0,T]$. The $T$
Gaussian operators $\mathcal{G}$ are applied to the registers to generate
Gaussian probability distributions at each timestep. The ADD operators are
then used in series to transform
$|x\rangle|y\rangle|0\rangle\mapsto|x\rangle|y\rangle|x+y\rangle$ [6].

As the Gaussian path loading operator $\mathcal{G}$ takes the place of the
operator $\mathcal{P}$, it is imperative to talk about the construction of
$\mathcal{G}$. The authors of [6] use a Variational Quantum Eigensolver
approach that uses a parameterized circuit, which in turn produce a
parameterized quantum state $|\psi(\\{\theta\\})\rangle$, which approximately
represents the target state $|\phi_{0}\rangle$. The parameters $\\{\theta\\}$
are updated using a classical optimizer that optimizes expectation value of a
suitable cost function. This can be formulated by

$E_{0}=\langle\psi_{0}|H|\psi_{0}\rangle,$ (5)

where energy expectation $E$, reaches its ground state $E_{0}$, when
calculated on a target state. It is noted that the energy Hamiltonian of the
quantum harmonic oscillator is given by:

$H=\frac{P^{2}}{2m}+\frac{m(X-x_{0})^{2}}{2},$ (6)

furthermore, by clever observation, it is noted that this Hamiltonian has a
ground state energy

$\phi_{0}(x)=(\frac{m}{\pi})^{1/4}e^{-m(x-x_{0})^{2}},$ (7)

which is a Gaussian function. Here $X$ is the position operator in real space,
$P=-i\frac{d}{dx}$ is the momentum operator, $m$ is a parameter representing
the variance of the Gaussian distribution, whereas $x_{0}$ is the center of
the distribution. By setting $m=1/(2\sigma^{2})$, one can find the state
$\psi_{0}(x)$, such that $\psi_{0}^{2}(x)=\mathcal{N}(x_{0},\sigma)$.

In order to calculate these on a quantum computer one must observe that
$X^{2}$ is diagonal in the $Z$-basis, therefore it can be measure directly
from the qubit register as $N_{counts}$ wave function collapses on
measurement. The $P^{2}$ is diagonal on the momentum basis and therefore a
centering Quantum Fourier Transform (QFT) is invoked after the state
preparation block. Since the calculations are done on the discrete position
space, the transformation $x_{i}=-w+i\Delta x$ is used, where
$i=0,\cdots,2^{n}-1$ and $\Delta x=2w/2^{n}$. Without loss of generality, if
the center is chosen to be at zero, the energy $E=E_{X^{2}}+E_{P^{2}}$ is
calculated as follows:

$E_{X^{2}}=\frac{1}{N_{shots}}\sum^{\mathcal{N}}_{j=0}\frac{m}{2}N_{counts}(j)(j\times\Delta
x-x_{0})^{2}$ (8)
$E_{P^{2}}=\frac{1}{N_{shots}}\sum^{\mathcal{N}}_{j=0}\frac{1}{2m}N_{counts}(j)(j\times\Delta
p)^{2}$ (9)

where, $N_{shots}$ is the total number of circuit repetitions for the spacial
and the momentum basis. Thus derivative pricing problem can be solved using
re-parameterization method followed by payoff calculation efficiently with the
help of arcsine and square root quantum operation. But there is no free lunch,
hence, these methods have to deal with several errors which are discussed
forthwith.

#### Error Analysis

The authors of [6] have characterized the errors induced in their approach as
four main components: Truncation Error, Discretization Error, Amplitude
Estimation Error and arithmetic error. First three are discussed here and the
arithmetic error is discussed in the next subsection 2.1 for the sake of
understanding.

  1. (a)

Truncation Error. Given the fault-tolerant setting of the algorithm presented
in [6], to feasibly compute the infinitely many path integrals, the domain of
integration is restricted to a range $[B_{l},B_{u}]$, thereby leaving out a
probability mass $\alpha$. Given an upper bound
$f_{\delta}=f_{max}^{disc}-f_{min}^{disc}$ on the discounted payoff as
calculated, and an upper bound $P_{max}$ on the density function at each step,
a truncation error of $\epsilon_{trunc}=P^{T}_{max}f_{\delta}\alpha$ is
incurred. For $dT$ different $n$-qubit registers that are $w$ standard
deviations around the mean for each timestep, the truncation error is given
by:

$\epsilon_{trunc}\leq 2dTe^{-w^{2}/2}$ (10)

  2. (b)

Discretization Error. This error arises when approximating the integral over
finite grid of points and can be reduced by increasing the number of qubits
$n$. Assuming $\beta$ is an upper bound on the second derivative of the
integrand and given $n$ qubits, thereby discretizing the integral domain over
$2^{ndT}$ cells, the discretization error $\epsilon_{d}isc$ is given by:

$\epsilon_{disc}=\frac{\beta(B_{u}-B_{l})^{dT+2}}{24\cdot 2^{2n}}$ (11)

  3. (c)

Amplitude Estimation Error. An error of $\epsilon_{amp}$ is incurred by the
Amplitude Estimation subroutine when repeating the state preparation and
pricing procedure $1/\epsilon_{amp}$ times.

A key observation that lays the very foundation of this paper is that the
algorithm heavily depends on quantum arithmetic operations in its various
aspects of its calculation in the discrete computational domain. It is
therefore imperative, that these operations be probed, thereby paving the way
for more efficient calculation methods in the quantum discrete arithmetic
operation domain. These quantum arithmetic operations are further elaborated
in the subsequent subsection. Since our approach of solving derivative pricing
uses higher dimensional quantum systems, an additional error apart from these
four has been inducted automatically, which is thoroughly described in Section
5.

###  2.1 Quantum Arithmetic Operations

This section highlights the background for common quantum arithmetic
operations. These operations are used in resource estimation and error
analysis in derivative pricing as discussed in previous section. In this
section, resources are usually reported as Toffoli cost as we are working in
the fault-tolerant setting. As per the state-of-the-art work, they also
estimate the optimized T-depth of the circuits by decomposing Toffoli gate in
a Clifford + T gate set [24]. They decomposed the Toffoli gates with a T-depth
of one using four ancilla qubits as shown in Fig. 2 [24]. Combining Fig. 2(a)
and 2(b), one can obtain a representation of the Toffoli gate of T -depth 1
and overall depth 7. They have also tried to parallelize the resulting
circuits wherever possible to obtain the optimized depth.

Figure 2: (a)Toffoli decomposition; (b)three-qubit phase gate decomposition

The authors of [6] performed all the calculations in fixed-point arithmetic
similarly to [2], which allows us to use the described quantum techniques for
reversible function evaluation. An $n$-bit representation of a number $x$ is

$x=\underbrace{x_{n-1}\cdots x_{n-p}}_{p}.\underbrace{x_{n-p-1}\cdots
x_{0}}_{n-p},$ (12)

where $x_{i}\in{0,1}$ denotes the $i$-th bit of the binary representation of
$x$ and $p$ denotes the number of bits to the left of the binary decimal
point. The choice of $n$ and $p$ controls the error that one can allow in each
calculation, we allow the same approximation for arithmetic error as in [6].
Let $Toffoli\\_count$ and $T\\_depth$ denote the number of Toffoli gates and
the T-depth required to compute an arithmetic function as per the state-of-
the-art work.

##### Addition/Subtraction

As per [6, 25], one can perform addition of two $n$-qubit registers in place
with a Toffoli cost,

$Toffoli\\_count_{add}=10n-3w(n)-3w(n-1)-3\log_{2}n\\\ -3\log_{2}(n-1)-7$ (13)

where $w(n)$ denotes the number of ones in the binary expansion of $n$, and a
Toffoli depth,

$T\\_depth_{add}=\lfloor\log_{2}(n)\rfloor+\lfloor\log_{2}(n-1)\rfloor+\lfloor\log_{2}\left(\frac{n}{3}\right)\rfloor\\\
+\lfloor\log_{2}\left(\frac{n-1}{3}\right)\rfloor+8.$ (14)

For subtraction, the Toffoli count remains same as addition.

##### Multiplication

For multiplication the authors follow the method, which uses the controlled
addition circuit in [26] and requires a Toffoli count,

$Toffoli\\_count_{\text{mul}}(n,p)=\frac{3}{2}n^{2}+3np+\frac{3}{2}n-3p^{2}+3p.$
(15)

This method can also be used for division, where the Toffoli count remains
same as multiplication. The fixed-point multiplication method’s controlled
additions necessitate ancilla qubits proportional to the register size, but
the circuits support uncomputing the ancillas, allowing them to be reused for
each consecutive addition that is not done in parallel. We may also
parallelize each multiplication circuit by viewing each factor’s register as
$z\geq 1$ separate registers of size $n/z$, and each controlled addition for
the $z$ subregisters can happen in parallel. To aggregate the $z$ sub-results
into the final result, $n\cdot(z-1)$ more qubits and $z-1$ additions are
required. $z=1$ indicates that no additional parallelization is used. We can
get a total T-depth cost of parallelized fixed-point multiplication by
parallelizing the pairwise accumulation adds as well,

$T\\_depth_{\text{mul}}(n,z)=\lceil\frac{n}{z}\rceil\cdot(T\\_depth_{add}+6)+\lceil\log_{2}z\rceil\cdot
T\\_depth_{add}.$ (16)

$(\text{T}_{\text{add}}+6)$ is the T-depth of a controlled addition discussed
in the Addition/Subtraction section.

##### Square Root

In [6], they employ the square root algorithm from [2], which has the Toffoli
count,

$Toffoli\\_count_{\text{sq}}(n,p)=\frac{n^{2}}{2}+3n-4.$ (17)

The T-depth of this algorithm as reported by the authors is

$T\\_depth_{\text{sq}}(n)=5n+3$ (18)

where $2n+1$ qubits are required.

##### Exponential

In [6], the authors developed a generic quantum technique that uses a parallel
piecewise polynomial approximation to generate smooth classical functions as
per [27], which they used to estimate the computing resources for
exponentials. The procedure takes two parameters, $k$ and $M$, which regulate
the piecewise approximation polynomial degree and the number of domain
subintervals, respectively. The total number of Toffolis is calculated as
follows:

$Toffoli\\_count_{\text{exp}}(n,p,k,M)=\frac{3}{2}n^{2}k+3npk+\frac{7}{2}nk-3p^{2}d\\\
+3pk-d+2Md(4\lceil\log_{2}M\rceil-8)+4Mn.$ (19)

##### Arcsine

The arcsine function is computed using the above exponential approach, which
needs $k$ iterations of multiplication and addition, with $k$-degree
polynomials employed for approximation. It also necessitates $M$ comparison
circuits between the $n$-qubit input register and a classical value for $M$
specified subintervals. With the use of the comparator from [25] with T-depth
of $2\lfloor\log_{2}(n-1)\rfloor+5$, the T-depth of a parallel polynomial
evaluation circuit is

$T\\_depth_{\text{pp}}(n,z)=k\left(T\\_depth_{\text{mul}}(n,z)+T\\_depth_{\text{add}}\right)\\\
+M(2\lfloor\log_{2}(n-1)\rfloor+5),$ (20)

where $z$ is the optional parallelization factor for the multiplication
circuit introduced in the resource estimation above.

The total Toffoli count for computing $\ket{\arcsin\sqrt{x}}$ as per [2] is

$Toffoli\\_count_{\text{arcsq}}(n,p,k,M)=\\\
k\left(\frac{3}{2}n^{2}+n(3p+\frac{7}{2})-3(p-1)p-1\right)\\\
+\frac{n^{2}}{2}+11n+2Md(4\lceil\log_{2}M\rceil-8)+4Mn-2.$ (21)

The T-depth for computing $\arcsin(\sqrt{x})$ of a number $x$ represented in a
register of size $(n,p)$, calculated as akin to the exponential is

$T\\_depth_{\text{arcsq}}(n,p,z)=T\\_depth_{\text{sq}}(n)+T\\_depth_{\text{pp}}(n,z)+8n+6,$
(22)

where $T\\_depth_{\text{sq}}(n)=5n+3$ is the T-depth for the square root
algorithm from [27]. Next we portray our approach of intermediate qutrit on
quantum arithmetic operations.

##  3 Quantum Arithmetic Operations with Intermediate Qutrits

This section first describes the Toffoli decomposition with the help of
intermediate qutrit that we have adapted from [7]. Thenceforth, we discuss
about one of the quantum arithmetic operations $i.e.,$ quantum adder with
intermediate qutrits [28, 29]. Later we have exhibited quantum multiplier
using intermediate qutrits with an example implementation. We have simulated
this multiplier circuit on Google Colab platform [30] and the code is
available at https://github.com/LegacYFTw/NTU. These two operations, adder and
multiplier, are the basic building blocks of other arithmetic operations like
square root, exponential and arcsine, which are used in derivative pricing.
Therefore, we vividly discuss about quantum adder and multiplier and their
implementation further in this section.

###  3.1 Toffoli Decomposition with Intermediate Qutrits

In [7, 31], the authors showed that we may occupy the $\ket{2}$ state
temporarily during computation, hence temporarily ternary. Maintaining binary
input and output allows this circuit construction to be inserted into any pre-
existing qubit-only circuits. A Toffoli decomposition via qutrits has been
portrayed in Fig. 3 [7, 31]. More specifically the goal is to carry out a NOT
operation on the target qubit (third qubit) as long as the two control qubits,
are both $\ket{1}$. First, a $\ket{1}$-controlled $X_{+1}$, where $+1$ is used
to denote that the target qubit is incremented by $1\ (\text{mod }3)$, is
performed on the first and the second qubits. This upgrades the second qubit
to $\ket{2}$ if and only if the first and the second qubits were both
$\ket{1}$. Then, a $\ket{2}$-controlled $X$ gate is applied to the target
qubit. Therefore, $X$ is executed only when both the first and the second
qubits were $\ket{1}$, as expected. The controls are reinstated to their
original states by a $\ket{1}$-controlled $X_{-1}$ gate, which reverses the
effect of the first gate. That the $\ket{2}$ state from ternary quantum
systems can be used instead of ancilla to store temporary information, which
is the most important aspect in this decomposition. Thus, to decompose Toffoli
gate, 3 generalized ternary CNOT gates are sufficient with circuit depth 3. In
fact, no T gate is required.

Figure 3: An example of Toffoli decomposition with intermediate qutrit, where
input and output are qubits. The red controls activate on $\ket{1}$ and the
blue controls activate on $\ket{2}$. The first gate temporarily elevates
$q_{1}$ to $\ket{2}$ if both $q_{0}$ and $q_{1}$ were $\ket{1}$. $X$ operation
is then only performed if $q_{1}$ is $\ket{2}$. The final gate acts as a miror
of first gate and restores $q_{0}$ and $q_{1}$ to their original state [7]

.

###  3.2 Quantum Adder with Intermediate Qutrits

We have now demonstrated quantum adder circuit from [29, 25] on two four-bit
registers $A$ and $B$ with a carry-out bit using ancilla as shown in Fig. 4.
The sum $S$ is computed in-place on register B while A is untouched and the
ancilla are restored to $\ket{0}$. In [29], for the first time, the authors
showed how this adder can be efficiently implemented with the help of
intermediate qutrits with respect to gate count and circuit depth instead of
conventional way of decomposition. The author achieves an advanced adder by
decomposing all the Toffoli gate presented in Fig. 4 with the discussed
intermediate qutrit method. This work provides us enough motivation to work
upon others quantum operations with intermediate qutrit. Therefore, we present
an example of implementing a multiplier with the adoption of intermediate
qutrit for better understanding.

Figure 4: An example A+B quantum Adder with 4-bit A and 4-bit B [29, 25]

###  3.3 Quantum Multiplier with Intermediate Qutrits

Let’s put some light on quantum multiplier here in this subsection. We have
considered multiplication of $5\times 3$ as an example to illustrate our
approach of designing quantum multiplier with intermediate qutrit. In Fig.
5(a), a multiplier circuit has been presented considering the mentioned
example as per [26], in which all the qubits are initialized with $\ket{0}$.
In this circuit, first five qubits ($q_{0}$ \- $q_{4}$) are the input qubits,
where first two qubits ($q_{0}$ and $q_{1}$) represent the number 3 by
applying two NOT gates on them and other three qubits ($q_{2}$, $q_{3}$ and
$q_{4}$) represent the number 5 by applying two NOT gates on qubits $q_{2}$
and $q_{4}$. Next, we perform multiply operation on these qubits by applying
Toffoli gates and stores the value on ancilla qubits ($q_{5}$ \- $q_{10}$).
Now, we carry out addition by applying CNOT gates on ancilla qubits. Finally,
to get the output of $5\times 3$, we shall measure the qubits ($q_{5}$,
$q_{10}$, $q_{11}$ and $q_{12}$). Further, all the Toffoli gates presented in
Fig. 5(a) are decomposed using intermediate qutrit approach as shown in Fig.
5(b) to achieve asymptotic improvement of the circuit. Our numerical analysis
also yields $5\times 3=15$ perfectly. Since the circuits of quantum adder and
multiplier are verified, the focus shifts to resource required to perform all
the discussed quantum operations using intermediate qutrits.

Figure 5: (a) Quantum Multiplier Circuit for the multiplication of $5\times
3$; (b) Quantum Multiplier with Intermediate Qutrit for the multiplication of
$5\times 3$.

##  4 Resource Estimation and Analysis

As shown in the proposed approach, we have synthesized the quantum arithmetic
operations via intermediate qutrits, in which, three generalized ternary CNOT
gates are used to decompose the Toffoli gate without any ancilla. Hence, no T
gate has been used in any proposed circuit synthesis. Therefore, T-depth
becomes zero in our proposed approach. The overall circuit depth for Toffoli
decomposition has now become three as compared to seven. Since there are no T
gates in our proposed circuits, the resource analysis is based on the count of
generalized ternary CNOT gate, which is a Clifford gate. It also needs to be
noted that the additional four ancilla qubits are not required to decompose
Toffoli gate, otherwise the number of logical qubits remain same for the
derivative pricing as per [6], as no other optimization with respect to
logical qubits is presented in this article. Hence, from now on we shall only
discuss about gate count or circuit depth of derivative pricing problem.

##### Addition/Subtraction

As per our proposed approach, one can perform addition of two $n$-qubit
registers in place with a CNOT-cost,

$CNOT\\_count_{add}=30n-9w(n)-9w(n-1)-9\log_{2}n\\\ -9\log_{2}(n-1)-21$ (23)

where $w(n)$ denotes the number of ones in the binary expansion of $n$. For
subtraction, the CNOT count remains same as addition.

##### Multiplication

For multiplication if one can follow our proposed method, then the CNOT count
becomes,

$CNOT\\_count_{\text{mul}}(n,p)=\frac{9}{2}n^{2}+9np+\frac{9}{2}n-9p^{2}+9p.$
(24)

This method can also be used for division, where the CNOT count remains same
as multiplication.

##### Square Root

If one can employ our proposed approach for the square root algorithm, then
the CNOT count becomes,

$CNOT\\_count_{\text{sq}}(n,p)=\frac{3n^{2}}{2}+9n-12.$ (25)

##### Exponential

As per our proposed approach, the total number of ternary CNOT is given by

$CNOT\\_count_{\text{exp}}(n,p,k,M)=\frac{9}{2}n^{2}k+9npk+\frac{21}{2}nk-9p^{2}d\\\
+9pk-3d+6Md(4\lceil\log_{2}M\rceil-8)+12Mn.$ (26)

##### Arcsine

The total ternary CNOT count for computing $\ket{\arcsin\sqrt{x}}$ is

$CNOT\\_count_{\text{arcsq}}(n,p,k,M)=\\\
3k\left(\frac{3}{2}n^{2}+n(3p+\frac{7}{2})-3(p-1)p-1\right)+\frac{3n^{2}}{2}\\\
+33n+6Md(4\lceil\log_{2}M\rceil-8)+12Mn-26.$ (27)

###  4.1 Comparative Analysis

As discussed, the Toffoli decomposition with intermediate qutrit is novel not
only for its depth optimization from 7 to 3 or gate count optimization from 25
to 3 as compared to [24], but also it does not require any T gates. Hence to
execute required quantum arithmetic operations like arcsine and square root
for derivative pricing, T-depth and T-cost become 0 for the proposed
methodology as discussed in this article. Since the T gates are more expensive
than other gates in terms of space and time cost due to their increased
tolerance to noise errors, our method of implementing derivative pricing
problem is superior to the method proposed in [6]. As there are no T gates in
our methodology, the resources for all the arithmetic operations for
derivative pricing are presented in the form of ternary CNOT gates, which is
thoroughly discussed earlier in this section. It can be easily observed that
the overall CNOT-cost for derivative pricing is much more improved as compared
to [6], since they are decomposed their Toffoli gate with 16 CNOT gates and as
per our decomposition it requires only 3 CNOT gates. As a case study of
derivative pricing problem in [6], the authors have taken into consideration a
basket autocallable (Auto) with 3 underlyings, 5 payment dates and a knock-in
put option with 20 barrier dates. They found that the benchmark use case that
they examined for re-parameterization method of derivative pricing, required
T-cost of 12 billion, T-depth of 54 million and overall circuit depth at least
378 million. In our case, both of these T-cost and T-depth become 0, while the
ternary CNOT-cost and overall circuit depth are 162 million respectively.
These results evidently show that our method outperforms the run-time of the
state-of-the-art algorithm for derivative pricing quite comprehensibly since
gate count and circuit depth have been significantly improved. Although our
circuit constructions have adopted higher dimensional gates, our used
decomposition scales favorably in terms of asymptotically fewer gate errors
and idle errors as our gate count and circuit depth is asymptotically lower,
which is elaborated upon in next section.

##  5 Error Analysis of Toffoli decomposition with Intermediate qutrits

Decoherence, noisy gates, and other sorts of errors can occur in any finite-
dimensional quantum system. It has been proven that using higher dimensional
states other than binary systems causes the system to have more errors. The
impact of these inaccuracies on the Toffoli gate decomposition has been
investigated in this section. Although the introduction of qutrits increases
error, the overall error probability of the decomposition is lower than that
of the earlier decomposition [24] since the number of ancilla qubits, gate
count, and depth are reduced.

###  5.1 Generic Error Model

The conventional quantum error or noise model is for gate and relaxation error
[7], which can be expressed by the Kraus Operator formalism [1]. If the
density matrix representation of a (pure) quantum state is
$\sigma=\ket{\Psi}{\bra{\Psi}}$, the evolution of this state for any channel
is represented as the function $\mathcal{E}(\sigma)$:

$\displaystyle\mathcal{E}\left(\sigma\right)=\mathcal{E}\left(\ket{\Psi}\bra{\Psi}\right)=\sum_{i}K_{i}\sigma
K_{i}^{\dagger}$ (28)

where $K_{i}$ are called the Kraus Operators, and $K_{i}^{\dagger}$ is the
matrix conjugate-transpose of $K_{i}$, $\forall$ $i$. The Kraus operator
formulation can also be used to represent the evolution of a state under a
noise model. The Kraus operators, for example, are simply the Pauli matrices
in the depolarization noise model.

####  5.1.1 Gate Errors

In a binary quantum system with only one-qubit and two-qubit gates, there are
four possible error channels for a one-qubit gate, which can be expressed as
products of the two Pauli matrices, a NOT gate, $X=\begin{pmatrix}0&1\\\
1&0\end{pmatrix}$ and a phase gate, $Z=\begin{pmatrix}1&0\\\
0&-1\end{pmatrix}$. The possible error channels are: (i) no-error
$X^{0}Z^{0}=I$, (ii) the phase flip which is the product $X^{0}Z^{1}$, (iii)
the bit flip which is $X^{1}Z^{0}$ and (iv) the phase+bit flip channel given
by $X^{1}Z^{1}$. We can express this one-qubit gate error model in the Kraus
operator formalism in the following manner:

$\displaystyle\mathcal{E}(\sigma)=\sum_{j=0}^{1}\sum_{k=0}^{1}p_{jk}(X^{j}Z^{k})\sigma(X^{j}Z^{k})^{\dagger}$
(29)

where $p_{jk}$ is the probability of the corresponding Kraus operator.

A noisy gate is modelled as an ideal gate followed by an unwanted Pauli
operator [32]. In other words, a one-qubit gate is followed by an unwanted
Pauli $\in\\{X,Y,Z\\}$ with probability $p_{x},p_{y},p_{z}$ respectively; and
a two-qubit gate is followed by an unwanted Pauli $\in\\{I,X,Y,Z\\}^{\otimes
2}\setminus\\{I,I\\}$ with probability $p_{i}\cdot p_{j}$, where
$i,j\in\\{x,y,z\\}$. For the sake of convenience, we represent the one-qubit
and two-qubit gate error probabilities as $p_{1}$ and $p_{2}$ respectively.

In a binary system, there are 2 types each of unwanted $X$ and $Z$ Pauli
errors that can follow a one-qubit gate. Therefore, there are $2^{2}-1$ ways
(without considering the identity error) in which an error can occur after a
one-qubit gate. If $p_{1}$ is the probability of a one-qubit Pauli error, then
the evolution of the system under noisy one-qubit operations can be
represented as in Eq. 30.

$\displaystyle\mathcal{E}(\sigma)=(1-(2^{2}-1)p_{1})\sigma+\sum_{jk\in\\{0,1\\}^{2}\setminus
0*2}p_{jk}K_{jk}\sigma K_{jk}^{\dagger}$ (30)

where $K_{jk}$ represents the various Pauli operators.

Similarly, for two-qubit gates, an unwanted Pauli operator can occur on each
of the two qubits after the gate operation. Therefore, there are $2^{4}-1$
ways (excluding the identity operation on both the qubits) in which a gate can
be noisy. If $p_{2}$ is the probability of two-qubit gate errors, then the
evolution of the system under noisy two-qubit operations is represented as in
Eq. 31.

$\mathcal{E}(\sigma)=(1-(2^{4}-1)p_{2})\sigma+\sum_{jklm\in\\{0,1\\}^{2}\setminus
0*2}p_{jklm}K_{jklm}\sigma K_{jklm}^{\dagger}$ (31)

where $p_{jklm}=p_{jk}\cdot p_{lm}$. The probability that the density matrix
remains error free is independent of whether the underlying depolarizing
channel is symmetric or asymmetric. Rather, it depends on the total
probability of error.

Our used decomposition here deals with two-qutrit gates only on ternary
quantum systems. In general, for the decomposition of a Toffoli gate, our used
method uses up to 3 dimension. Therefore, for a $3$-dimensional system, the
error in our system scales as $\mathcal{O}(3^{4})$ as shown in Eq. 32.

$\mathcal{E}(\sigma)=\\{1-(3^{4}-1)p_{2}\\}\sigma+\sum_{\begin{subarray}{c}jklm\in\\\
\\{0,1,2,\dots,3\\}^{4}\setminus 0000\end{subarray}}p_{jklm}K_{jklm}\sigma
K_{jklm}^{\dagger}$ (32)

In Table I, we show the decrease in the probability of no-error for two-qutrit
gates due to the usage of higher dimensions for ternary systems.

TABLE I: Probability of success of two-qutrit gates due to the usage of higher
dimensions

Dimension $d$ | without our decomposition | with our decomposition
---|---|---
2 | $1-15p_{2}$ | $1-81p_{2}$

####  5.1.2 Idle error:

In quantum devices, idle errors mainly focus on the relaxation from higher to
lower energy levels. Amplitude damping is another name for this. This noise
channel takes qutrits to lower states in an irreversible manner. For qubits,
the only amplitude damping channel is from $\ket{1}$ to $\ket{0}$, and we
denote this damping probability as $\lambda_{1}$. For qubits, the Kraus
operators for amplitude damping are:

$\displaystyle K_{0}=\begin{pmatrix}1&0\\\
0&\sqrt{1-\lambda_{1}}\end{pmatrix}\text{\quad and
\quad}K_{1}=\begin{pmatrix}0&\sqrt{\lambda_{1}}\\\ 0&0\end{pmatrix}$ (33)

For qutrits, we also model damping from $\ket{2}$ to $\ket{0}$, which occurs
with probability $\lambda_{2}$. For qutrits, the Kraus operator for amplitude
damping can be modeled as:

$K_{0}=\begin{pmatrix}1&0&0\\\ 0&\sqrt{1-\lambda_{1}}&0\\\
0&0&\sqrt{1-\lambda_{2}}\end{pmatrix}\text{, }$ $\displaystyle
K_{1}=\begin{pmatrix}0&\sqrt{\lambda_{1}}&0\\\ 0&0&0\\\
0&0&0\end{pmatrix}\text{\quad and
\quad}K_{2}=\begin{pmatrix}0&0&\sqrt{\lambda_{2}}\\\ 0&0&0\\\
0&0&0\end{pmatrix}$ (34)

In each Kraus Operator $K_{i}$, the value of $\lambda_{i}\propto
exp(-t/T_{1_{i}})$, where $t$ is the duration of the computation, and
$T_{1_{i}}$ are the relaxation time. We have qubit quantum devices, where
$T_{1_{1}}\simeq 100\mu s$ in some higher end IBM Quantum Devices [33].
However, due to the lack of qudit quantum computers, we do not have explicit
values of other $T_{1_{i}}$’s except $30\mu s$ for qutrit ($T_{1_{2}}$)
quantum devices [34]. Nevertheless, the length of time depends on the circuit
depth. As a result, by reducing the circuit depth, idle error are reduced.
Therefore, since depth has been optimized, the decoherence owing to our
employed decomposition is significantly lower than the previous decomposition.

###  5.2 Analysis of Success Probability

In [7], the authors advocated the use of higher dimension for efficient
decomposition of Toffoli gates. However, because there was no qudit hardware
at the time, they assumed that the value of $T_{1_{i}}$ for ternary systems is
the same as for binary systems in that article. However, as explained in the
preceding article, currently we have the value of $T_{1_{3}}$ for ternary
systems. As a result, in this section, we apply the method in [24, 6] and our
method in this article to investigate the probability of success in the
decomposed circuit of a Toffoli gate. It is worth noting that, although the
decomposition of [24, 6] requires one-qubit and two-qubit gates, our method
just necessitates two-qutrit ternary gates.

The complexity of decomposition of a Toffoli gate in terms of the number of
gates and depth of the circuit for the method in [24, 6] and our used one are
depicted here. For each Toffoli decomposition as shown in Fig. 2, one requires
7 one-qubit gates and 16 two-qubit gates with overall circuit depth 7, whether
we need 3 two-qutrit gate with circuit depth 3 for our used decomposition.

Small errors in quantum circuit gates can be described as an ideal gate
followed by an undesirable Pauli operator, as discussed in previous
subsections. However, instead of comparing the probability of minor errors in
the circuit, we compare the probability that the circuit remains error-free
(probability of success) as per [35] for the decomposition in [24, 6] and our
employed decomposition, without losing generality.

For any decomposition, the generalized formula for probability of success
($P_{success}$) described in [35, 36] is the product that the individual
components does not fail. In other words,

$P_{success}=\Pi_{gates}({(P_{success~{}of~{}gate})}^{\\#~{}gates}\times
e^{-(depth/T_{1})}),$ (35)

where the first term’s product is the likelihood of all types of gates
employed in the decomposition (one-qubit, two-qubit, two-qutrit), and the
second term is the probability of no relaxation error. Due to the zero in the
power, when a specific type of gate is not employed in a decomposition, the
associated term has a value of $1$. For example, our suggested decomposition
does not require a one-qutrit gate, therefore that term’s contribution to the
product is 1.

Current quantum devices are mostly binary, and the probabilities of one-qubit
and two-qubit gates in the IBMQ Quantum Devices are in the range of $10^{-4}$
and $10^{-2}$ respectively [33]. Moreover, the time $T_{1_{1}}$ of most of the
IBM Quantum Devices are in the range of $100\mu s$. However, in [34], the
authors experimentally showed that the value of $T_{1_{2}}$ for each ternary
gate is $30\mu s$, which we have also assumed for our study. We assume that
the probability of error of each two-qubit and two-qutrit gate is $10^{-2}$,
that of one-qubit gate is $10^{-4}$, and the time $T_{1_{1}}$ is $100\mu s$
and $T_{1_{2}}$ is $30\mu s$ for our simulation.

Figure 6: Probability of success for the decomposition of Toffoli gate using
our used method versus the method in [24, 6]

In Fig. 6, we exhibit the probability of success for the Toffoli gate
decomposition using the method of [24, 6] (which we label as ‘conventional
decomposition’) and our used method. We find that our proposed technique
produces much fewer errors than the decomposition in [24, 6]. This is due to
the fact that our decomposition has fewer gates and is shallower. Although our
decomposition employs a few qutrit gates, which have a higher error
probability due to the curse of dimensionality, our technique is superior due
to the overall large reduction in gate count and depth. In fact, for Toffoli
count 30 in a circuit, our used decomposition has a probability of success of
$\simeq 0.4$, whereas that of [24, 6] has a probability of success of $\simeq
0.01$. Therefore, we obtain a percentage decrease in the probability of error
by $\simeq 40\%$ for Toffoli count 30. Thus, it can be concluded that the
conventional decomposition methods attain $100\%$ error for Toffoli count 30
in a circuit, whereas our used decomposition method yields less erroneous
results for Toffoli count 30 and above in a circuit. A comparative study of
our Toffoli decomposition used in derivative pricing with some previous works
[6, 24] is shown in Table II. Our work outperforms them in terms of T-depth,
overall circuit depth, overall gate count of the circuit and probability of
error.

TABLE II: Comparative analysis between conventional approach [6, 24] and our
approach with qutrits used in derivative pricing problem for the decomposed
circuit of Toffoli gate

| # T | # overall | # two-qutrit | # Gate | Prob. of error (%)
---|---|---|---|---|---
| depth | circuit depth | gates | count | for Toffoli count 30
Decomposition | 1 | 7 | 0 | 25 | 99.95
of [6, 24] |  |  |  |  |
Our Decomposition | 0 | 3 | 3 | 3 | 60

##  6 Conclusion

In this work, we have addressed basic quantum arithmetic operations and
estimated the resources using intermediate qutrits which also demonstrate that
our approach outperforms current techniques in terms of circuit depth and
circuit robustness. Further, as an application, we have shown a novel approach
of implementing derivative pricing problem by decomposing Toffoli gate into
two-qutrit gates with optimized gate count and depth without using any ancilla
qubit. We have given a comparative study on resources for derivative pricing
to establish that our approach is better than the existing state-of-the-art
one [6]. Finally, we have studied the effect of different error models on this
decomposition technique. Our study shows that the few gates in higher
dimensional quantum systems which are used in the used decomposition, are
prone to more errors. Nevertheless, as we have obtained improved gate count
and circuit depth, leading to low total error probability, the gates can
operate with high fidelity as compared to state-of-the art work. Through
numerical simulation, as an instance, we have shown that intermediate qutrit-
based Toffoli decomposition obtained a percentage increase in the probability
of success by $\simeq 40\%$ for Toffoli count 30 in a circuit as compared to
conventional way of Toffoli decomposition. These improved quantum arithmetic
operations pave the way for more detailed time improvement estimate with
intermediate qudit to study the decomposition for other quantum circuits.

## References

  * [1] M. A. Nielsen and I. Chuang, “Quantum computation and quantum information,” 2002\.
  * [2] T. Häner, M. Roetteler, and K. M. Svore, “Optimizing quantum circuits for arithmetic,” 2018. [Online]. Available: https://arxiv.org/abs/1805.12445
  * [3] P. Rebentrost, B. Gupt, and T. R. Bromley, “Quantum computational finance: Monte carlo pricing of financial derivatives,” _Phys. Rev. A_ , vol. 98, p. 022321, Aug 2018. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.98.022321
  * [4] A. Martin, B. Candelas, Á . Rodríguez-Rozas, J. D. Martín-Guerrero, X. Chen, L. Lamata, R. Orús, E. Solano, and M. Sanz, “Toward pricing financial derivatives with an IBM quantum computer,” _Physical Review Research_ , vol. 3, no. 1, feb 2021. [Online]. Available: https://doi.org/10.1103%2Fphysrevresearch.3.013167
  * [5] C. Zoufal, A. Lucchi, and S. Woerner, “Quantum generative adversarial networks for learning and loading random distributions,” _npj Quantum Information_ , vol. 5, no. 1, nov 2019. [Online]. Available: https://doi.org/10.1038%2Fs41534-019-0223-2
  * [6] S. Chakrabarti, R. Krishnakumar, G. Mazzola, N. Stamatopoulos, S. Woerner, and W. J. Zeng, “A threshold for quantum advantage in derivative pricing,” _Quantum_ , vol. 5, p. 463, jun 2021. [Online]. Available: https://doi.org/10.22331%2Fq-2021-06-01-463
  * [7] P. Gokhale, J. M. Baker, C. Duckering, N. C. Brown, K. R. Brown, and F. T. Chong, “Asymptotic improvements to quantum circuits via qutrits,” in _Proceedings of the 46th International Symposium on Computer Architecture_. ACM, jun 2019. [Online]. Available: https://doi.org/10.1145%2F3307650.3322253
  * [8] Y.-M. Di and H.-R. Wei, “Elementary gates for ternary quantum logic circuit,” 2011\. [Online]. Available: https://arxiv.org/abs/1105.5485
  * [9] Y. Wang, Z. Hu, B. C. Sanders, and S. Kais, “Qudits and high-dimensional quantum computing,” _Frontiers in Physics_ , vol. 8, Nov 2020. [Online]. Available: http://dx.doi.org/10.3389/fphy.2020.589504
  * [10] J. Koch, T. M. Yu, J. Gambetta, A. A. Houck, D. I. Schuster, J. Majer, A. Blais, M. H. Devoret, S. M. Girvin, and R. J. Schoelkopf, “Charge-insensitive qubit design derived from the cooper pair box,” _Phys. Rev. A_ , vol. 76, p. 042319, Oct 2007. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.76.042319
  * [11] A. B. Klimov, R. Guzmán, J. C. Retamal, and C. Saavedra, “Qutrit quantum computer with trapped ions,” _Physical Review A_ , vol. 67, p. 062313, Jun 2003. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.67.062313
  * [12] X. Gao, M. Erhard, A. Zeilinger, and M. Krenn, “Computer-inspired concept for high-dimensional multipartite quantum gates,” _Physical Review Letters_ , vol. 125, no. 5, Jul 2020. [Online]. Available: http://dx.doi.org/10.1103/PhysRevLett.125.050501
  * [13] G. Crawford and B. Sen, _Derivates for decision makers_. Wiley, 1996.
  * [14] P. P. Boyle, “Options: A monte carlo approach,” _Journal of Financial Economics_ , vol. 4, no. 3, pp. 323–338, 1977. [Online]. Available: https://www.sciencedirect.com/science/article/pii/0304405X77900058
  * [15] G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum amplitude amplification and estimation,” pp. 53–74, 2002. [Online]. Available: https://doi.org/10.1090%2Fconm%2F305%2F05215
  * [16] A. Montanaro, “Quantum speedup of monte carlo methods,” _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , vol. 471, no. 2181, p. 20150301, sep 2015. [Online]. Available: https://doi.org/10.1098%2Frspa.2015.0301
  * [17] N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, and S. Woerner, “Option pricing using quantum computers,” _Quantum_ , vol. 4, p. 291, jul 2020. [Online]. Available: https://doi.org/10.22331%2Fq-2020-07-06-291
  * [18] Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, “Amplitude estimation without phase estimation,” _Quantum Information Processing_ , vol. 19, no. 2, p. 75, Jan 2020. [Online]. Available: https://doi.org/10.1007/s11128-019-2565-2
  * [19] S. Aaronson and P. Rall, “Quantum approximate counting, simplified,” in _Symposium on Simplicity in Algorithms_. Society for Industrial and Applied Mathematics, jan 2020, pp. 24–32. [Online]. Available: https://doi.org/10.1137%2F1.9781611976014.5
  * [20] D. Grinko, J. Gacon, C. Zoufal, and S. Woerner, “Iterative quantum amplitude estimation,” _npj Quantum Information_ , vol. 7, no. 1, p. 52, Mar 2021. [Online]. Available: https://doi.org/10.1038/s41534-021-00379-1
  * [21] K. Nakaji, “Faster amplitude estimation,” _Quantum Information and Computation_ , vol. 20, no. 13&14, pp. 1109–1123, nov 2020. [Online]. Available: https://doi.org/10.26421%2Fqic20.13-14-2
  * [22] T. Tanaka, Y. Suzuki, S. Uno, R. Raymond, T. Onodera, and N. Yamamoto, “Amplitude estimation via maximum likelihood on noisy quantum computer,” _Quantum Information Processing_ , vol. 20, no. 9, sep 2021. [Online]. Available: https://doi.org/10.1007%2Fs11128-021-03215-9
  * [23] T. Giurgica-Tiron, I. Kerenidis, F. Labib, A. Prakash, and W. Zeng, “Low depth algorithms for quantum amplitude estimation,” 2020. [Online]. Available: https://arxiv.org/abs/2012.03348
  * [24] P. Selinger, “Quantum circuits of $t$-depth one,” _Phys. Rev. A_ , vol. 87, p. 042302, Apr 2013. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.87.042302
  * [25] T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, “A logarithmic-depth quantum carry-lookahead adder,” 2004. [Online]. Available: https://arxiv.org/abs/quant-ph/0406142
  * [26] Y. Takahashi, S. Tani, and N. Kunihiro, “Quantum addition circuits and unbounded fan-out,” 2009. [Online]. Available: https://arxiv.org/abs/0910.2530
  * [27] E. Muñoz Coreas and H. Thapliyal, “T-count and qubit optimized quantum circuit design of the non-restoring square root algorithm,” _J. Emerg. Technol. Comput. Syst._ , vol. 14, no. 3, oct 2018. [Online]. Available: https://doi.org/10.1145/3264816
  * [28] A. Chamoli and C. M. Bhandari, “Groverian entanglement measure and evolution of entanglement in search algorithm for n(= 3, 5)-qubit systems with real coefficients,” _Quantum Information Processing_ , vol. 6, no. 4, p. 255–271, Aug. 2007. [Online]. Available: https://doi.org/10.1007/s11128-007-0057-2
  * [29] J. M. Baker, C. Duckering, and F. T. Chong, “Efficient quantum circuit decompositions via intermediate qudits,” 2020. [Online]. Available: https://arxiv.org/abs/2002.10592
  * [30] E. Bisong, _Google Colaboratory_. Berkeley, CA: Apress, 2019, pp. 59–64. [Online]. Available: https://doi.org/10.1007/978-1-4842-4470-8_7
  * [31] J. M. Baker, C. Duckering, P. Gokhale, N. C. Brown, K. R. Brown, and F. T. Chong, “Improved quantum circuits via intermediate qutrits,” _ACM Transactions on Quantum Computing_ , vol. 1, no. 1, oct 2020. [Online]. Available: https://doi.org/10.1145/3406309
  * [32] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” _Physical Review A_ , vol. 86, no. 3, p. 032324, 2012.
  * [33] “IBM Quantum,” https://quantum-computing.ibm.com/, 2021.
  * [34] L. E. Fischer, D. Miller, F. Tacchino, P. K. Barkoutsos, D. J. Egger, and I. Tavernelli, “Ancilla-free implementation of generalized measurements for qubits embedded in a qudit space,” 2022. [Online]. Available: https://arxiv.org/abs/2203.07369
  * [35] R. Majumdar, D. Madan, D. Bhoumik, D. Vinayagamurthy, S. Raghunathan, and S. Sur-Kolay, “Optimizing ansatz design in qaoa for max-cut,” _arXiv preprint arXiv:2106.02812_ , 2021.
  * [36] A. Saha, R. Majumdar, D. Saha, A. Chakrabarti, and S. Sur-Kolay, “Asymptotically improved circuit for $d$-ary grover’s algorithm with advanced decomposition of $n$-qudit toffoli gate,” 2020. [Online]. Available: https://arxiv.org/abs/2012.04447