# Generalized uncertainty principle and Asymptotic Safe gravity

Gaetano Lambiase<EMAIL_ADDRESS>Dipartimento di Fisica ”E.R.
Caianiello”, Universita’ di Salerno, I-84084 Fisciano (Sa), Italy &
INFN - Gruppo Collegato di Salerno, Italy  Fabio Scardigli111corresponding
author<EMAIL_ADDRESS>Dipartimento di Matematica, Politecnico di
Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy  Department of
Applied Mathematics, University of Waterloo, Ontario N2L 3G1, Canada

###### Abstract

We present a procedure to link the deformation parameter $\beta$ of the
generalized uncertainty principle (GUP) to the two free parameters
$\tilde{\omega}$ and $\gamma$ of the running Newtonian coupling constant of
the Asymptotic Safe gravity (ASG) program. To this aim, we compute the Hawking
temperature of a black hole in two different ways. The first way involves the
use of the GUP in place of the Heisenberg uncertainty relations, and therefore
we get a deformed Hawking temperature containing the parameter $\beta$. The
second way involves the deformation of the Schwarzschild metric due to the
Newtonian coupling constant running according to the AS gravity prescription.
The comparison of the two techniques yields a relation between $\beta$ and
$\tilde{\omega}$, $\gamma$. As a particular case, we discuss also the so
called $\xi$-model. The relations between $\beta$ and $\tilde{\omega}$, $\xi$
allow us to transfer upper bounds from one parameter to the others.

##  I Introduction

It is well-known that the formulation of a consistent quantum theory of
gravity is still an open task in modern theoretical physics. Many of the
approaches to the problem existing today in the literature (for a partial list
see e.g. QG1 ; QG2 ; QG3 ; QG4 ; QG6 ; QG8 ; QG9  and references therein),
share one particular property. Namely, the basic parameters that enter into
the action defining the model at hand, such as Newton’s constant,
electromagnetic coupling, the cosmological constant etc, become scale
dependent quantities. This does not come as a surprise of course, since scale
dependence at the level of the effective action is a generic feature of
ordinary quantum field theory. In theories of gravity, the scale dependence is
expected to modify the horizon, the thermodynamics as well as the quasinormal
modes spectra of classical black hole backgrounds Koch:2016uso ;
Rincon:2017goj ; Contreras:2017eza ; Rincon:2018sgd ; Contreras:2018dhs ;
Rincon:2018lyd ; Rincon:2018dsq ; Rincon:2019cix ; Contreras:2018gpl . Also,
the Sagnac effect Rincon:2019zxk , the evolution of trajectories of photons
Fathi:2019jid , some cosmological solutions Canales:2018tbn , and transverse
wormhole solutions Contreras:2018swc  have been investigated. In the context
of theories beyond classical GR, apart from the aforementioned approach based
on scale-dependent gravity, there is yet another method, which is usually
called ”improved” asymptotically safe (AS) gravity Bonanno:2000ep ;
Bonanno:2001xi ; Reuter:2003ca . For RG-improved cosmologies and inflationary
models from asymptotic safety see e.g. Platania:2020lqb ; Bonanno:2002zb ;
Bonanno:2001hi ; Liu:2018hno ; Hindmarsh:2012rc , and for recent progress
Platania:2019kyx ; Moti:2018uvl ; Koch:2013owa ; Bonanno:2016dyv ; chinosII ;
Li:2013kkb . In that scenario, the main idea is to integrate the beta function
for the gravitational coupling in order to compute Newton’s constant as a
function of some energy scale $k$, $G(k)$. After that, Newton’s constant is
inserted into the classical black hole solution and the improved lapse
function is obtained. It is essential to notice that the gravitational
coupling depends on some arbitrary renormalization scale $k$. Finally, a link
between the energy scale $k$ and the radial coordinate $r$ is established.
Only after this final step, the complete form of an improved black hole
solution is obtained. Those extended solutions, inspired by the asymptotic
safety program, are expected to modify the classical black hole solutions by
incorporating quantum features. Similar black hole solutions, free of the
central singularity, can be found, e.g, in Refs. bardeen ; hayward ; frolov ,
although they are not directly connected with the ASG program.

Another important stream of ideas that try to describe the interplay between
quantum effects and gravity is the research line known under the name of
Generalized Uncertainty Principle (GUP). Although some seminal work on
possible generalizations of the fundamental Heisenberg Uncertainty Principle
(HUP) Heisenberg  can be traced back to more than seventy years ago GUPearly ,
these concepts have been intensely revived and precised in the last thirty
years VenezGrossMende ; MM ; kempf ; FS ; Adler2 ; CLS ; SC . In a nutshell,
several re-analysis of the measurement process, in particular of the famous
Heisenberg microscope argument, have shown, with plenty of details, that, when
the action of gravity is taken into account, the fundamental uncertainty
relation should be modified as

$\displaystyle\mbox{}\Delta x\,\Delta p$ $\displaystyle\geq$
$\displaystyle\frac{\hbar}{2}\left(1+\beta\,\frac{4\,\ell_{P}^{2}}{\hbar^{2}}\,\Delta
p\,^{2}\right)=\frac{\hbar}{2}\left[1+\beta\left(\frac{\Delta
p}{M_{P}}\right)^{2}\right]$ (1)

Here $\ell_{P}$ is the Planck length, $M_{P}$ the Planck mass, and we work in
units where $2G_{0}M_{P}=\ell_{P}$, $\hbar=2M_{P}\ell_{P}$, $c=k_{B}=1$. As
said, studies in this framework focus on understanding the effects of gravity
on the formulation of uncertainty relations. Therefore, it turns out natural
that the most relevant modifications to the HUP have been proposed in contexts
such as string theory, non commutative geometry, and studies of black hole
physics VenezGrossMende ; MM ; FS ; Adler2 ; kempf ; CLS ; SC . The
dimensionless parameter $\beta$ in (1) is not fixed a priori by the theory,
however in some models of string theory it is generally assumed that
$\beta\sim{\cal O}(1)$ VenezGrossMende .

The aim of this paper is to present and discuss a link between the free
parameters of ASG, i.e. the renormalization scale, and the deforming parameter
$\beta$ of the generalized uncertainty principle (GUP) . Here we shall use the
GUP to compute the Hawking temperature of a given black hole, obtaining it as
a function of the deformation parameter $\beta$. The same deformed temperature
can however be computed as well via the ASG deformation of Schwarzschild
metric. This will yield a relation between $\beta$ and the ASG free
parameters.

The paper is organized as follows. In the next Section we shortly recall the
main results of the renormalization group approach leading to the ASG-improved
classical Newton potential, as well to the ASG-modification of the
Schwarzschild metric. In Section III we compute the GUP-deformed Hawking
temperature. In Section IV we compute the ASG-deformed Hawking temperature. In
Section V we compare such two deformations and relate the respective
deformation parameters. In Section VI we give a precise evaluation of the ASG
parameters. Section VII is devoted to discuss a particular example. Conclusion
are shortly presented in the last Section.

##  II Running Newtonian coupling and Black hole metrics

As we briefly summarized in the Introduction, the main steps towards the
construction of a renormalization group improved Schwarzschild metric are
essentially three (we make particular reference to Ref. Bonanno:2000ep ):
first, we integrate the beta function for the gravitational coupling to
compute Newton’s constant as a function of some energy scale $k$, namely
$G(k)$. It is essential to notice that the gravitational coupling depends on
some arbitrary renormalization scale $k$. After that, a link between the
energy scale $k$ and the radial coordinate $r$ must be established (the so
called ”identification of the infrared cutoff”, namely $k=k(r)$). Finally, the
$G(r)$ Newton’s constant is inserted into the classical black hole solution
and we obtain the improved lapse function of the metric. It is only after this
final step that the complete solution of a ”renormalization improved” black
hole becomes concretely usable for explicit calculations. The above steps are
detailed in Appendix A.

So, the basic idea of the AS gravity approach in order to obtain the
renormalization improved, classical Newtonian or general relativistic,
solutions is to replace everywhere the Newton constant $G_{0}$ with the
running constant $G(r)$, whose explicit form is given by Bonanno:2000ep

$\displaystyle
G(r)=\frac{G_{0}r^{3}}{r^{3}+\tilde{\omega}G_{0}\hbar\left(r+\gamma
G_{0}M\right)}\,,$ (2)

where, in accordance with our conventions, $c=k_{B}=1$ and we retained
$\hbar$. Here $\tilde{\omega}$ and $\gamma$ are dimensionless numerical
parameters, whose concrete value will be discussed later.

The line element for the spherically symmetric, Lorentzian metric preserves
the usual form, that is

$\displaystyle\mathrm{d}s^{2}=f(r)\mathrm{d}t^{2}-f(r)^{-1}\mathrm{d}r^{2}-r^{2}\>\mathrm{d}\Omega^{2},$
(3)

where $r$ is the radial coordinate, and
$\mathrm{d}\Omega^{2}=\mathrm{d\theta^{2}+sin^{2}\theta\>d\phi^{2}}$ is the
line element of the unit two-sphere. But now, according to the above
prescriptions, the lapse function $f(r)$ of our ASG improved Schwarzschild
geometry reads

$\displaystyle
f(r)=1-\frac{2MG(r)}{r}=1-\frac{2G_{0}Mr^{2}}{r^{3}+\tilde{\omega}G_{0}\hbar(r+\gamma
G_{0}M)}\,,$ (4)

with $G(r)$ given by (2) and $M$ the mass of the black hole. Of course, we
suppose $\tilde{\omega}\neq 0$, otherwise we would go back to the standard
Schwarzschild metric. Two very important limiting cases should be considered.
The first corresponds to the low energy scales ($r\rightarrow\infty$, or $k\to
0$), which implies

$\displaystyle f(r\rightarrow\infty)\simeq 1-\frac{2G_{0}M}{r},$ (5)

so we recover the standard Schwarzschild metric at large distances, and this
behavior is independent from the values of $\tilde{\omega}$ and $\gamma$.
The second corresponds to the high energy scales ($r\rightarrow 0$, or
$k\to\infty$). Here we have to distinguish two subcases:
if $\gamma\neq 0$, then

$\displaystyle f(r\rightarrow 0)\simeq 1-\frac{2r^{2}}{\tilde{\omega}\gamma
G_{0}\hbar}\,,$ (6)

and thus the lapse function corresponds to a deSitter
($\tilde{\omega}\gamma>0$) or an Anti-deSitter ($\tilde{\omega}\gamma<0$) core
of our metric, depending on the sign of $\tilde{\omega}\gamma$;
if $\gamma=0$, then

$\displaystyle f(r\rightarrow 0)\simeq 1-\frac{2Mr}{\tilde{\omega}\hbar}\,,$
(7)

so in this case we have a so-called conic singularity at the origin. Clearly,
the $\hbar$ at denominator is the hallmark of the quantum character of the
correction that the ASG approach gives to the core of the standard
Schwarzschild metric. Note that in both cases the central singularity is wiped
out.

##  III GUP-deformed Hawking temperature

The argument based on Heisenberg microscope Heisenberg  suggests that the size
$\delta x$ of the smallest detail of an object (theoretically detectable with
a beam of photons of energy $E$) is roughly given by

$\displaystyle\delta x\simeq\frac{\hbar}{2\,E}$ (8)

since ever larger energies are required to explore ever smaller details. On
the other hand, the uncertainty relation (1) implies that the GUP version of
Eq. (8) is

$\displaystyle\delta
x\simeq\frac{\hbar}{2\,E}+2\,\beta\,\ell_{P}^{2}\,\frac{E}{\hbar}$ (9)

which relates the (average) wavelength of a photon to its energy $E$. The
thermal GUP corrections to the Hawking spectrum are traced in many references
FS9506 ; ACSantiago ; CDM03 ; Susskind ; nouicer ; Glimpses . Equation (9)
allow to derive a relation between the mass and the temperature of a
Schwarzschild black hole. To this aim, consider an ensemble of unpolarized
photons of Hawking radiation just outside the event horizon of a Schwarzschild
black hole. The position uncertainty of such photons can be estimated to be
$\delta x\simeq 2\mu R_{S}$, where $R_{S}=2G_{0}M$ is the Schwarzschild radius
of the black hole. We fixed $\mu=\pi$ to recover the standard semiclassical
Hawking temperature when $\beta\to 0$ (see below). The equipartition principle
imposes that the average energy $E$ of unpolarized photons of the Hawking
radiation is related to the temperature $T$ as $E\ \simeq\ T$, so that Eq. (9)
yields

$\displaystyle M\ =\ \frac{\hbar}{8\pi G_{0}T}\ +\ \beta\,\frac{T}{2\pi}\,.$
(10)

Inverting this relation, and expanding in $\beta$, we obtain

$\displaystyle T(M)=\frac{\hbar}{8\pi
G_{0}M}\left(1+\frac{\beta\,M_{P}^{2}}{4\pi^{2}\,M^{2}}+\dots\right)~{}.$ (11)

In deriving (11) we have assumed the thermal character of the correction
induced by the GUP. There are, however, different approaches in which the
corrections do not respect the exact thermality of the spectrum, and thus need
not be reducible to a simple shift of the temperature (an example is the
corpuscular model of a black hole of Refs. dvali ). Further aspects of the GUP
are discussed (among the many papers) in Refs. GUP .

##  IV Hawking temperature from the ASG-deformed Schwarzschild metric

Of course, the Bekenstein-Hawking temperature for the general class of black
holes with metrics of type (3) can be computed with a well known general
procedure Hawking  for any arbitrary function $f(r)$. By assuming that $f$ has
a simple zero at some $r_{h}$, namely $f(r_{h})=0$ and $f^{\prime}(r_{h})\neq
0$, and that it increases monotonically from zero to $f(+\infty)=1$ for
$r>r_{h}$, then the Bekenstein-Hawking temperature on the horizon $r=r_{h}$ is

$\displaystyle T_{BH}=\frac{\hbar}{4\pi}\,f^{\prime}(r_{h})\,.$ (12)

Here the above calculation can be in principle performed exactly, using for
$f(r)$ the expression given in Eq.(4), although a cubic equation would be
involved (see Ref.Bonanno:2000ep  for this procedure). However, to our scope,
since we have in mind to match the ASG-deformed temperature with the GUP-
deformed temperature in order to extract the relation between $\beta$ and
$(\tilde{\omega},\gamma)$, it results much more doable and clear to write
$f(r)$ of Eq.(4) in the form of a small perturbation over the Schwarzschild
metric (we follow SLV ; SC2 ; LambSME ; SLVConf ; tomoyo )

$\displaystyle
f(r)=1-\frac{2G_{0}M}{r}+\frac{2\,G_{0}^{2}\,\tilde{\omega}\,M\hbar\,(r+\gamma
G_{0}M)}{r^{4}}+{\cal O}(\frac{1}{r^{5}})=1-\frac{2G_{0}M}{r}+\varepsilon(r)$
(13)

with

$\displaystyle\varepsilon(r)\simeq\frac{2\,G_{0}^{2}\,\tilde{\omega}\,M\hbar\,(r+\gamma
G_{0}M)}{r^{4}}\,,$ (14)

and this can be done since $|\varepsilon(r)|\ll 2G_{0}M/r$ for any
$r>2G_{0}M$. For any metric of the form (13) the horizon equation $f(r)=0$
reads

$\displaystyle r-2G_{0}M+r\varepsilon(r)=0\,,$ (15)

which can be solved to the first order in $\varepsilon(r)$ by

$\displaystyle
r_{h}=a-\frac{a\varepsilon(a)}{1+\varepsilon(a)+a\varepsilon^{\prime}(a)}=a\left[1-\varepsilon(a)+{\cal
O}(\varepsilon^{2})\right]\,,$ (16)

where $a=2G_{0}M$. Using now Eqs.(12), (13), and (16), we can expand in
$\varepsilon$ and arrive to the deformed Hawking temperature

$\displaystyle T_{BH}=\frac{\hbar}{4\pi}\,f^{\prime}(r_{h})=\frac{\hbar}{4\pi
a}\left\\{1+[2\varepsilon(a)+a\varepsilon^{\prime}(a)]+\varepsilon(a)[\varepsilon(a)-2a\varepsilon^{\prime}(a)-a^{2}\varepsilon^{\prime\prime}(a)]+{\cal
O}(\varepsilon^{3})\right\\}$ (17)

where for sake of completeness we report also the second order in
$\varepsilon$. The symbol ′ stands for the derivative with respect to $r$
(${}^{\prime}\equiv\partial_{r}$).

##  V Relation between $\beta$ and $\tilde{\omega},\gamma$

By comparing the first orders of the expansions of the GUP-deformed Hawking
temperature given in Eq.(11), and of the ASG-Schwarschild temperature (17),
one obtains

$\displaystyle\beta=\frac{4\pi^{2}M^{2}}{M_{P}^{2}}\,\left[2\varepsilon(a)+a\varepsilon^{\prime}(a)\right]\,,$
(18)

where $a=2G_{0}M$. Finally, using the expression (14) for $\varepsilon(r)$ we
arrive at

$\displaystyle\beta\ =\ -\,4\,\pi^{2}\,\tilde{\omega}\,(1+\gamma)\,.$ (19)

This is the general relation between the ASG parameters $\tilde{\omega}$,
$\gamma$ and the deformation parameter $\beta$ of the GUP.

##  VI Estimate of parameters $\tilde{\omega}$, $\gamma$, $\beta$

As we said in Sec.II, the ASG-improved Newtonian potential can be obtained
from the standard Newton formula

$\displaystyle V(r)=-\frac{G_{0}Mm}{r}$ (20)

by simply replacing the experimentally observed Newton constant $G_{0}$ with
the running coupling $G(r)$ given in Eq.(2). Thus we get

$\displaystyle
V^{ASG}(r)=-\frac{G(r)Mm}{r}=-\frac{G_{0}\,M\,m\,r^{2}}{r^{3}+\tilde{\omega}\,G_{0}\,\hbar\,(r+\gamma
G_{0}M)}\,,$ (21)

which can be expanded for large $r$ as

$\displaystyle
V^{ASG}(r)=-\frac{G_{0}Mm}{r}\left[1-\frac{\tilde{\omega}G_{0}\hbar}{r^{2}}-\frac{\gamma\tilde{\omega}G_{0}^{2}\hbar
M}{r^{3}}+{\cal O}\left(\frac{G_{0}^{2}\hbar^{2}}{r^{4}}\right)\right]\,.$
(22)

We should notice that the corrections to the standard Newtonian potential
predicted by the ASG approach are all of quantum nature. This is clearly
suggested by the presence of $\hbar$ in each term of correction. In fact,
there are no correction terms of classical origin, coming from some kind of
post-Newtonian approximation. On the other hand, corrections of quantum origin
to the classical Newtonian potential have been elaborated by several
researchers Duff ; donoghue  in the last three decades or so. In particular,
it was pointed out by Donoghue donoghue ; donoASP  that the standard
perturbative quantization of Einstein gravity leads to a well defined, finite
prediction for the leading large distance quantum correction to Newtonian
potential. The numerical coefficients of the quantum expansion have undergone
a certain evolution over the years kiril , but the result today accepted by
the community dono2  reads

$\displaystyle V^{Quantum}(r)=-\frac{G_{0}Mm}{r}\left[1\ +\
\frac{41}{10\pi}\frac{G_{0}\hbar}{r^{2}}\ +\ \dots\right]\,.$ (23)

This is an expansion at first order in $\hbar$ (up to classical terms due to
non-linear nature of General Relativity, which can be reabsorbed by a change
of coordinates), where the first correction term represents a genuine quantum
correction proportional to $\hbar$.

The comparison of the two expansions (22) and (23) fixes the parameter
$\tilde{\omega}$, which results to be

$\displaystyle\tilde{\omega}=-\frac{41}{10\pi}\,.$ (24)

The ASG parameter $\gamma$ is not fixed by these considerations. In this
regard, we can follow two different paths:

i)

We can refer to the considerations developed in Ref.Bonanno:2000ep . Those
classical general relativistic arguments fix $\gamma=9/2$. Using this value of
$\gamma$ and the Eqs.(19),(24), we can compute the $\beta$ parameter of the
GUP, which results to be

$\displaystyle\beta=\frac{451\,\pi}{5}\,.$ (25)

As we see $\beta$ results to be of order $10^{2}$ as suggested by some models
of string theory VenezGrossMende .

ii)

We can first compute $\beta$, by following the procedure described in Ref.SLV
, namely comparing the GUP Hawking temperature (11) with the Hawking
temperature of a Schwarzschild metric corrected through the Donoghue potential
(23). This yields $\beta=82\pi/5$. Then, using (19),(24), we get

$\displaystyle\gamma=0\,.$ (26)

Given the indeterminacy of the arguments used in Bonanno:2000ep  to fix
$\gamma$, we would incline for the second possibility. Finally, the study of
the metric (4), and of the related (somehow surprising) black hole features
when $\tilde{\omega}<0$, will be carried out in Ref. SLnew .

##  VII The $\xi$-model

In this Section we investigate further an example of modified, or ”improved”,
Schwarzschild solution, described by the lapse function

$\displaystyle f(r)=1-\frac{2G_{0}Mr}{r^{2}+\xi}$ (27)

Mathematically, the above lapse function is just a particular case of the
previous (4) with $\gamma=0$ and the identification
$\xi=\tilde{\omega}G_{0}\hbar$. Metrics as the above have been studied for
example in Refs. chinosII ; Li:2013kkb  as an approximate expression of the
lapse

$\displaystyle f(r)=1-\Lambda\eta-\frac{\Lambda
r^{2}}{3}-\frac{2G_{0}Mr}{r^{2}+\xi}\,,$ (28)

where the parameters $\eta$ and $\xi$ have the dimensions of a length squared
and they are supposed, at least initially, to be positive. The authors
obtained the lapse (28) as the static, spherically symmetric solution (in the
infrared limit) of an ASG quantum-corrected black hole in an Anti-de Sitter
(AdS) spacetime, with a deficit angle $\Lambda\eta$. However, the effect of
the latter is negligibly small, as referred to cosmological observations and,
for an astrophysical black hole, the corrections yielded by the cosmological
constant are extremely small. Therefore, neglecting $\Lambda$, the authors
arrive to the expression (27). At a far distance the lapse (27) correctly
reproduces the Schwarzschild solution (recovered for $\xi=0$), and deflection
from it is of the order of $\xi$. At the origin the metric is finite, however
it is not regular, since it contains a conic singularity. According to
Ref.frolov , the metric has a curvature invariant $R$ of the form

$\displaystyle R=\frac{2G_{0}M}{\xi^{3/2}}g(r/\sqrt{\xi})$ (29)

(where $g$ is a finite function), which means that for any fixed $r$ the
corresponding $R$ can be made arbitrarily large by simply increasing the mass
parameter $M$. Therefore the metric (27) for a black hole does not satisfy the
so-called limiting curvature condition. Of course, the same can be said for
the lapse (4) in the case $\gamma=0$.

From (27) we can expand for large $r$ (the regime $r^{2}\gg\xi$), and get

$\displaystyle f(r)=1-\frac{2G_{0}M}{r}+\frac{2G_{0}M\xi}{r^{3}}+{\cal
O}\left(\frac{1}{r^{5}}\right)\,,$ (30)

so we can identify the deformation to the Schwarzschild metric, i.e.

$\displaystyle\varepsilon(r)\simeq\frac{2G_{0}M\xi}{r^{3}}\,.$ (31)

Thus Eq. (18) gives

$\displaystyle\beta=-\frac{\pi^{2}\xi}{G_{0}^{2}M_{P}^{2}}=-\frac{4\pi^{2}\xi}{\ell_{P}^{2}}\,.$
(32)

As arises from Eq. (32), the GUP parameter $\beta$ is independent on the
gravitational mass source, and it is only related to the fundamental Planck
mass-scale. In case we assume $\xi>0$ a priori, then $\beta$ would result
negative. This would not sound particularly weird, if we remember that a
negative $\beta$ appears in contexts as uncertainty principle on a lattice JKS
, or white dwarf stability ong  or decoherence limit of quantum systems
(Tsallis thermostatistics) jizba2022 .

However, if we coherently follow the logic of the previous section, then from
(30) we can extract the expansion of the effective Newtonian potential
$V_{N}=[f(r)-1]/2$, and by comparing it with the Donoghue quantum-corrected
Newtonian potential (23), we get

$\displaystyle\xi=-\frac{41}{10\pi}\,G_{0}\hbar=-\frac{82}{5\pi}\,G_{0}^{2}M_{P}^{2}$
(33)

which inserted in (32) yields

$\displaystyle\beta=\frac{82\pi}{5}\,,$ (34)

consistently with the case $ii)$ of the previous section ($\gamma=0$).

Two comments are now in order.

  * •

Requiring the matching with the Donoghue quantum-corrected Newtonian potential
at large $r$, the parameter $\xi$ results actually to be negative, as it
resulted also the parameter $\tilde{\omega}$ (see the previous section),
consistently with the identification $\xi=\tilde{\omega}G_{0}\hbar$. This fact
has heavy consequences on the structure of the metric (27) for singularities,
horizons, etc. This will form the subject of a forthcoming paper.

  * •

In the same vein as in Ref.LambSME , we can use the relations (19) (with
$\gamma=0$) and (32), connected by $\xi=\tilde{\omega}G_{0}\hbar$, in order to
transfer experimental upper bounds from the GUP parameter $\beta$ to the ASG
parameters $\tilde{\omega}$, $\xi$.

From (19) it is clear that between $\beta$ and $\tilde{\omega}$ there is a
mere factor $\sim 40$, therefore upper bounds on $\beta$ are essentially
reflected directly on $\tilde{\omega}$. Instead, using (32) in the form
$|\xi|=(\ell_{P}/2\pi)^{2}|\beta|$, we obtain for the upper bounds on $\xi$
the results reported in Table 1. Of course, if the GUP parameter is of the
order of unity, $\beta\sim{\cal O}(1)$, then $\xi$ is of the order of the
Planck Length squared, that is

$\xi\sim\ell_{P}^{2}\,.$

Table 1: Upper bounds on $\xi$ derived from gravitational and non-gravitational experiments. $\beta<$ | Physical framework | $\sqrt{\xi}\,\,cm<$
---|---|---
$10^{6}$ | Sapphire mechanical resonator Bushev  | $10^{-31}$
$10^{12}$ | Micro and nano mechanical | $10^{-28}$
| oscillators (masses $\sim M_{P}$) Bonaldi  |
$10^{20}$ | Lamb shift vagenas  | $10^{-24}$
$10^{21}$ | Scanning tunneling microscope vagenas  | $10^{-23}$
| Violation of equivalence principle ghosh  |
$10^{33}$ | Gravitational bar detectors martin  | $10^{-18}$
$10^{34}$ | Electroweak measurement SC2  | $10^{-17}$
| Charmonium levels vagenas  |
| Energy difference in Hydrogen levels $1S-2S$ Tkachuk  |
$10^{39}$ |  87Rb cold-atom-recoil experiment gao  | $10^{-14}$
$10^{46}$ | Landau levels vagenas  | $10^{-11}$

As a general comment, we can say that it is important, from an experimental
point of view, to have revealed a direct connection between the parameters
$\beta$, $\tilde{\omega}$, $\xi$, namely Eqs.(19),(32). This allows us to
transfer experimental upper bounds from one parameter to the other, thus
enriching, at least in principle, the phenomenology available to researchers
in the field.

##  VIII Conclusions

In this paper we have derived an exact relation between the GUP parameter
$\beta$ and the parameters $\tilde{\omega},\gamma$ characterizing the
Asymptotic Safe gravity. The shift of the Hawking black hole temperature, for
which the GUP is relevant, is derived by means of pure quantum mechanical
principles, and no specific representation of the canonical commutation
relation is postulated. On the other hand, the same temperature is derived
geometrically for an ASG-improved version of the Schwarzschild metric,
allowing to link the deformed uncertainty relation parameter $\beta$ with the
renormalization scale, here measured by the parameters $\tilde{\omega},\gamma$
(or $\xi$, in a specific example).

As a byproduct, from the well known and up-to-date upper bounds on GUP
parameter $\beta$ present in literature, we obtained an upper bound on the
renormalization scale parameters $\tilde{\omega},\xi$ (derived in the
framework of ASG running coupling Newtonian constant). Indeed, a common point
in the wide discussions on various models yielding the GUPs is related to test
the size of these modifications of the uncertainty relations. These aspects
appear particularly interesting in the perspective of a laboratory-scale
imitation of the black hole horizon, with the subsequent possible emission of
an analogue Hawking radiation ron .

Aside from the above results, through a comparison with the quantum corrected
Newtonian potential, we have also determined the exact numerical value of the
ASG parameters $\tilde{\omega},\xi$, which both result to be negative. The
deep consequences that this fact has on the related black hole metrics will be
explored in Ref. SLnew .

##  Appendix A Renormalization group-improved Schwarzschild solutions

In this Appendix we shall review the improved Schwarzschild solution obtained
in Bonanno:2000ep . The average Einstein-Hilbert action, able to avoid ghosts,
is given by ($\hbar=1$)

$\displaystyle\Gamma_{k}[\mathfrak{g}]$ $\displaystyle=\frac{1}{16\pi
G(k)}\int\mathrm{d}^{4}x\sqrt{\mathfrak{g}}\Bigl{(}-R(\mathfrak{g})+2\bar{\lambda}(k)\Bigl{)}.$
(35)

Here $\mathfrak{g}$ is the metric, while $G(k)$ and $\bar{\lambda}(k)$ are the
running Newton’s constant and the cosmological constant, respectively. The
evolution of the scale-dependent couplings is governed by the Wetterich
equation

$\displaystyle\partial_{t}\Gamma_{k}$
$\displaystyle=\frac{1}{2}\text{Tr}\left(\frac{\partial_{t}\mathcal{R}_{k}}{\Gamma^{(2)}_{k}[\phi]+\mathcal{R}_{k}}\right),$
(36)

where $t=\ln(k)$, $\Gamma_{k}^{(2)}$ is the Hessian of $\Gamma_{k}$ with
respect to $g_{\mu\nu}$, and $\mathcal{R}_{k}$ is a filtering function
Bonanno:2000ep , $\mathcal{R}_{k}(p^{2})\propto k^{2}R^{(0)}(z)$, with
$z\equiv p^{2}/k^{2}$ and $R^{(0)}(z)\equiv\frac{z}{e^{z}-1}$. Inserting
$\Gamma_{k}$ into (36) and projecting the flow onto the subspace spanned by
the Einstein-Hilbert truncation, one infers a system of coupled differential
equations for the dimensionless Newton’s constant $g(k)\equiv k^{2}G(k)$, and
the dimensionless cosmological constant
$\lambda(k)\equiv\bar{\lambda}(k)/k^{2}$. Since the cosmological constant
plays no role within the scope of the present investigation we may approximate
$\lambda\approx 0$. Thus the evolution of $g(t)$ is governed by the equation

$\displaystyle\frac{\mathrm{d}g(t)}{\mathrm{d}t}\equiv\beta(g(t))=\left[2+\frac{B_{1}g(t)}{1-B_{2}g(t)}\right]\>g(t),$
(37)

where the constants $B_{1}$ and $B_{2}$ are given by Bonanno:2000ep

$\displaystyle B_{1}\equiv B_{1}(0)$
$\displaystyle=-\frac{1}{3\pi}\bigg{(}24\Phi^{2}_{2}(0)-\Phi_{1}^{1}(0)\bigg{)},$
(38) $\displaystyle B_{2}\equiv B_{2}(0)$
$\displaystyle=\frac{1}{6\pi}\bigg{(}18\tilde{\Phi}^{2}_{2}(0)-5\tilde{\Phi}_{1}^{1}(0)\bigg{)}.$
(39)

$\Phi^{p}_{n}(w)$ and $\tilde{\Phi}^{p}_{n}(w)$ are two auxiliary functions
defined by

$\displaystyle\Phi^{p}_{n}(w)$
$\displaystyle\equiv\frac{1}{\Gamma(n)}\int_{0}^{\infty}\mathrm{d}z\
z^{n-1}\frac{R^{(0)}(z)-z{R^{(0)}}^{\prime}(z)}{(z+R^{(0)}(z)+w)^{p}},$ (40)
$\displaystyle\tilde{\Phi}^{p}_{n}(w)$
$\displaystyle\equiv\frac{1}{\Gamma(n)}\int_{0}^{\infty}\mathrm{d}z\
z^{n-1}\frac{R^{(0)}(z)}{(z+R^{(0)}(z)+w)^{p}}.$ (41)

Integrating (37) to get an explicit form for $g(k)$, and using the above
relation $g(k)=k^{2}G(k)/\hbar$ (here we restored $\hbar$), one obtains the
dimensionfull Newton’s coupling

$\displaystyle G(k)=\frac{G_{0}}{1+\tilde{\omega}G_{0}k^{2}/\hbar}.$ (42)

As this equation shows, deviations from the classical solution are important
at high energy/momentum scales. The classical space-time is recovered in the
opposite regime, when $k\to 0$. To connect $k$ with the physical radial
coordinate $r$, in Bonanno:2000ep  it has been used the identification

$\displaystyle k(r)\equiv\hbar\left(\frac{r+\gamma
G_{0}M}{r^{3}}\right)^{1/2}.$ (43)

The renormalization scale $k(r)$ is a modified proper distance, more precisely
$k(r)\sim\hbar/d(r)$: this function interpolates smoothly the behaviour of the
proper distance close to $r=0$ and at infinity. The final result of the
modification of the Newtonian gravitational constant is expressed by Eq. (2).

## References

  * (1) T. Jacobson,  Phys. Rev. Lett., 75 1260 (1995).
  * (2) A. Connes,  Commun. Math. Phys., 182 155 (1996).
  * (3) M. Reuter,  Phys. Rev., D 57 971 (1998).
  * (4) C. Rovelli,  Living Rev. Rel., 1 1 (1998).
  * (5) A. Ashtekar,  New J. Phys., 7 198 (2005).
  * (6) P. Horava,  Phys. Rev., D 79 084008 (2009).
  * (7) E.P. Verlinde,  JHEP, 04 029 (2011).
  * (8) B. Koch, I.A. Reyes, Ã. Rincon,  Class. Quant. Grav., 33 (22) 225010 (2016).
  * (9) Ã.Rincon, E.Contreras, P.Bargueno, B.Koch, G.Panotopoulos, A.Hernandez-Arboleda, Eur. Phys. J., C 77 (7) 494 (2017).
  * (10) E. Contreras, Ã. Rincon, B. Koch, P. Bargueno,  Int. J. Mod. Phys., D 27 (03) 1850032 (2017).
  * (11) Ã. Rincon, G. Panotopoulos,  Phys. Rev., D 97 (2) 024027 (2018).
  * (12) E. Contreras, Ã. Rincon, B. Koch, P. Bargueno,  Eur. Phys. J., C 78 (3) 246 (2018).
  * (13) Ã. Rincon, B. Koch,  Eur. Phys. J., C 78 (12) 1022 (2018).
  * (14) Ã. Rincon, E. Contreras, P. Bargueno, B. Koch, G. Panotopoulos,  Eur. Phys. J., C 78 (8) 641 (2018).
  * (15) Ã. Rincon, E. Contreras, P. Bargueno, B. Koch,  Eur. Phys. J. Plus, 134 (11) 557 (2019).
  * (16) E. Contreras, P. Bargueno,  Mod. Phys. Lett., A 33 (32) 1850184 (2018).
  * (17) Ã. Rincon, J.R. Villanueva,  Class. Quant. Grav. 37 (2020), 175003.
  * (18) M. Fathi, Ã. Rincon, J.R. Villanueva,  Class. Quant. Grav. 37 (2020), 075004.
  * (19) F. Canales, B. Koch, C. Laporte, Ã. Rincon.  JCAP 01 (2020), 021.
  * (20) E. Contreras, P. Bargueno,  Int. J. Mod. Phys., D 27 (09) 1850101 (2018).
  * (21) A. Bonanno, M. Reuter,  Phys. Rev., D 62 043008 (2000).
  * (22) A. Bonanno, M. Reuter,  Phys. Rev., D 65 043508 (2002).
  * (23) M. Reuter, H. Weyer,  Phys. Rev., D 69 104022 (2004).
  * (24) A.Platania,  Front. in Phys., 8 188 (2020).
  * (25) A.Bonanno, M. Reuter,  Int. J. Mod. Phys. D, 13 107 (2004).
  * (26) A. Bonanno, M. Reuter,  Phys. Lett. B, 527 9 (2002).
  * (27) L.H. Liu, T. Prokopec, A. Starobinsky,  Phys. Rev. D, 98 (4) 043505 (2018).
  * (28) M. Hindmarsh, I.D. Saltas,  Phys. Rev. D, 86 064029 (2012).
  * (29) A. Platania,  Eur. Phys. J. C, 79 (6) 470 (2019).
  * (30) R. Moti, A. Shojai,  Int. J. Mod. Phys. A, 35 2050016 (2020).
  * (31) B. Koch, F. Saueressig,  Class. Quant. Grav., 31 015006 (2014).
  * (32) A. Bonanno, B. Koch, A. Platania,  Class. Quant. Grav., 34 (9) 095012 (2017).
  * (33) Dao-Jun Liu, Bin Yang, Yong-Jia Zhai, Xin-Zhou Li,  Class. Quant. Grav., 29 145009 (2012).
  * (34) Jin Li, Yuanhong Zhong,  Int. J. Theor. Phys., 52 1583 (2013).
  * (35) J.M. Bardeen, Proceedings of of International Conference GR5 (Tbilisi, USSR, 1968) p. 174.
  * (36) S.A. Hayward, Phys. Rev. Lett. 96 (2006), 031103.
  * (37) V.P. Frolov, Phys. Rev. D 94 (2016) no.10, 104056.
  * (38) W. Heisenberg, Zeitschrift für Physik, 43, 172 (1927).
  * (39) H.S. Snyder, Phys.Rev. 71, 38 (1947);
C.N. Yang, Phys. Rev. 72, 874 (1947);
C.A. Mead, Phys. Rev. 135, B 849 (1964);
F. Karolyhazy, Nuovo Cim. A 42, 390 (1966).

  * (40) D. Amati, M. Ciafaloni, G. Veneziano, Phys. Lett. B 197, 81 (1987);
D.J. Gross, P.F. Mende, Phys. Lett. B 197, 129 (1987);
D. Amati, M. Ciafaloni, G. Veneziano, Phys. Lett. B 216, 41 (1989);
K .Konishi, G. Paffuti, P. Provero, Phys. Lett. B 234, 276 (1990).

  * (41) M. Maggiore, Phys. Lett. B 304, 65 (1993).
  * (42) A. Kempf, G. Mangano, R.B. Mann, Phys. Rev. D 52, 1108 (1995).
  * (43) F. Scardigli, Phys. Lett. B 452, 39 (1999).
  * (44) R.J. Adler, D.I. Santiago, Mod. Phys. Lett. A14, 1371 (1999).
  * (45) S. Capozziello, G. Lambiase, G. Scarpetta, Int. J. Theor. Phys. 39, 15 (2000).
  * (46) F. Scardigli, R. Casadio, Class. Quantum Grav. 20, 3915 (2003).
  * (47) F. Scardigli, Nuovo Cim. B 110, 1029 (1995).
  * (48) R.J. Adler, P. Chen, D.I. Santiago, Gen. Rel. Grav. 33, 2101 (2001).
  * (49) M. Cavaglia, S. Das and R. Maartens, Class. Quant. Grav. 20, L205 (2003).
  * (50) L. Susskind, J. Lindesay, An Introduction to Black Holes, Information, and the String Theory Revolution (World Scientific, Singapore, 2005). See chapter 10.
  * (51) K. Nouicer, Class. Quant. Grav. 24, 5917 (2007).
  * (52) F. Scardigli, Symmetry 12 (2020) no.9, 1519.
  * (53) G. Dvali, C. Gomez, Fortsch. Phys. 61, 742 (2013);
R. Casadio, A. Giugno, A. Orlandi, Phys. Rev. D 91, 124069 (2015);
R. Casadio, A. Giugno, A. Giusti, Phys. Lett. B 763, 337 (2016);
L. Buoninfante, G. G. Luciano and L. Petruzziello, Eur. Phys. J. C 79 (2019),
663;
A. Giusti, Int. J. Geom. Meth. Mod. Phys. 16 (2019), 1930001.

  * (54) G. Luciano, L. Petruzziello, Eur. Phys. J. C 79 (2019), 283;
L. Petruzziello, F. Wagner, Phys. Rev. D 103 (2021), 104061;
M. J. Lake, M. Miller, R. F. Ganardi, Z. Liu, S. D. Liang, T. Paterek, Class.
Quant. Grav. 36 (2019), 155012;
M. Bishop, J. Lee, D. Singleton, Phys. Lett. B 802 (2020), 135209;
A. Alonso-Serrano, M.P. Dabrowski, H. Gohar, Phys. Rev. D 97, 044029 (2018);
F. Scardigli, M. Blasone, G. Luciano, R. Casadio, Eur. Phys. J. C 78 (2018),
728;
R. Casadio, F. Scardigli, Phys. Lett. B 807 (2020), 135558;
S. Das, M. Fridman, G. Lambiase, E. Vagenas, Phys. Lett. B 824 (2022), 136841;
R. Casadio and F. Scardigli, Eur. Phys. J. C 74 (2014) no.1, 2685;
S.Hassanabadi, J.Kriz, W.S.Chung, B.C.Lütfüoğlu, E.Maghsoodi, H.Hassanabadi,
Eur.Phys.J.Plus 136 (2021) no.9, 918;
I. Pikovski, C. Brukner, et al., Nat. Phys. 8, 393 (2012).

  * (55) S. W. Hawking, Commun. Math. Phys. 43 (1975), 199.
  * (56) F. Scardigli, R. Casadio, Eur. Phys. J. C 75 425 (2015).
  * (57) F. Scardigli, G. Lambiase, E.C. Vagenas, Phys. Lett. B 767, 242 (2017).
  * (58) G. Lambiase, F. Scardigli, Phys.Rev. D 97, 075003 (2018).
  * (59) F. Scardigli, G. Lambiase, E.C. Vagenas, J. Phys. Conf. Ser. 880, 012044 (2017).
  * (60) T. Kanazawa, G. Lambiase, G. Vilasi, A. Yoshioka, Eur. Phys. J. C 79, 95 (2019).
  * (61) M.J. Duff, Phys. Rev. D 9, 1837 (1974).
  * (62) J.F. Donoghue, Phys. Rev. Lett. 72, 2996 (1994); Phys. Rev. D 50, 3874 (1994).
  * (63) J.F. Donoghue, Front. in Phys. 8, 56 (2020).
  * (64) H.W. Hamber, S. Liu, Phys.Lett.B 357, 51 (1995);
I.B. Khriplovich, G.G. Kirilin, J.Exp.Theor.Phys. 95, 981 (2002);
I.B. Khriplovich, G.G. Kirilin, J.Exp.Theor.Phys. 98, 1063 (2004);
N.E.J. Bjerrum-Bohr, J.F. Donoghue, B.R. Holstein, Phys.Rev.D 68, 084005
(2003); Erratum-ibid.D 71, 069904 (2005).

  * (65) N.E.J. Bjerrum-Bohr, J.F. Donoghue, B.R. Holstein, Phys.Rev.D 67, 084033 (2003); Erratum-ibid.D 71, 069903 (2005);
A.Akhundov, A.Shiekh, EJTP 5, No. 17, 1 (2008);
C. Kiefer, J. Phys. Conf. Ser. 442, 012025 (2013);
N.E.J. Bjerrum-Bohr, J.F. Donoghue, B.R. Holstein, L. Planté, P. Vanhove,
Phys. Rev. Lett. 114, 061301 (2015);
J.F. Donoghue, B.R. Holstein, J. Phys. G 42 10, 103102 (2015).

  * (66) F. Scardigli, G. Lambiase, in preparation.
  * (67) P. Jizba, H. Kleinert, F. Scardigli, Phys. Rev. D 81, 084030 (2010).
  * (68) Y.C. Ong, JCAP 09 (2018), 015.
  * (69) P. Jizba, G. Lambiase, G.Luciano, L. Petruzziello [arXiv:2201.07919]
  * (70) P.A. Bushev, J. Bourhill, M. Goryachev, N. Kukharchyk, E. Ivanov, S. Galliou, M.E. Tobar, S. Danilishin, Phys. Rev. D 100 (2019) no.6, 066020.
  * (71) F. Marin, M. Cerdonio et al., Nat. Phys. 9, 71 (2013).
  * (72) S. Ghosh, Class. Quantum Gravity 31, 025025 (2014).
  * (73) M. Bawaj, C. Biancofiore, F. Marin et al., Nat. Commun. 6, 7503 (2015).
  * (74) A.F. Ali, S. Das, E.C. Vagenas, Phys. Rev. D 84, 044013 (2011);
S. Das, E.C. Vagenas Can. J. Phys. 84, 233 (2009).

  * (75) C. Quesne, V.M. Tkachuk, Phys. Rev. A 81, 012106 (2010).
  * (76) D. Gao, M. Zhan, Phys. Rev. A 94, 013607 (2016).
  * (77) J. Steinhauer, Nature Physics 10, 864 (2014);
R. Cowen, Nature News, 12 October 2014, Hawking radiation mimicked in the lab,
(doi:10.1038/nature.2014.16131).


# Quantum Annealing with Special Drivers for Circuit Fault Diagnostics

Hannes Leipold1,2,∗, Federico M. Spedalieri1,3 1Information Sciences
Institute, University of Southern California, Marina del Rey, CA 90292, USA
2Department of Computer Science, University of Southern California, Los
Angeles, CA 90089, USA
3Department of Electrical and Computer Engineering, University of Southern
California, Los Angeles, CA 90089, USA
$\ast$Corresponding author: Hannes Leipold<EMAIL_ADDRESS>
###### Abstract

We present a very general construction for quantum annealing protocols to
solve Combinational Circuit Fault Diagnosis (CCFD) problems that restricts the
evolution to the space of valid diagnoses. This is accomplished by using
special local drivers that induce a transition graph on the space of feasible
configurations that is regular and instance independent for each given circuit
topology. Analysis of small instances shows that the energy gap has a generic
form, and that the minimum gap occurs in the last third of the evolution. We
used these features to construct an improved annealing schedule and
benchmarked its performance through closed system simulations. We found that
degeneracy can help the performance of quantum annealing, especially for
instances with a higher number of faults in their minimum fault diagnosis.
This contrasts with the performance of classical approaches based on brute
force search that are used in industry for large scale circuits.

##  I Introduction

Quantum computation can offer new and exciting prospects for solving problems
that are difficult with existing classical approaches Harrow and Montanaro
(2017)Arute  _et al._ (2019). Quantum Annealing (QA) and the Quantum
Approximate Optimization Algorithm Farhi  _et al._ (2014) are two popular
approaches for doing quantum computation on near-term quantum devices
Gyongyosi and Imre (2019a)Gyongyosi and Imre (2019b)Alexeev  _et al._
(2021)Preskill (2021). While Driver Hamiltonians in QA and ansatz strategies
in QAOA are often selected based on their simplicity to be implemented on
near-term devices, an exciting prospect to improve the performance of these
systems is to tailor these constructions to the underlying structure of the
problem being solved Bian  _et al._ (2016)Cerezo  _et al._ (2021)Hadfield
(2021). Many modern quantum computational frameworks attempt to leverage
quantum phenomena to solve combinatorial optimization problems. Among these is
quantum annealing (QA), which leverages adiabatic (or diabatic) evolution from
one Hamiltonian to another, usually through a standard interpolation.
Applications in combinational circuit fault diagnostics (CCFD) have gained
considerable attention Perdomo-Ortiz  _et al._ (2015)Bian  _et al._
(2016)Perdomo-Ortiz  _et al._ (2019) for quantum annealers to potentially
leverage quantum speed up. Developments in Constrained Quantum Annealing (CQA)
Hen and Spedalieri (2016)Hen and Sarandy (2016)Leipold and Spedalieri (2021)
and Quantum Alternating Operator Ansatz (QAOA) Hadfield  _et al._
(2017)Hadfield  _et al._ (2019)Wang  _et al._ (2020)Shaydulin  _et al._
(2020)Hadfield  _et al._ (2021) have centered around more novel driver
operators, with higher body interaction terms than the transverse field. As
noted in Ref. Bian  _et al._ (2016), driver Hamiltonians beyond the transverse
field are pertinent to understanding what QA can bring to solving such
problems and this work can be seen as a step in this direction.

In this paper we delineate a CQA approach for solving single input/output CCFD
problems that maintains support only on the space of valid diagnoses. By
constraining the anneal to only explore feasible states associated with a
given CCFD instance, we find a square root reduction in the size of the
explored space compared to the standard transverse field approach in the
explicit mapping setting Perdomo-Ortiz  _et al._ (2019). It also avoids the
need to impose energy penalties on the final Hamiltonian to suppress invalid
diagnoses, that in turn results in stringent requirements for the range of the
interaction parameters. The driver terms that are needed to do this are all
local (with bounded weight), representing the possible transformations that
takes a feasible configuration to another feasible configuration involving
only the variables associated with a single circuit gate. These driver terms
are sufficient and minimal for describing a driver Hamiltonian that constrains
the evolution to the subspace of all valid diagnoses, such that they form a
generating set for all possible driver Hamiltonians that constrain the
evolution to this feasibility space Leipold and Spedalieri (2021).

To solve an instance of the CCFD problem we need, (i) an initial 1-local
Hamiltonian that has as its ground state the trivial diagnosis (all faults
occur in the output gates), (ii) a driver Hamiltonian composed of the driver
terms discussed in the previous paragraph, and (iii) a final Hamiltonian (also
1-local) that favors diagnoses with the smaller number of faults. Utilizing a
standard interpolation between these three Hamiltonians, the wavefunction of
the system begins with support on a specific valid configuration and then
explores all valid configurations while the evolution of the instantaneous
Hamiltonian to the final Hamiltonian eventually restricts the wavefunction to
support on the subset of diagnoses with the minimum number of faults.

The paper is organized as follows. In Section II, we provide background on the
combinatorial problem CCFD and in Section III delineate how our approach can
be utilized to solve this problem. In Sec. IV, we analyze the minimum gap of
the annealing spectrum for a set of randomly generated non-degenerate
instances of a modified version of the C17 circuit form the ISCAS benchmarks
Brglez (1985), as well as the success probability for different choices of the
annealing schedule. We then construct a larger, richer family of instances on
which we run a generic but improved annealing schedule, and study the
relationship between the success probability, the degeneracy of the ground
space of the instance, and the number of faults of the minimum fault
diagnosis. While these instances require 52 qubits to represent explicitly,
because the closed system evolution occurs in a much smaller space, we are
still able to tractably simulate these systems on a workstation. The results
suggest our approach can be beneficial for employing quantum annealers to
solve instances where higher number of faults are needed to be able to
diagnose the circuit.

##  II Combinatorial Optimization for Circuit Fault Diagnostics

Figure 1: A schematic of the C17 circuit with a fault on output of the third
NAND gate for a given input/output pair. In Sec. IV, we generate new random
circuits by replacing each NAND gate with a randomly selected two input logic
gate.

Consider a combinational circuit with $N$ wires (or locations), with $N_{I}$
inputs and $N_{O}$ outputs. Each wire can take one of two values, $x_{i}=0$ or
$x_{i}=1$, so a state of the circuit is associated with an $N$ bit string or
assignment, $(x_{1},\ldots,x_{N})$. The wires are connected to logical gates
in such a way that any wire that is not an input or an output for the entire
circuit, is connected to exactly two gates (it is the output of one gate and
the input to another one). Inputs (outputs) to the circuit are inputs
(outputs) to (for) one gate. The connectivity of the gates determines the
function performed by the circuit. This is referred to as the structural
description of the circuit, and is one of the most commonly used abstractions
in testing digital systems Jha and Gupta (2002).

For the purpose of our discussion here, we consider gates that are either fan
out gates (FAN), which maps a single input to two outputs such that the two
outputs have values equivalent to the input, an inverter gate (INV) or one of
the following logic gates: OR, AND, XOR, NOR, NAND. The methods described in
this paper can be extended trivially to a more general $k_{1}-$inputs,
$k_{2}-$outputs gate.

Since we are using the structural description of the circuit, we will use the
most well known structural fault model, the stuck-at fault (SAF) model of CCFD
Jha and Gupta (2002). In this model, a wire is either healthy, or fails by
being either stuck-at-0 (SA0) or stuck-at-1 (SA1). Given an input-output pair,
and a description of the circuit structure, a diagnosis is an explanation of
this input-output relationship that is consistent with the chosen fault model.
To describe a diagnosis, we will add to the $N$ bits describing the values of
each wire, another $N$ fault bits $f_{i}$, associated with each of the wires,
that would indicate if a wire is faulty ($f_{i}=1$) or not ($f_{i}=0$).

Under the assumption that every wire is equally likely to be faulty, the goal
of the circuit fault diagnosis (CFD) problem is to find the minimal number of
faults necessary to provide a consistent explanation for the outputs of the
circuit Perdomo-Ortiz  _et al._ (2015). We will refer to any diagnosis with
the minimum number of faults as a minimum fault diagnosis (MFD). Note that our
representation does not specify the type of fault (SA0 or SA1), but this
information can be inferred from the state of the wire: if a wire has a value
$x_{i}=1$ ($x_{i}=0$) and $f_{i}=1$, we can conclude the wire must be SA1
(SA0).

###  II.1 The set of valid diagnoses

We can refer to any $2N-$bit string as a diagnosis, in the sense that it
provides a description of the state of the wires on the system and the
location of potential faults. However, not any $2N-$bit string will represent
a fault assignment that is consistent with the chosen fault model. We will
call this subset of consistent assignments, the set of valid diagnoses. Hence,
a valid diagnosis can be represented by a $2N-$bit string,
$(x_{1},\ldots,x_{n},f_{1},\ldots,f_{n})$, where the first $N$ bits describe
the state of the circuit, while the last $N$ bits flag whether a wire is
healthy or not. For every wire location $i$, if the assignment value $x_{i}$
is not compatible with the logic of the gate that it is an output to and the
corresponding inputs for that gate, then the fault flag $f_{i}$ must be set to
1 for the assignment to valid, otherwise the assignment is invalid (as a false
negative). Likewise, if the assignment value $x_{i}$ is compatible, then the
fault flag $f_{i}$ must be set to 0, otherwise the assignment is invalid (as a
false positive).

The last $N_{O}$ wires correspond to the output bits of the circuit and are
fixed by the problem instance. Given a collection of empirical outputs for a
faulty circuit, there are potentially many valid diagnoses to explain this
phenomenon, since the faults could occur anywhere in the circuit, but a fault
occurring on a particular wire does not mean the subsequent wire values are
faulty since they were compatible with their respective gates (i.e. the inputs
for the gate were different from what the non-faulty circuit would have and
this led to their erroneous assignment). The first $N_{I}$ wires correspond to
the inputs and are in principle fixed. However, we must allow for a fault to
occur before the input wires reach the first gates, so the first $N_{I}$ wires
are allowed to take any value: any discrepancy with the actual inputs to the
circuit will be reflected by the corresponding fault bit being set to 1. The
consistency of the fault assignment is imposed on the wires and fault bits
associated with every gate in the circuit. We can illustrate this with the
following example.

Consider the bit string
$(x_{i_{1}},x_{i_{2}},x_{o};f_{i_{1}},f_{i_{2}},f_{o})$ representing the wires
and fault bits associated with a NAND gate in the circuit. The configuration
$(110;000)$ represents a consistent assignment, in the sense that the output
of the gate is compatible with its inputs, i.e.,
$x_{o}=\text{NAND}(x_{i_{1}},x_{i_{2}})$, and no wire is flagged as faulty;
$(100;001)$ is also a consistent assignment, because even though the output
wire is inconsistent with the inputs and the gate function
($x_{o}\neq\text{NAND}(x_{i_{1}},x_{i_{2}}))$, the output wire is flagged as
faulty ($f_{o}=1$). Examples of inconsistent assignments would be $(111;000)$
and $(011;001)$, where in the first case the output is incorrect but its fault
bit indicates no fault, while in the second case the output is correct but the
fault bit is flagging it as faulty. Note that the fault bit of a gate input is
of no importance in deciding whether the output of that gate is faulty or not:
the output is faulty (healthy) if it is inconsistent (consistent) with the
values of the inputs of the gate that produces it. A valid diagnosis will then
be described by a $2N-$ bit string, where for all circuit gates, the
corresponding wires and fault bits form a consistent assignment for the
specific function of that gate. In Table 1 we present an exhaustive list of
all consistent assignments for a NAND gate, indexed by the values of the input
and output wires.

($x_{i_{1}},x_{i_{2}};x_{o}$) | Consistent assignments ($x_{i_{1}},x_{i_{2}},x_{o};f_{i_{1}},f_{i_{2}},f_{o}$)
---|---
(0,0;0) | (0,0,0;0,0,1), (0,0,0;1,0,1), (0,0,0;0,1,1), (0,0,0;1,1,1)
(1,0;0) | (1,0,0;0,0,1), (1,0,0;1,0,1), (1,0,0;0,1,1), (1,0,0;1,1,1)
(0,1;0) | (0,1,0;0,0,1), (0,1,0;1,0,1), (0,1,0;0,1,1), (0,1,0;1,1,1)
(1,1;0) | (1,1,0;0,0,0), (1,1,0;1,0,0), (1,1,0;0,1,0), (1,1,0;1,1,0)
(0,0;1) | (0,0,1;0,0,0), (0,0,1;1,0,0), (0,0,1;0,1,0), (0,0,1;1,1,0)
(1,0;1) | (1,0,1;0,0,0), (1,0,1;1,0,0), (1,0,1;0,1,0), (1,0,1;1,1,0)
(0,1;1) | (0,1,1;0,0,0), (0,1,1;1,0,0), (0,1,1;0,1,0), (0,1,1;1,1,0)
(1,1;1) | (1,1,1;0,0,1), (1,1,1;1,0,1), (1,1,1;0,1,1), (1,1,1;1,1,1)
Table 1: Consistent assignments for a NAND gate: note that there is no
restriction on the values of the inputs, their fault bits and the output
(hence, we have $2^{5}=32$ configurations). However, the output fault bit is
completely determined by the values of the inputs and the output.

We can now see how to construct any possible valid diagnosis. Given any
arbitrary value for the first $N-N_{O}$ wires, and the values of the $N_{O}$
output wires, we can then univocally set the value of each fault bit $f_{i}$
such that it is consistent with the value of the wire and the constraint
imposed by the preceding gate. Hence the set of valid diagnoses has
$2^{N-N_{O}}$ elements.

##  III Constrained Quantum Annealing Approach

Quantum Annealing (QA) has been used in many combinatorial optimization tasks
Farhi  _et al._ (2000)Hen and Young (2011)Rieffel  _et al._ (2015)King  _et
al._ (2019). Many studied quantum annealing protocols involve two
Hamiltonians: a driver Hamiltonian like the transverse field
$H_{d}=-\sum_{i}\sigma_{i}^{x}$ and a final Hamiltonian made of single body
and two body spin-z interaction terms
$H_{f}=\sum_{i}\left(h_{i}\sigma_{i}^{z}+\sum_{j}J_{ij}\sigma_{i}^{z}\sigma_{j}^{z}\right)$
Perdomo-Ortiz  _et al._ (2019) ($\sigma_{i}^{x}$ and $\sigma_{i}^{z}$ are the
standard Pauli matrices). A typical linear transverse field annealing schedule
will then be $H(s(t))=(1-s(t))H_{d}+s(t)\,H_{f}$ with the time function
$s(t)=t/T_{f}$ for some specified total time $T_{f}$. The transverse field
driver Hamiltonian mixes configurations that differ by a single bit flip.
Applying it to our CFD problem would result in generating configurations that
are not valid diagnoses. One way to deal with this issue is to add a term to
the final Hamiltonian that penalizes any configuration that is not a valid
diagnosis. This is a commonly used technique to deal with constraints both in
classical and quantum optimization Lucas (2014)Venturelli  _et al._ (2015). In
QA this introduces other problems, such as a determining the right energy
scale for these penalty terms, and requiring more qubit connectivity to
represent them. Constrained Quantum Annealing (CQA) Hen and Spedalieri
(2016)Hen and Sarandy (2016)Leipold and Spedalieri (2021) and the Quantum
Alternating Operator Ansatz (QAOA) Hadfield  _et al._ (2017)Hadfield  _et al._
(2019)Wang  _et al._ (2020)Shaydulin  _et al._ (2020)Hadfield  _et al._ (2021)
have been introduced to avoid these precise issues, and our work aligns with
the spirit of these approaches.

In the case of CQA, a ground state for the driver Hamiltonian can be more
difficult to prepare and so annealing protocols are often generalized beyond a
two Hamiltonian interpolation. To overcome this barrier, we consider annealing
protocols involving three Hamiltonians, a form for annealing schedules often
seen when exploiting ‘catalysts’ Albash (2019)Albash and Kowalsky (2021)Cao
_et al._ (2021): $H(s(t))=A(s(t))\,H_{i}+B(s(t))\,H_{d}+C(s(t))\,H_{f}$ with
$s:[0,T_{f}]\rightarrow[0,1]$, $A(s(0))=1-B(s(0))=1-C(s(0))=1$, and
$A(s(T_{f}))=B(s(T_{f}))=1-C(s(T_{f}))=0$. In Sec. III.1 we show how to
explicitly construct the driver Hamiltonian for this approach and in Sec.
III.2 describe a general CQA protocol using an interpolation of an initial
Hamiltonian, the driver Hamiltonian, and a final Hamiltonian.

###  III.1 Special Drivers for CQA Solvers tackling CFD

The special CFD drivers are designed to locally connect pairs of valid
diagnoses. To each gate in the circuit we will associate operators that are
non-diagonal in the computational basis, which couple two valid diagnoses that
differ only on the qubits associated with that specific gate. Since each input
and output wire of a gate is mapped to two qubits (one for the wire value and
one for the fault bit), the special drivers will have a weight that is double
the number of inputs plus outputs of the gate.

We will now show how to construct the required drivers for a NAND gate (this
process can be extended to any other gate). Assume that we have a valid
diagnosis for the whole circuit, and let
$|x_{i_{1}}x_{i_{2}}x_{o};f_{i_{1}}f_{i_{2}}f_{o}\rangle$ be the corresponding
state restricted to the qubits associated with this specific NAND gate. We
want to find other configurations of these 6 qubits that also represent a
valid diagnosis. The transformed configuration must be locally and globally
consistent with the assignment of other wires and fault bits in the circuit.
To ensure global consistency, we must (i) keep the value of the output wire
fixed, to prevent propagating its effect forward, and (ii) flip the wire and
associated fault bit of any input simultaneously, since this will keep the new
assignment consistent with any previous gate for which this input wire is an
output. Summarizing, we can only change the input wires and their fault bits
(as long as the wire and the corresponding fault bit are flipped together),
and the output fault bit to ensure the local consistency of the new diagnosis.

To illustrate the idea, consider a valid diagnosis whose state restricted to
the qubits representing a given NAND gate are given by the state
$|100;001\rangle$, where the output wire is flagged as faulty because it does
not respect the gate’s functionality. If we flip $x_{i_{1}}$ and $f_{i_{1}}$,
we get $|000;101\rangle$ and the output fault bit remains unchanged since this
configuration still represents a failing NAND gate. Same if we flip both
inputs and their fault bits. However, if we flip only $x_{i_{2}}$ and
$f_{i_{2}}$, the resulting configuration $|110;011\rangle$ has an output wire
that now is consistent with the NAND gate, but its fault bit marks it as
faulty. Hence, we should also flip the output fault bit to $0$ to make it
consistent, resulting in the new local configuration $|110;010\rangle$.
Gathering all this information, we see that the required driver terms to
implement these local transformations of a valid diagnosis will be:

$\\{|000;101\rangle\langle 100;001|+h.c.,|110;010\rangle\langle
100;001|+h.c.,|010;111\rangle\langle 100;001|+h.c.\\},$ (1)

where h.c. stands for Hermitian conjugate. The same analysis can be carried
out for any valid configuration of the NAND gate. There are 32 such valid
configurations for a 2-input, 1-output gate (cfr. Table 1). For each one of
those we need 3 driver terms (per valid configuration) to perform the input
flips (and flip the output bit if necessary). But due to the hermiticity
requirement, the total number of driver terms is reduced by half, to 48.

###  III.2 Implementing CQA protocols for CFD with special drivers

In order to map an instance of CFD to our quantum annealing framework, we need
to specify an initial Hamiltonian, a driver Hamiltonian and a final
Hamiltonian. The driver Hamiltonian can be constructed from the circuit
description, as a linear combination of the drivers corresponding to each gate
in the gate set $G$ of the circuit. There is actually some freedom on what the
coefficients of this linear combination could be (as long as they are nonzero)
Leipold and Spedalieri (2021). This could potentially impact the performance
of the approach and developing useful strategies for choosing these
coefficients is an intriguing direction for future research. Here we will
discuss this briefly later when we compare the effects of stoquastic versus
non-stoquastic drivers, but for now we will proceed with the following
(stoquastic) assignment

$H_{D}=-\sum_{g\in G}H_{g},$ (2)

where each $H_{g}$ is a sum of the drivers associated with the gate $g$, which
we described how to construct in the previous section (see Eq. 1). Each gate
has a bounded number of drivers associated with it, so the total number of
terms in $H_{D}$ scales linearly with the number of gates in the circuit.

The initial Hamiltonian should have a ground state, written in the
computational basis, that is a valid diagnosis. Such a state can always be
found by simply assuming that all gates are healthy except for the gates that
produce the output bits that are known to be wrong. The input and output wires
are fixed by the instance, and the interior wire values are computed by
propagating the input through the healthy circuit. The fault bits are set to
0, except for the ones corresponding to the faulty output wires, which are set
to 1.

Let $|x_{1}\ldots x_{N}f_{1}\ldots f_{N}\rangle$ be that initial state. Then
we can initialize the system by implementing an initial Hamiltonian diagonal
in the computational basis given by

$H_{I}=\sum_{i=1}^{N}((-1)^{x_{i}}\,\sigma_{i}^{z}+(-1)^{f_{i}}\,\sigma_{N+i}^{z}),$
(3)

which has this initial state as its ground state. The final Hamiltonian must
penalize diagnoses that have a higher number of faults, so the Hamiltonian

$H_{F}=-\sum_{i=N+1}^{2N}\sigma_{i}^{z},$ (4)

where the sum is only over the fault bit qubits. We can then combine all this
into a time dependent Hamiltonian:

$H(s(t))=A(s(t))\,H_{I}+B(s(t))\,H_{D}+C(s(t))\,H_{F}.$ (5)

Hence, the system starts in a specific valid diagnosis, and once the driver is
turned on it will explore only the space of valid diagnoses. Finally, at the
end, the final Hamiltonian will favor diagnoses with the lowest number of
faults. In comparison to the transverse field approach used with explicit
mappings in Refs. Bian  _et al._ (2016)Perdomo-Ortiz  _et al._ (2015)Perdomo-
Ortiz  _et al._ (2019), there is no need for penalty terms associated with
constraining the solution to be a valid diagnosis, which also requires setting
a coefficient in the order of $N_{O}$ for the most general type of instances.

The action of the driver Hamiltonian allows us to reach any valid diagnosis
from any other valid diagnosis, so the adiabatic evolution generates a
superposition of all valid diagnoses. The graph induced by $H_{D}$ in this
space is connected and regular, with degree $(3G_{2}+G_{1})$, where $G_{2}$
and $G_{1}$ are the number of gates with 2 and 1 inputs, respectively.
Furthermore, for a given connectivity, the corresponding induced graphs are
isomorphic for all instances (i.e., any input-output pairs). This is due to
the fact that the driver terms are essentially just performing all possible
flips of the inputs of a gate, while the fault bits are flipped accordingly to
enforce the constraints of a valid diagnoses. In the next Section, we
benchmark the CQA approach discussed on small sized circuits.

##  IV Benchmarks on Synthetic Instances: Spectral Gaps and Simulated
Annealing Schedules

###  IV.1 Generalized ISCAS C17 Random Circuits: Spectral Gaps and
Parameterized Annealing Schedule

Our first example is a circuit known as C17 (see Fig. 1), that appeared in the
ISCAS’85 benchmarks Brglez (1985)Hansen  _et al._ (1999). This circuit has 17
wires, 5 inputs, 2 outputs, 6 NAND gates and 3 FAN gates. Using our approach,
it requires 34 qubits to represent all the wire values and the fault bits. The
reduced dynamics occurs on a space of dimension $2^{15}$, so it is possible to
simulate the closed system evolution and compute the spectrum along the
anneal.

We generated new circuit instances by randomly replacing the NAND gates with
other 2-input, 1 output gates, randomly chosen from the set {NAND, AND, OR,
NOR, XOR}. Then we randomly chose the 5 input bits, simulated the circuit to
compute the 2 output bits, and then flipped the value of these 2 outputs. The
CFD instance is then defined by the circuit description, and the input-output
pair. Note that the number of output bits that are faulty is always an upper
bound on the number of faults in the minimal fault diagnosis (MFD), since
assigning the fault only to those output bits is itself a valid diagnosis.
That is also the reason why we flipped both output bits, to make room for a
non-trivial MFD with a single fault.

####  IV.1.1 Spectral Gaps for C17 Instances

|
---|---
(1) | (2)
Figure 2: (1) shows the instantaneous minimum gap for 100 random instances of
the generalized C17 circuit at regular discretized points of time. (2)
similarly shows the instantaneous ground state gap for the same instances with
a non-stoquastic version of the driver Hamiltonian.

Fig. 2.1 shows the energy gap between the ground state and the first excited
state at every point during the anneal, for 100 randomly generated instances.
We can see that the gap always starts at 4 (due to the form of the initial
Hamiltonian, and the fact that any two valid diagnoses are at least Hamming
distance 2 away). Depending on the degeneracy of the instance, the gap either
has an absolute minimum during the anneal (non-degenerate), or goes to 0 at
the end of the anneal (degenerate). An interesting feature is that the minimum
gap for non-degenerate instances seems to be localized on the last third of
the anneal. The generic shape of the gap as a function of the anneal parameter
could be exploited to evolve the system faster at the beginning, when the gap
is large. This would only result in a constant factor reduction in the total
annealing time required, so it has no impact on the complexity, but is useful
for simulating larger circuits.

We also computed the spectrum corresponding to flipping the sign of the
Hamiltonian driver, which produces a non-stoquastic Hamiltonian. Due to the
infamous sign problem, non-stoquastic Hamiltonians are thought to be harder to
simulate than stoquastic ones Albash (2019)Crosson and Harrow (2016), leading
some to conjecture they may provide some computational speedup in some
situations and non-stoquastic catalyst Hamiltonians, such as considered in
Ref. Albash (2019), are able to achieve large improvements over catalyst-free
approaches in the finite and infinite Nishimori and Takada (2017) range
ferromagnetic p-spin model. Ref. Choi (2021) likewise shows possible
improvements from introducing non-stoquastic terms in a driver Hamiltonian.
However, there is also evidence Crosson  _et al._ (2020) that they can produce
smaller energy gaps, resulting in a computational slowdown.

In Fig. 2.2 we show the minimum gap for the non-stoquastic version of the
driver Hamiltonian. Comparing this with Fig. 2.1 we can see that in this case,
the minimum gap seems to be generically smaller, and the region where the gap
is small is also larger. It is important to point out that these are not the
only choices for the coefficients of the terms in the driver Hamiltonian.
Since these coefficients determine how different diagnoses are mixed by the
driver, one could imagine that a better choice, perhaps one that exploits the
particular structure of the circuit, may favor some sort of interference that
could enhance diagnoses with lower number of faults and result in a
computational advantage. However, it is not clear at this point if that is
feasible, or even what the complexity of finding those coefficient would be.
It is nonetheless an intriguing direction for future research.

####  IV.1.2 Choosing annealing schedule to exploit spectrum features

(1) (2)

Figure 3: (1) and (2) show the success probability versus the minimum gap for
22 non-degenerate single fault instances of the C17, with 40 units and 80
units of time respectively, for the single parameter function (labeled param),
the linear function (labeled linear) and a piece-wise linear function fitted
over 100 evenly spaced points, such that the slope is proportional to the
instantaneous inverse gap squared between evenly spaced $s_{i-1}$ and $s_{i}$
(labeled opt_adia).

For our annealing schedule, we chose functions $A(s(t))=1-s^{2}(t)$,
$B(s(t))=4s\,(1-s)$, and $C(s(t))=s^{2}(t)$ (the instantaneous Hamiltonian is
then given by Eq. 5). We utilized the generic features of the energy gap for
C17 (and in Sec. IV.2 for C26), to generate a single parameter annealing
schedule, that evolves faster at the beginning of the anneal (when the gap is
larger), and then slows down when traversing the region containing the minimum
gap. For a given amount of total anneal time $T_{f}$, the annealing schedule
assigns $T_{0}$ ($T_{0}<T_{f}$) units of time for the range $[0,s_{0}]$,
following a quadratic function, and then shifts at point $T_{0}$ to a linear
function over the interval $[s_{0},1]$ such that $s^{\prime}(T_{0})$ is not a
point of discontinuity. These conditions yield:

$\displaystyle
s(t)=\begin{cases}\left(\frac{s_{0}\left(T_{f}/T_{0}\right)-1}{T_{0}\left(T_{0}-T_{f}\right)}\right)t^{2}+\left(\frac{1-s_{0}\left(2\,\left(T_{f}/T_{0}\right)-1\right)}{T_{0}-T_{f}}\right)t,&t<T_{0}\\\
\left(\frac{s_{0}-1}{T_{0}-T_{f}}\right)t+\left(\frac{1-s_{0}\left(T_{f}/T_{0}\right)}{1-\left(T_{f}/T_{0}\right)}\right),&t>T_{0}\end{cases}$

In the experiments on C17, $T_{0}$ was set to $20$ units and $s_{0}$ was set
to $3/4$. We used the DifferentialEquations.jl Rackauckas and Nie (2017)
package in Julia Bezanson  _et al._ (2017) to simulate the Schrödinger
equation for the time interval $[0,T]$ in this and the succeeding Section.
Results in Fig. 3 suggests that while this parameterized function is not an
optimal strategy (a strategy that optimally exploits the adiabatic condition
is represented in the plot by opt_adia), it has a clear advantage over the
linear function and is therefore used in the next Section on benchmarks for
the C26 circuit.

###  IV.2 Generalized C26 Random Circuits: Effects of Degeneracy and Multi-
Fault Solution Spaces

Figure 4: A schematic of the C26 circuit. For our C26 benchmarks, we replace
each NAND gate with a randomly selected two input logic gate as well as
randomly select inputs to the circuit. Each has 8 2-input logic gates, 6 FAN
gates, 26 wires, 6 inputs, and 4 outputs.

The number of outputs of a circuit is an upper bound on the number of faults
of the minimum fault diagnosis. Since the C17 has only two outputs, if both of
these are faulty, the MFD can have either 1 or 2 faults; the latter case is
trivial (just assign the faults to the output bits), and the non-trivial case
of a single fault is rather simple. In order to explore instances that offer
higher complexity, we need to consider circuits with a larger number of
outputs. In this section, we consider a modification of C17 to a 26 wire, 6
input, 4 output circuit that we call C26 (see Fig. 4 for a schematic).

While the circuits studied in Sec. IV.1 required 34 qubits to represent
explicitly, the evolution of the wavefunction is restricted to a subspace of
dimension $2^{15}$. In this section we consider a larger class of circuits
that require 52 qubits to represent explicitly, but whose wavefunction
evolution is restricted to a subspace of size $2^{22}$, which is still
simulatable for sparse Hamiltonians.

|
---|---
(1) | (2)
Figure 5: (1) shows a box and whisker plot of the logarithm of the minimum gap
as a function of the number of faults in the MFD, while (2) shows a box and
whisker plot of the location of the minimum gap versus the MFD number of
faults, for randomly generated instances of C26 with non-degenerate ground
states.

We generated random instances of C26 following the same procedure described in
Sec. IV.1, and we selected 100 non-degenerate instances for each value (1, 2
and 3) of the number of faults in the MFD. We selected non-degenerate
instances so that we could identify the location and size of the minimum gap
(degenerate instances have a vanishing gap as $s\rightarrow 1$), and also
because these are in some sense the hardest instances. In Fig. 5.1 we see
that, even though the distribution of the minimum gap seems to spread towards
smaller values as we increase the number of faults in the MFD, the median
shows only a rather mild dependence. This means that an annealing schedule
designed to solve, say, all non-outlier 1-fault MFD instances, will also solve
about 75% and just above 50% of 2-fault and 3-fault MFD instances,
respectively. In Fig. 5.2, we also see that the location of the gap (similar
to the C17 case) occurs in a well defined range for most instances and this
appears stable with regard to the number of faults of the MFD.

However, as we consider larger circuits, the degeneracy of the MFD subspace
will also potentially increase. That could be beneficial for a quantum
annealing approach, since jumps from the ground state to excited states may
still result in optimal solutions at the end of the anneal. Of course, we
cannot know a priori whether a given instance is degenerate or non-degenerate,
and what is the number of faults of its MFD. In order to gain some more
insight into the performance of our approach on generic CFD instances, we
simulated the closed system evolution and computed the success probability for
a new set of randomly generated instances of CFD for C26, without implementing
any type of post-selection. The only feature we exploited was the generic form
of the spectrum (as seen in Fig. 2.1), and implemented the modified annealing
schedule detailed in Sec. IV.1.

We simulated the annealing protocol for 100 randomly generated instances
(including those with degenerate ground spaces) for a total annealing time of
40, 60, 80, and 140 units. Note that (following our parameterized annealing
schedule) 20, 40, 60, and 120 time units were consumed on the interval
$[3/4,1]$, using a linear function, and always 20 time units were used on the
interval $[0,3/4]$ using a quadratic function. Fig. 6 shows the results of
these experiments. First, we note that random instance seem more likely to
have 2-fault and 3-fault MFDs, and these in turn tend to be more degenerate.
Instances with a 1-fault MFD were always non-degenerate, and were the hardest
instances to solve. In general, we can see that instances with low degeneracy
are typically harder than those with high degeneracy. From a quantum annealing
point of view we can understand this as results of the many jumps the system
must go through to go from the ground state to the first state that is not
part of the ground state manifold (i.e., the set of eigenstates that will end
up converging into the ground state of the final Hamiltonian). High degeneracy
seems to add extra protection against the effects of diabatic transitions,
resulting in higher success probabilities.

|
---|---
(1) | (2)
|
(3) | (4)
Figure 6: Logarithm of success probability as a function of instance
degeneracy and number of faults in the MFD (for different values of the total
annealing time $T_{f}$).

##  V Conclusions

In this work, we introduced a novel approach to solving the CFD problem, where
the quantum state throughout the anneal is constrained to the space of valid
diagnoses. of size $2^{N-N_{O}}$ (rather than $2^{2N}$ for the total space).
Previously studied QA approaches have relied on a transverse field driver
Hamiltonians to solve CFD problems Bian  _et al._ (2016)Perdomo-Ortiz  _et
al._ (2015)Perdomo-Ortiz  _et al._ (2019). As noted in Ref. Bian  _et al._
(2016), more novel driver Hamiltonians are one of the clearest routes to
improving the performance for QA on such classes of problems and this work can
be considered a step in this direction, relying specifically on the
development and theory of CQA Hen and Spedalieri (2016)Hen and Sarandy
(2016)Leipold and Spedalieri (2021). Ordinary transverse field quantum
annealing approaches typically require imposing penalty terms to suppress
configurations that do not satisfy the problem constraints. Our approach
exploits the structure of the problem to construct a set of special drivers
(whose number is linear on the size of the circuit) that naturally implement
transitions only between valid configurations.

We constructed a family of circuit instances generalizing the ISCAS C17 (17
wires, 5 inputs, 2 outputs) and analyzed the performance of the delineated
protocol on these instances. By analyzing the spectral gap of a set of random
instances, we were able to exploit its features (mainly the approximate
location of the minimum gap) to construct an annealing schedule that evolved
faster in regions of large spectral gap. This information was then utilized to
benchmark the performance of the approach on a family of larger circuits with
26 wires, 6 inputs, and 4 outputs (which we refer to as C26). We looked at the
minimum gap for instances with non-degenerate solutions (i.e., those having
unique solutions with the minimum number of faults), and found that the size
of this gap had a mild dependence with the number of faults in the MFD. This
is of interest, because large circuit ($\sim 10^{6}$ wires) CFD problems
typically found in industrial applications are currently solved using a brute
force search approach, by looking for diagnosis with a fixed number of faults
(typically 1 or 2). Since the complexity of this approach scales exponentially
with the number of faults, it is currently not practical to search for
diagnoses with higher number of faults. In contrast, the mild dependence of
the minimum gap on the number of faults of the MFD suggests that our QA based
approach could solve some instances with more faults in their MFDs, using a
fixed amount of computational resources, since QA is essentially characterized
by the minimum gap.

In our QA approach based on special drivers, we chose the sign of each term in
a way to make the overall Hamiltonian stoquastic. We considered one possible
way of making it non-stoquastic by changing the sign of each driver term.
Since non-stoquastic Hamiltonians could be more difficult to simulate, it has
been speculated that they could provide more computational power. In our
particular case, computing the spectral gap showed that the minimum gap was
typically smaller than for the stoquastic case, which would translate into a
lower success probability for solving our CFD problem. However, it is
important to point out that there are many ways of setting the phases of the
driver terms in order to make the Hamiltonian non-stoquastic. A different
choice (maybe informed by the circuit structure) could induce more
interference effects between different diagnoses during the evolution, thereby
possibly enhancing those with a lower number of faults. This is an intriguing
possibility that we plan to pursue in future work.

In analyzing the performance of our approach, we focused on mainly two aspects
we believe could prove beneficial when applied to larger scale problems. One
was exploiting the generic form of the minimum gap as a function of the
annealing parameter. We showed that it starts large, decreases almost
monotonically and reaches a minimum in the last third of the anneal. These
generic features allowed for a tailored schedule that moves faster at the
beginning and slows down at the end where the minimum gap is typically
located. We showed that this improves the probability of success for a given
total anneal time, which will reduce the time needed to see a solution (i.e.,
the number of times the annealing should be repeated).

The other aspect we studied was the dependence of the minimum gap on the
number of faults in the MFD (minimum fault diagnosis). Our simulations showed
that the dependence is rather mild, and furthermore, the increased degeneracy
seen in instances with a higher number of faults in their MFD translated to a
higher probability of success for instances with larger number of faults in
their MFD. This is of interest because in practice (i.e., in actual industrial
applications), large instances of CFD are tackled using exhaustive search for
diagnoses with low number of faults (i.e., a few). Since the complexity of
such search increases exponentially with the number of faults, this can become
impractical for circuits with $10^{6}$, wires and diagnoses with more than 2
faults. Our analyses suggest that a QA approach could push this boundary
further, resulting in significant practical (economical) impact.

We would like to address the lack of head-to-head comparisons of our approach
with classical algorithms. Our analysis involved simulating the quantum
evolution of systems that required considerable computational effort (C26 was
represented using 22 qubits in the reduced subspace). However, these circuits
are still small for classical methods: since the number of faults is upper
bounded by the number of circuits outputs, our examples were still in the
regime where exhaustive search would be extremely fast and classical
algorithms more closely related to QA, such as simulated annealing, can be
misleading to make comparisons with. Hence, we considered that a head-to-head
comparison of time to solution for example, would not be very illuminating.
Instead, as discussed in the previous two paragraphs, we decided to focus our
analysis on features of the QA approach that we believe could provide an
improvement when applied to larger circuits, where the combinatorial hardness
of CFD becomes unavoidable for classical algorithms.

Finally, we would like to note that our approach, even though designed with a
quantum annealing framework in mind, can be translated to the circuit model of
quantum computing, following the framework of the QAOA approach. For example,
the construction of individual driver terms around gates can be translated
into unitary mixing terms for the ansatz strategy based on the same underlying
structure. Furthermore, since the structure of these driver terms is related
to the circuit structure, it could be possible to gain some insight into
better ways of choosing the mixing parameters, which could improve the
performance of the QAOA approach. We consider this an intriguing direction for
future research.

##  VI Acknowledgements

FS thanks Sandeep Gupta for many useful conversations about the CFD problem.
The research is based upon work (partially) supported by the Office of the
Director of National Intelligence (ODNI), Intelligence Advanced Research
Projects Activity (IARPA) and the Defense Advanced Research Projects Agency
(DARPA), via the U.S. Army Research Office contract W911NF-17-C-0050. The
views and conclusions contained herein are those of the authors and should not
be interpreted as necessarily representing the official policies or
endorsements, either expressed or implied, of the ODNI, IARPA, or the U.S.
Government. The U.S. Government is authorized to reproduce and distribute
reprints for Governmental purposes notwithstanding any copyright annotation
thereon.

The datasets used and/or analyzed during the current study are available from
the corresponding author upon reasonable request.

## References

  * Harrow and Montanaro (2017) A. W. Harrow and A. Montanaro, Nature 549, 203 (2017).
  * Arute  _et al._ (2019) F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Nature 574, 505 (2019).
  * Farhi  _et al._ (2014) E. Farhi, J. Goldstone, and S. Gutmann, arXiv preprint arXiv:1411.4028 (2014).
  * Gyongyosi and Imre (2019a) L. Gyongyosi and S. Imre, Quantum Information Processing 18, 1 (2019a).
  * Gyongyosi and Imre (2019b) L. Gyongyosi and S. Imre, Computer Science Review 31, 51 (2019b).
  * Alexeev  _et al._ (2021) Y. Alexeev, D. Bacon, K. R. Brown, R. Calderbank, L. D. Carr, F. T. Chong, B. DeMarco, D. Englund, E. Farhi, B. Fefferman, _et al._ , PRX Quantum 2, 017001 (2021).
  * Preskill (2021) J. Preskill, Scientific Reports 11, 19587 (2021).
  * Bian  _et al._ (2016) Z. Bian, F. Chudak, R. B. Israel, B. Lackey, W. G. Macready, and A. Roy, Frontiers in ICT 3, 14 (2016).
  * Cerezo  _et al._ (2021) M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, _et al._ , Nature Reviews Physics 3, 625 (2021).
  * Hadfield (2021) S. Hadfield, ACM Transactions on Quantum Computing 2, 1 (2021).
  * Perdomo-Ortiz  _et al._ (2015) A. Perdomo-Ortiz, J. Fluegemann, S. Narasimhan, R. Biswas, and V. N. Smelyanskiy, The European Physical Journal Special Topics 224, 131 (2015).
  * Perdomo-Ortiz  _et al._ (2019) A. Perdomo-Ortiz, A. Feldman, A. Ozaeta, S. V. Isakov, Z. Zhu, B. O’Gorman, H. G. Katzgraber, A. Diedrich, H. Neven, J. de Kleer, _et al._ , Physical Review Applied 12, 014004 (2019).
  * Hen and Spedalieri (2016) I. Hen and F. M. Spedalieri, Physical Review Applied 5, 034007 (2016).
  * Hen and Sarandy (2016) I. Hen and M. S. Sarandy, Physical Review A 93, 062312 (2016).
  * Leipold and Spedalieri (2021) H. Leipold and F. M. Spedalieri, Quantum Science and Technology 7, 015013 (2021).
  * Hadfield  _et al._ (2017) S. Hadfield, Z. Wang, E. G. Rieffel, B. O’Gorman, D. Venturelli, and R. Biswas, in  _Proceedings of the Second International Workshop on Post Moores Era Supercomputing_ (2017) pp. 15–21.
  * Hadfield  _et al._ (2019) S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, Algorithms 12, 34 (2019).
  * Wang  _et al._ (2020) Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel, Physical Review A 101, 012320 (2020).
  * Shaydulin  _et al._ (2020) R. Shaydulin, S. Hadfield, T. Hogg, and I. Safro, arXiv preprint arXiv:2012.04713 (2020).
  * Hadfield  _et al._ (2021) S. Hadfield, T. Hogg, and E. G. Rieffel, arXiv preprint arXiv:2105.06996 (2021).
  * Brglez (1985) F. Brglez, Proc. IEEE ISCAS: Special Session on ATPG and Fault Simulation , 151 (1985).
  * Jha and Gupta (2002) N. K. Jha and S. Gupta,  _Testing of Digital Systems_ (Cambridge University Press, USA, 2002).
  * Farhi  _et al._ (2000) E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, arXiv preprint quant-ph/0001106 (2000).
  * Hen and Young (2011) I. Hen and A. Young, Physical Review E 84, 061152 (2011).
  * Rieffel  _et al._ (2015) E. G. Rieffel, D. Venturelli, B. O’Gorman, M. B. Do, E. M. Prystay, and V. N. Smelyanskiy, Quantum Information Processing 14, 1 (2015).
  * King  _et al._ (2019) J. King, S. Yarkoni, J. Raymond, I. Ozfidan, A. D. King, M. M. Nevisi, J. P. Hilton, and C. C. McGeoch, Journal of the Physical Society of Japan 88, 061007 (2019).
  * Lucas (2014) A. Lucas, Frontiers in Physics 2, 5 (2014).
  * Venturelli  _et al._ (2015) D. Venturelli, D. J. Marchand, and G. Rojo, arXiv preprint arXiv:1506.08479 (2015).
  * Albash (2019) T. Albash, Physical Review A 99, 042334 (2019).
  * Albash and Kowalsky (2021) T. Albash and M. Kowalsky, Physical Review A 103, 022608 (2021).
  * Cao  _et al._ (2021) C. Cao, J. Xue, N. Shannon, and R. Joynt, Physical Review Research 3, 013092 (2021).
  * Hansen  _et al._ (1999) M. C. Hansen, H. Yalcin, and J. P. Hayes, IEEE Design & Test of Computers 16, 72 (1999).
  * Crosson and Harrow (2016) E. Crosson and A. W. Harrow, in  _2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)_ (IEEE, 2016) pp. 714–723.
  * Nishimori and Takada (2017) H. Nishimori and K. Takada, Frontiers in ICT 4, 2 (2017).
  * Choi (2021) V. Choi, arXiv preprint arXiv:2105.02110 (2021).
  * Crosson  _et al._ (2020) E. Crosson, T. Albash, I. Hen, and A. Young, Quantum 4, 334 (2020).
  * Rackauckas and Nie (2017) C. Rackauckas and Q. Nie, The Journal of Open Source Software 5 (2017), 10.5334/jors.151, r package version 1.1.1.
  * Bezanson  _et al._ (2017) J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, SIAM review 59, 65 (2017).