# From Quantum Mechanics to
Quantum Software Engineering

Giuseppe Bisicchia, Jose Garcia-Alonso, Juan M. Murillo, and Antonio Brogi G.
Bisicchia and A. Brogi are with the Department of Computer Science, University
of Pisa (Pisa, Italy).J. Garcia-Alonso and J. M. Murillo are with Quercus
Software Engineering Group, University of Extremadura (Cáceres,
Spain).Corresponding author<EMAIL_ADDRESS>partly
supported by projects: hOlistic Sustainable Management of distributed softWARE
systems (OSMWARE), PRA_2022_64, funded by the University of Pisa;
PID2021-1240454OB-C31, funded by the Spanish Ministry of Science, Innovation
and Universities; GR21133, funded by the Regional Ministry of Economy, Science
and Digital Agenda of the Regional Government of Extremadura.

###### Abstract

Victor Hugo’s timeless observation, ‘Nothing is more powerful than an idea
whose time has come’, resonates today as Quantum Computing, once only a dream
of a physicist, stands at the threshold of reality with the potential to
revolutionise the world. To comprehend the surge of attention it commands
today, one must delve into the motivations that birthed and nurtured Quantum
Computing. While the past of Quantum Computing provides insights into the
present, the future could unfold through the lens of Quantum Software
Engineering. Quantum Software Engineering, guided by its principles and
methodologies investigates the most effective ways to interact with Quantum
Computers to unlock their true potential and usher in a new era of
possibilities. To gain insight into the present landscape and anticipate the
trajectory of Quantum Computing and Quantum Software Engineering, this paper
embarks on a journey through their evolution and outlines potential directions
for future research.

###### Index Terms:

Quantum Computing, Quantum Software Engineering.

##  I A Brief History of Quantum Computing

‘What kind of computer are we going to use to simulate physics?’ It was the
Nobel laureate Richard Feynman who raised this question in his visionary talk
[1], beginning the history of Quantum Computing111To be fair, already a few
years earlier, in 1980, mathematician Yuri Manin pointed out the problems in
simulating quantum systems with classical computers [2]. Independently,
between 1980 and 1982, the physicist Paul Benioff proposed a quantum
mechanical model of Turing machines [3, 4], a topic also discussed by Feynman
in 1985 [5]..

This question is rooted in a series of crises and revolutions [6, 7, 8, 9, 10,
11] that shook the world of physics to its foundations between 1900 and 1925.
The result of that period of turmoil was a new fundamental theory of physics
which describes the behaviour of Nature at subatomic levels: Quantum Mechanics
[12, 13, 14].

Manin and Feynman’s concerns [1, 2, 5] on the simulation of physical systems
were primarily about the difficulties of modelling quantum systems. In such
systems, the number of variables required to represent them increases
exponentially with their complexity and with the number of particles
involved222On the other hand, the number of variables to describe classical
physical systems grows only linearly with their complexity..

Following these considerations, in 1985, physicist David Deutsch suggested, in
his seminal work [15], a deeper connection between computing and physics,
stating a stronger ‘physical version’ of the Church-Turing thesis333Here is
reported a version, from [15], for completeness: ‘Every function which would
naturally be regarded as computable can be computed by the universal Turing
machine’.. Such thesis, also called the Church–Turing–Deutsch principle states
that:

> Every finitely realizable physical system can be perfectly simulated by a
> universal model computing machine operating by finite means.

With his physical interpretation of the Church-Turing thesis, Deutsch brought
attention to an often neglected fact about computation. Every algorithm is
actually performed by a physical system, whether it be an electronic
calculator, a mechanical apparatus or a human being. Thus, computation is
ultimately a physical process and, hence, a universal computer (that is a
physical system too) must be able to simulate the dynamics of every possible
physical system.

The consequences of the physics revolution in the early 20th century, however,
led scientists to postulate that the fundamental nature of physics is
ultimately quantum mechanical. Unfortunately, classical systems seem to be
ineffective in efficiently simulating quantum mechanical systems [1, 2].
Deutsch was then naturally led to propose a universal computing device based
on the principles of quantum mechanics [15], so as to overcome the limitations
of classical computers: the quantum computer was born.

Pretty soon, the potential of quantum computers began to be, as Deutsch
surmised, far more impactful than just simulating physical systems. In 1992,
David Deutsch, in collaboration with Richard Jozsa, formulated a problem that,
even if of little practical interest, can be solved more efficiently by
quantum devices than by any classical or stochastic algorithm [16]. Shortly
afterwards, in 1993, Ethan Bernstein and Umesh Vazirani proposed another
problem, showing the advantage of quantum devices over classical ones even
when small errors are allowed [17]. In the same work, Bernstein and Vazirani
designed a quantum version of the Fourier transform444The Quantum Fourier
Transform serves as the quantum counterpart to the Discrete Fourier Transform,
offering an efficient quantum algorithm for implementing Fourier Transform
operations. Crucial in various quantum algorithms, it plays a fundamental role
in extracting and translating purely quantum information stored within qubits
into classically measurable outcomes. [18]. In 1994, leveraging the quantum
Fourier transform and the work of Daniel Simon [19], who showed that a quantum
computer could find the period of a function with an exponential speedup,
Peter Shor presented an efficient quantum algorithm for computing discrete
logarithms. Only a few days later, Shor formulated an efficient quantum
algorithm also for factoring large numbers [20]. Both problems are believed to
be intractable on classical computers, and thereby commonly used in
cryptographic protocols [21, 22]. Just two years later, Seth Lloyd proved that
quantum computers could simulate quantum systems without the exponential
overhead present in classical simulations, confirming Feynman’s 1982
conjecture [23]. In the same year, Lov Grover presented a quantum algorithm
achieving an optimal quadratic speedup for unstructured search [24]. Shor and
Grover’s breakthroughs gave a strong impetus to the research on quantum
algorithms, demonstrating the existence of useful problems that benefit from a
quantum speedup.

Meanwhile, research into working quantum computers also began to take its
first steps. In 1993, Seth Lloyd proposed a method for building a potentially
realisable quantum computer through pulsed quantum arrays, i.e., arrays of
weakly coupled quantum systems subjected to a sequence of electromagnetic
pulses of specific lengths and frequencies [25]. Not long afterwards, in 1995,
Juan Cirac and Peter Zoller suggested an implementation of a quantum computer
employing cold ionised atoms confined in electric potential traps and
interacting with laser beams [26]. Following the developments in the field,
just one year later, David DiVincenzo formalised five minimal requirements for
creating a working quantum computer. Such criteria include the availability of
scalable qubits555A ‘qubit’ is the computational unit of a Quantum Computer
(as opposed to the classical bit). A qubit state can be 0, 1 or in a
superposition (i.e., linear combination) of both. In the latter, when measured
it will be only 0 or 1, with different probabilities according to its
superposition. highly isolated from the external environment, the ability to
initialise, manipulate and entangle their state and to ‘strongly’666With
‘strong’ measurement it is meant a measure capable of collapsing the state of
a qubit. measure the state of each qubit [27]. A further milestone was set by
Yasunobu Nakamura et al., between 1991 and 2001, who built a working,
controllable superconducting qubit through a Josephson junction [28, 29].

In those years, however, a shadow threatened and questioned the very
foundations of Quantum Computing [30]. The decoherence menaced to dash any
hopes of having actually usable quantum computers [31]. Decoherence is the
phenomenon that, under typical conditions, prevents complex many-particle
quantum systems from exhibiting quantum behaviour for a long time, stranding
the dream of a quantum computer with no way out [32]. It was Shor again who
gave hope and new life to the field. Shor demonstrated in 1995 how it was
possible to reduce the destructive effects of decoherence through the quantum
analogue of error-correcting codes [33] and fault-tolerant methods for
executing reliable quantum computations on noisy quantum computers [34]. The
work of Shor and others [35, 36, 37] thus confirmed that it is possible, at
least in principle, to suppress the error rate of a quantum computer to
arbitrarily low levels, thanks to error correction schemes and as long as the
error rate is below a certain threshold777The assumptions made regarding the
computational capability have a significant impact on the precise value of the
threshold, but it is considered in the range $10^{-4}-10^{-6}$ [38]., this is
the so-called threshold theorem [39].

Significant developments have been made since those first steps in both
quantum software and hardware [38, 40]. In 2011, the first ever commercially
available quantum computer was presented, and sold, by D-Wave [41]. It was
D-Wave One, a 128-qubit quantum annealer888A quantum annealer is a specialised
form of quantum computer. Unlike universal quantum computers, quantum
annealers are non-Turing complete devices tailored specifically for solving
optimisation problems as energy minimisation problems. Roughly speaking,
quantum annealers ensure that each qubit eventually settles into a classical
state that reflects the minimum energy configuration of the problem [42].
[43]. In 2016, IBM put online their 5-qubit, gate-based999Unlike quantum
annealers, gate-based quantum computers are universal computing machines. A
gate-based quantum computer operates by manipulating qubits through the
quantum analogue of classical logical gates [44]., superconducting quantum
computer, making quantum computing publicly available for the first time,
through the cloud [45, 46]. In 2018, the first commercial quantum computer
employing trapped ions was launched by IonQ [47]. Just one year later, Google
claimed the achievement of quantum supremacy101010Quantum Supremacy is the
goal to ‘perform tasks with controlled quantum systems going beyond what can
be achieved with ordinary digital computers’ [48]. with their 54-qubit,
superconducting processor ‘Sycamore’ [49]. However, some doubts arose shortly
afterwards [50, 51, 52] and eventually classical devices beat Google’s result
[53]. The last current milestone in the quantum race was set in 2023 by IBM,
which announced evidence for the utility of quantum computing even with noisy
hardware, showing how it is possible to produce reliable results even without
fault-tolerant quantum computers and at a scale beyond brute-force classical
computation [54]. Also in this case, though, the scientific community does not
entirely agree [55, 56, 57, 58].

Nevertheless, even though the supremacy and utility of quantum computers have
not yet been established beyond a shadow of a doubt, there is no denying that
we are now at the gates of a new era [59, 60, 61]. Indeed, even if quantum and
classical computers feature the same computational power [15], i.e., they can
solve the same class of problems, it is believed (and some evidence began to
arise) [62, 63, 64, 65], that quantum computers can solve some problems
asymptotically faster than what it is possible just with classical resources
[66]. In fact, increasingly cutting-edge applications are emerging, promising
to revolutionise numerous industries and sectors and with a potentially
immeasurable impact on society [67]. Among the most researched areas are
medicine, chemistry and pharmacy, biology and agriculture, engineering, energy
and logistics, economy and finance, meteorology, manufacturing and
cybersecurity [68, 69].

##  II The Dawn of Quantum Software Engineering

Despite the great and fast progress being made in Quantum Computing, current
quantum computers cannot scale beyond dimensions of a few tens (or in the best
cases hundreds) of qubits. At the same time, quantum devices are still very
sensitive to external interference (noise), which can easily disrupt an
ongoing computation. Due to such limitation, current quantum computers are
usually referred to as Noisy Intermediate-Scale Quantum (NISQ) devices [70],
highlighting their capacity to execute only Quantum programs featuring a small
number of qubits and consecutive steps [71, 72, 73].

However, this is not the first time in history that computer scientists have
had to face such limitations on computing devices. Several authors, indeed,
compare the current quantum computing landscape to that of classical computing
during the 60s and that a similar development should be followed [74, 75, 76].

In such a roadmap, Quantum Software Engineering has a primary role ‘to exploit
the full potential of commercial quantum computer hardware, once it arrives’
[77]. Quantum Software Engineering will be, indeed, also necessary to define
the best quantum software development and application management lifecycles.
They will enable to coherently employ and operate the increasing amount of
quantum methodologies and tools, proposed to solve problems nowadays present
in all the development and management phases [78, 79]. To this aim, there are
already emerging several full ecosystems to exploit such methodologies and
tools (e.g., [80, 81]), and the compelling need for a structured discipline of
Quantum Software Engineering is discussed by numerous authors (e.g., [82, 83,
84])

Jianjun Zhao defines in [78] the term ‘Quantum Software Engineering’ as

> ‘The use of sound engineering principles for the development, operation, and
> maintenance of quantum software and the associated document to obtain
> economically quantum software that is reliable and works efficiently on
> quantum computers’

Highlighting the importance of applying ‘sound engineering principles’ to the
quantum software lifecycle, that its management must be ‘economically’
affordable, and that the resulting software must be ‘reliable’ and must work
‘efficiently’ on quantum computers.

Some authors claim that Quantum Computing will lead to a new ‘Golden Age’ of
Software Engineering. They believe that ‘Software Engineering has built up a
broad knowledge base, and has learnt many lessons that should be applied to
the production of quantum software. The new quantum software engineering field
needs to be considered as the application or adaptation of the well-known
methods, techniques, and practices of software engineering. At the same time,
however, new methods and techniques will be defined specifically for quantum
software production’ [85].

These strong beliefs gather a large support all around the globe. As an
example, ‘The Talavera Manifesto for Quantum Software Engineering and
Programming’ [76], a document that summarises the principles and commitments
for Quantum Software Engineering, and that is considered a milestone in the
(even if brief) history of QSE [86], has already been signed by more than 200
researchers and practitioners from more than 20
countries111111https://www.aquantum.es/endorsers/.

##  III Quantum Software Engineering

The history of Quantum Software Engineering (QSE) is pretty recent. The term
‘Quantum Software Engineering’ first appeared in 2002 in the ‘Grand Challenge
for Computing Research’ [77] by John Clark and Susan Stepney, in which the
authors identify four different potential research lines, viz., Foundations,
Languages and Compilers, Methods and Tools and, Novel Quantum Possibilities.

As for the foundational aspects, the authors highlighted the need to further
develop and investigate the concepts of Universal Turing Machine and Quantum
Algorithmic Complexity as well as new models of quantum computations above the
level of unitary matrices and gates. Strictly linked with the new quantum
computational models the authors discussed the need to determine new
fundamental building blocks of quantum programming for assembly, high-level
and specification languages, and the corresponding quantum compilers. Such
progress should be accompanied by new architectures and debugging and testing
techniques, as well as more powerful simulators and visualisation techniques.
Finally, the authors recommended investigating the effects of the pure random
generation and entanglement capabilities offered by quantum computers and how
they can help to produce new algorithms and protocols.

Moving forward, in 2020, ‘The Talavera Manifesto for Quantum Software
Engineering and Programming’ [76] was presented as the resulting effort of
academia and industry practitioners who joined at the first International
Workshop on QuANtum SoftWare Engineering & pRogramming. The Manifesto
discusses how QSE should:

  1. 1.

be agnostic regarding quantum programming languages and technologies,

  2. 2.

embrace the coexistence of classical and quantum computing,

  3. 3.

support the management of quantum software development projects,

  4. 4.

consider the evolution of quantum software,

  5. 5.

aim at delivering quantum programs with desirable zero defects,

  6. 6.

promote quantum software reuse,

  7. 7.

address security and privacy by design, and

  8. 8.

cover the governance and management of software.

The Manifesto also links Quantum Software Engineering with classical Software
Engineering suggesting how a quantum approach to Software Engineering should
‘take care of producing quantum software by applying knowledge and lessons
learned from the software engineering field. This implies applying or adapting
the existing software engineering processes, methods, techniques, practices
and principles for the development of quantum software (or it may imply
creating new ones)’.

The same approach is also suggested in [75]. The authors discuss that ‘the new
quantum software engineering field needs to be considered as the application
or adaptation of the well-known methods, techniques, and practices of software
engineering. Some techniques can be used just as they are in classical
computing. At the same time, however, new methods and techniques will be
defined specifically for quantum software production’.

Luis Barbosa, in his position paper [87], identifies four main issues to a
scientific rigorously Quantum Software Engineering discipline, viz.,
investigate appropriate semantic structures capable of managing classical
controls and quantum data, develop an algorithmic calculus for the systematic
derivation of quantum programs in a compositional way, seek a new family of
dynamic logics to support the formulation of contract for quantum programs and
their compositional verification and, finally, design a framework for
coordination of orchestrated quantum computation systems. In the same work,
Barbosa discusses also three research directions from a formal methods point
of view, namely, the study of quantum models, architectures and, properties
with the ultimate goal of developing a ‘a mathematically based approach, able
to conceptualise, and predict behaviour, and to provide a rich, formal
framework for specifying, developing and verifying quantum algorithms’.

In [83], the authors identify software design, software construction, software
testing, software maintenance, and software quality as the main SWEBOK
(Software Engineering Body of Knowledge) [88] areas that will be heavily
influenced by quantum computing, followed by software requirements, software
engineering process, software engineering models and methods, and computing
foundations. Furthermore, the authors discuss some promising research lines,
viz., design of quantum hybrid systems, quantum program testing, quality
assurance, and re-engineering and modernisation.

In [74], the authors link the current state of Quantum Computing with that of
classical computing in the late fifties and early sixties [89, 90], by
considering different challenges and problems that researchers had to face in
those periods and that today they reappeared in their quantum version, e.g.,
the hardware cost, their limited availability and limited power, the
difficulty of operating quantum computers, their sensitivity and small
reliability, the limited portability of the programs. On the basis of such
considerations and the computer science history [91], the authors warn that
‘all of the above [considerations] can lead one to assume that we are on the
verge of a potential Quantum Software Crisis. Software Engineering must pay
attention to these signals in order to anticipate it’. At the same time, they
believe that starting from this analogy and, ‘analyzing the advances and the
lessons learned in the field of Software Engineering in the last 60 years,
raises the directions that could help to develop the future Quantum Software
Engineering’. The authors outline also three possible directions for QSE,
viz., investigating new quantum software processes and methodologies, design
of new abstractions for quantum software, and development of quantum
structured programming.

One of the main comprehensive surveys on the field of QSE [78], was published
by Jianjun Zhao in 2020. The ‘quantum software lifecycle’ is a pivotal point
in Zhao’s work and after a careful discussion and analysis a first systemic,
sequential model is proposed. Zhao’s model is a five-step lifecycle
comprising, namely, requirements analysis, software design, implementation,
testing, and maintenance.

In the same year, Weder et al. proposed a quantum software lifecycle model too
[79]. Their proposal, differently from Zhao’s, starts by considering how to
separate a problem’s classical and quantum parts and is a ten steps process
designed for applications during the NISQ era and, thus, incorporates phases
such as data preparation, oracle expansion, and mitigation of readout-errors.
Other steps are related to hardware-independent and dependent optimisation and
the selection of a suitable quantum computer.

In [84], the authors present a five-step quantum development model, based on
their experiences and findings in the development of three Variational Quantum
Algorithms (VQA) [92] for two industrial use cases (i.e., route planning and
optimisation). The proposed phases are the following, problem definition,
quantum algorithm selection, implementation, fine-tuning, and postprocessing.
The authors also noticed a high quantity of (even difficult) design decisions
to be taken during each phase, most of them related to the problems induced by
NISQ devices. They also highlight the need for experimental approaches to
support the design decision process and underline the importance of Model-
driven Software Development [93] in quantum computing. In [94] too,
Gemeinhardt et al. support the study of Model-Driven Engineering for quantum
technologies, arguing its utility in easing the development of software
systems.

With the aim of understanding what are the challenges and opportunities of
quantum computing facing the software engineering community, El Aoun et al.
carried out an empirical study on Stack Exchange Forums and GitHub Issues to
investigate the QSE-related challenges perceived by developers [95]. They
discovered that some of the challenges faced by quantum developers are the
same present in classical software developments (e.g., dependency management).
Anyway, quantum development also presents quantum-specific challenges (e.g.,
the interpretation of quantum programs’ output). The authors also identify
different areas requiring attention (e.g., learning resources both on
practical and theoretical aspects of quantum computing, error management, and
production of tools to support the development).

With a similar approach, De Stefano et al. mined GitHub repositories employing
quantum framework to understand the most commonly used technologies and
interviewed the contributors of such repositories to survey their opinions on
the current adoption and challenges of quantum programming [96]. They found
out that quantum programming tools are mostly used for personal study purposes
and most GitHub contributors on quantum computing work in research and
framework repositories. They also discovered that most challenges are related
to the understanding of quantum programs, the complexities associated with
establishing hardware and software infrastructures, issues pertaining to
implementation and code quality, the difficult task of building a quantum
developer community, and the existing shortcomings in the realism of current
quantum applications. They conclude how at the date quantum programming
primarily serves didactic purposes or satisfies researchers’ curiosity in
experimenting with quantum technologies and that challenges are not only
related to quantum development but also socio-technical considerations.

Focusing on quantum tools, Serrano et al. reviewed main quantum software
components and platforms [97]. They discovered that most of the available
quantum tools lack standard classical features such as project support,
software governance, and a focus on software quality and evolution. Another
systematic survey on quantum tools, frameworks, and platforms is presented in
[98].

With a systematic study of broader scope, De Stefano et al. surveyed existing
literature on QSE [86]. They discovered that current QSE research ‘has
primarily focused on software testing with little attention given to other
topics, such as software engineering management’. Moreover, most papers
proposed solutions and techniques or reported empirical findings and
positions. They also propose to set the ‘official’ establishment of QSE in
2020 with the Talavera Manifesto, with first publications, however, dating
back to 2018.

In the realm of quantum software testing, researchers have grappled with the
unique challenges posed by the principles of quantum mechanics. As highlighted
by Miranskyy et al. [99, 100], the very act of observing a quantum computation
unavoidably alters its state, rendering traditional interactive debugging
impractical. Consequently, a shift towards methodologies such as black-box
testing or the judicious use of quantum simulators becomes imperative. Quantum
simulators offer the advantage of observing qubit states without perturbation,
allowing for more effective testing strategies.

Addressing these challenges, in [101] the authors delve into potential
approaches for quantum software testing. Their exploration encompasses
statistical techniques tailored to the stochastic nature of quantum physics.
Leveraging statistical proof rules [102] and assertions [103], they propose
strategies for both the verification and testing phases. In the pursuit of
verification, discussions revolve around quantum adaptations of Hoare logic
[104], a formal system for reasoning about the correctness of computer
programs. Additionally, the authors illustrate how the concept of quantum
reversibility, as elucidated by Patel et al. [105] and Zamani et al. [106],
can be harnessed for verification purposes, further enhancing the reliability
of quantum programs.

##  IV The Future of Quantum Software Engineering

The existing body of literature indicates a growing and pressing demand for
the creation of a novel Software Engineering paradigm tailored for Quantum
Computing. This need becomes even more pronounced as the quantity and quality
of quantum computers continue to advance. This approach should be adept at
addressing problems by either building upon and potentially enhancing
classical techniques and tools or by pioneering entirely new solutions, facing
challenges unique to the quantum domain. This new Quantum Software Engineering
must possess the capability to address the challenges that the next generation
of quantum developers will encounter. Notably, the upcoming cohort of quantum
developers will comprise individuals who are not solely specialists in the
field with extensive experience in quantum mechanics and computing. Thus, the
new Quantum Software Engineering proposal must address also such a
heterogeneous user base.

Numerous papers have explored intriguing and potentially transformative
avenues for future research in Quantum Software Engineering (QSE) [61, 74, 78,
86, 95, 96]. While these directions hold considerable merit and interest, we
have chosen not to reiterate them in this manuscript. Instead, we decided to
delve into uncharted territories, proposing research directions that we
anticipate harbouring significant potential yet remain, to the best of our
knowledge, barely addressed in the existing literature. Herein, we present
promising research avenues and challenges within QSE, anticipating their
escalating importance in the near future and envisaging their potential to
yield groundbreaking discoveries:

  1. 1.

Language abstractions. Developing Quantum algorithms remains a nuanced art
rather than a streamlined engineering process. Presently, quantum abstractions
mirror the early stages of classical computing, where each individual (qu)bit
and gate requires meticulous management. Crafting intricate quantum programs
thus poses formidable challenges. However, with the development of higher-
level language abstractions and foundational quantum primitives, developers
can potentially transcend the burdensome intricacies of low-level matrix
operations. This shift promises to bring quantum development closer to the
intuitive and efficient coding practices prevalent in modern classical
programming paradigms [107, 108, 109].

  2. 2.

Quantum software debugging and visualisation. Debugging and visualising
quantum software pose unique challenges due to the inherent nature of quantum
computation. Unlike classical computing, observing the state of a quantum
computation inevitably disrupts its execution, complicating the debugging
process on real quantum hardware. Fortunately, quantum simulators offer a
workaround, enabling observation of qubit states without perturbation. By
refining debugging techniques tailored to quantum environments, we can enhance
the quality and ease of developing quantum programs. Moreover, improving
visualisation techniques for quantum computation holds promise in enhancing
both comprehension and debugging capabilities. Clear visual representations of
quantum processes can provide invaluable insights into program behaviour and
facilitate the identification of errors. By investing in the advancement of
quantum software debugging and visualisation tools, we can significantly
accelerate progress in quantum computing [100, 110, 111].

  3. 3.

Distributed quantum computations. The current quantum computing landscape is
characterised by a significant diversity in qubit implementations and quantum
computer architectures, resulting in a broad spectrum of performance and
qualitative attributes. Presently, quantum computers are predominantly
perceived and utilised as individual monolithic entities. However, an
alternative approach could involve distributing quantum computations across
multiple quantum computers, capitalising on and leveraging the existing
heterogeneity rather than perceiving it as a limitation. This paradigm shift
opens doors to novel strategies in quantum computation. By harnessing the
diverse capabilities of various quantum computing platforms, we can envision a
distributed computing framework where tasks are intelligently allocated across
a network (either classical or quantum) of interconnected quantum devices.
This distributed approach not only mitigates the limitations imposed by
individual quantum computers but also unlocks synergistic potentials arising
from their collective strengths. Embracing this heterogeneity fosters a more
robust and scalable quantum computing ecosystem, paving the way for
collaborative problem-solving on a scale previously unattainable [112, 113,
114].

## References

  * [1] R. P. Feynman, “Simulating physics with computers,” _International Journal of Theoretical Physics_ , vol. 21, pp. 467–488, 1982.
  * [2] Y. Manin, “Computable and uncomputable,” _Sovetskoye Radio, Moscow_ , vol. 128, p. 28, 1980.
  * [3] P. Benioff, “The computer as a physical system: A microscopic quantum mechanical hamiltonian model of computers as represented by turing machines,” _Journal of statistical physics_ , vol. 22, pp. 563–591, 1980.
  * [4] ——, “Quantum mechanical hamiltonian models of turing machines,” _Journal of Statistical Physics_ , vol. 29, pp. 515–546, 1982.
  * [5] R. P. Feynman, “Quantum mechanical computers,” _Optics news_ , vol. 11, no. 2, pp. 11–20, 1985.
  * [6] M. Planck, “Ueber das gesetz der energieverteilung im normalspectrum,” _Annalen der Physik_ , vol. 309, no. 3, pp. 553–563, 1901.
  * [7] A. Einstein, “Über einen die erzeugung und verwandlung des lichtes betreffenden heuristischen gesichtspunkt,” _Annalen der Physik_ , vol. 322, no. 6, pp. 132–148, 1905.
  * [8] N. Bohr, “I. on the constitution of atoms and molecules,” _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , vol. 26, no. 151, pp. 1–25, 1913.
  * [9] W. K. Heisenberg, _Über quantentheoretische Umdeutung kinematischer und mechanischer Beziehungen._ , 1925, vol. 33, no. 1.
  * [10] E. Schrödinger, “Quantisierung als eigenwertproblem,” _Annalen der Physik_ , vol. 384, no. 4, pp. 361–376, 1926.
  * [11] M. Born, “Quantenmechanik der stoßvorgänge,” _Zeitschrift für physik_ , vol. 38, no. 11-12, pp. 803–827, 1926.
  * [12] P. A. M. Dirac, _The principles of quantum mechanics_ , 1981, no. 27.
  * [13] J. Von Neumann, _Mathematical foundations of quantum mechanics: New edition_ , 2018, vol. 53.
  * [14] W. Pauli, _General principles of quantum mechanics_ , 2012.
  * [15] D. Deutsch, “Quantum theory, the church–turing principle and the universal quantum computer,” _Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences_ , vol. 400, no. 1818, pp. 97–117, 1985.
  * [16] D. Deutsch and R. Jozsa, “Rapid solution of problems by quantum computation,” _Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences_ , vol. 439, no. 1907, pp. 553–558, 1992.
  * [17] E. Bernstein and U. Vazirani, “Quantum complexity theory,” in _Proceedings of the twenty-fifth annual ACM symposium on Theory of computing_ , 1993, pp. 11–20.
  * [18] H. J. Nussbaumer, _The fast Fourier transform_ , 1982.
  * [19] D. R. Simon, “On the power of quantum computation,” in _Proceedings 35th Annual Symposium on Foundations of Computer Science_ , 1994, pp. 116–123.
  * [20] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th annual symposium on foundations of computer science_ , 1994, pp. 124–134.
  * [21] K. S. McCurley, “The discrete logarithm problem,” in _Proc. of Symp. in Applied Math_ , vol. 42, 1990, pp. 49–74.
  * [22] J. Buchmann, _Introduction to cryptography_ , 2004, vol. 335.
  * [23] S. Lloyd, “Universal quantum simulators,” _Science_ , vol. 273, no. 5278, pp. 1073–1078, 1996.
  * [24] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ , 1996, pp. 212–219.
  * [25] S. Lloyd, “A potentially realizable quantum computer,” _Science_ , vol. 261, no. 5128, pp. 1569–1571, 1993.
  * [26] J. I. Cirac and P. Zoller, “Quantum computations with cold trapped ions,” _Physical review letters_ , vol. 74, no. 20, p. 4091, 1995.
  * [27] D. P. DiVincenzo, “Topics in quantum computers,” in _Mesoscopic electron transport_ , 1997, pp. 657–677.
  * [28] Y. Nakamura, Y. A. Pashkin, and J. Tsai, “Coherent control of macroscopic quantum states in a single-cooper-pair box,” _nature_ , vol. 398, no. 6730, pp. 786–788, 1999.
  * [29] Y. Nakamura, Y. A. Pashkin, and J. S. Tsai, “Rabi oscillations in a josephson-junction charge two-level system,” _Physical Review Letters_ , vol. 87, no. 24, p. 246601, 2001.
  * [30] R. Landauer, “Is quantum mechanics useful?” _Philosophical Transactions of the Royal Society of London. Series A: Physical and Engineering Sciences_ , vol. 353, no. 1703, pp. 367–376, 1995.
  * [31] W. G. Unruh, “Maintaining coherence in quantum computers,” _Physical Review A_ , vol. 51, no. 2, p. 992, 1995.
  * [32] S. Haroche and J.-M. Raimond, “Quantum computing: dream or nightmare?” _Physics Today_ , vol. 49, no. 8, pp. 51–52, 1996.
  * [33] P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” _Physical review A_ , vol. 52, no. 4, p. R2493, 1995.
  * [34] ——, “Fault-tolerant quantum computation,” in _Proceedings of 37th conference on foundations of computer science_ , 1996, pp. 56–65.
  * [35] D. Aharonov and M. Ben-Or, “Fault-tolerant quantum computation with constant error,” in _Proceedings of the twenty-ninth annual ACM symposium on Theory of computing_ , 1997, pp. 176–188.
  * [36] E. Knill, R. Laflamme, and W. H. Zurek, “Resilient quantum computation,” _Science_ , vol. 279, no. 5349, pp. 342–345, 1998.
  * [37] A. Y. Kitaev, “Quantum computations: algorithms and error correction,” _Russian Mathematical Surveys_ , vol. 52, no. 6, p. 1191, 1997.
  * [38] M. A. Nielsen and I. L. Chuang, _Quantum Computation and Quantum Information_ , 2012.
  * [39] J. Preskill, “Fault-tolerant quantum computation,” in _Introduction to quantum computation and information_ , 1998, pp. 213–269.
  * [40] ——, “Quantum computing 40 years later,” in _Feynman Lectures on Computation_ , 2023, pp. 193–244.
  * [41] Z. Merali _et al._ , “First sale for quantum computing,” _Nature_ , vol. 474, no. 7349, p. 18, 2011.
  * [42] P. Hauke _et al._ , “Perspectives of quantum annealing: Methods and implementations,” _Rep. Prog. Phys._ , vol. 83, no. 5, p. 054401, 2020.
  * [43] M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, “Quantum annealing with manufactured spins,” _Nature_ , vol. 473, no. 7346, pp. 194–198, 2011.
  * [44] K. Michielsen _et al._ , “Benchmarking gate-based quantum computers,” _Comput. Phys. Commun._ , vol. 220, pp. 44–55, 2017.
  * [45] A. C. Santos, “The ibm quantum computer and the ibm quantum experience,” 2016.
  * [46] D. Alsina and J. I. Latorre, “Experimental test of mermin inequalities on a five-qubit quantum computer,” _Physical Review A_ , vol. 94, no. 1, 2016.
  * [47] P. Ball, “First commercial ion-based quantum computer built,” _Physics World_ , vol. 32, no. 2, pp. 5–5, 2019.
  * [48] J. Preskill, “Quantum computing and the entanglement frontier,” 2012.
  * [49] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, “Quantum supremacy using a programmable superconducting processor,” _Nature_ , vol. 574, no. 7779, pp. 505–510, 2019.
  * [50] Y. A. Liu, X. L. Liu, F. N. Li, H. Fu, Y. Yang, J. Song, P. Zhao, Z. Wang, D. Peng, H. Chen, C. Guo, H. Huang, W. Wu, and D. Chen, “Closing the ‘quantum supremacy’ gap,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , 2021.
  * [51] J. F. F. Bulmer, B. A. Bell, R. S. Chadwick, A. E. Jones, D. Moise, A. Rigazzi, J. Thorbecke, U.-U. Haus, T. V. Vaerenbergh, R. B. Patel, I. A. Walmsley, and A. Laing, “The boundary for quantum advantage in gaussian boson sampling,” _Science Advances_ , vol. 8, no. 4, Jan. 2022.
  * [52] K. McCormick, “Race not over between classical and quantum computers,” _Physics_ , vol. 15, 2022.
  * [53] F. Pan, K. Chen, and P. Zhang, “Solving the sampling problem of the sycamore quantum circuits,” _Physical Review Letters_ , vol. 129, no. 9, 2022.
  * [54] Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. van den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zaletel, K. Temme, and A. Kandala, “Evidence for the utility of quantum computing before fault tolerance,” _Nature_ , vol. 618, no. 7965, pp. 500–505, 2023.
  * [55] J. Tindall, M. Fishman, M. Stoudenmire, and D. Sels, “Efficient tensor network simulation of ibm’s eagle kicked ising experiment,” 2023.
  * [56] T. Begušić and G. K.-L. Chan, “Fast classical simulation of evidence for the utility of quantum computing before fault tolerance,” 2023.
  * [57] K. Kechedzhi, S. V. Isakov, S. Mandrà, B. Villalonga, X. Mi, S. Boixo, and V. Smelyanskiy, “Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments,” 2023.
  * [58] S. Anand, K. Temme, A. Kandala, and M. Zaletel, “Classical benchmarking of zero noise extrapolation beyond the exactly-verifiable regime,” 2023.
  * [59] W. Knight, “Serious quantum computers are finally here. what are we going to do with them,” _MIT Technology Review. Retrieved on October_ , vol. 30, p. 2018, 2018.
  * [60] I. I. for Business Value, _The Quantum Decade: A Playbook for Achieving Awareness, Readiness, and Advantage_ , 2021.
  * [61] A. Carleton, E. Harper, J. E. Robert, M. H. Klein, D. De Niz, E. Desautels, J. B. Goodenough, C. Holland, I. Ozkaya, D. Schmidt _et al._ , “Architecting the future of software engineering: A national agenda for software engineering research and development,” _Softw. Eng. Inst., Pittsburgh, PA, USA, AD1152714_ , 2021.
  * [62] A. J. Daley, I. Bloch, C. Kokail, S. Flannigan, N. Pearson, M. Troyer, and P. Zoller, “Practical quantum advantage in quantum simulation,” _Nature_ , vol. 607, no. 7920, pp. 667–676, 2022.
  * [63] L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins _et al._ , “Quantum computational advantage with a programmable photonic processor,” _Nature_ , vol. 606, no. 7912, pp. 75–81, 2022.
  * [64] H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu _et al._ , “Quantum computational advantage using photons,” _Science_ , vol. 370, no. 6523, pp. 1460–1463, 2020.
  * [65] Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan _et al._ , “Strong quantum computational advantage using a superconducting quantum processor,” _Physical review letters_ , vol. 127, no. 18, p. 180501, 2021.
  * [66] D. R. Simon, “On the power of quantum computation,” _SIAM Journal on Computing_ , vol. 26, no. 5, pp. 1474–1483, 1997.
  * [67] M. A. Lopez and M. Da Silva, “Quantum technologies digital transformation, social impact, and cross-sector disruption,” _Interamerican Development Bank_ , 2019.
  * [68] A. Bayerstadler, G. Becquin, J. Binder, T. Botter, H. Ehm, T. Ehmer, M. Erdmann, N. Gaus, P. Harbach, M. Hess _et al._ , “Industry quantum computing applications,” _EPJ Quantum Technology_ , vol. 8, no. 1, p. 25, 2021.
  * [69] F. Bova, A. Goldfarb, and R. G. Melko, “Commercial applications of quantum computing,” _EPJ quantum technology_ , vol. 8, no. 1, p. 2, 2021.
  * [70] J. Preskill, “Quantum computing in the nisq era and beyond,” _Quantum_ , vol. 2, p. 79, 2018.
  * [71] K. Bharti _et al._ , “Noisy intermediate-scale quantum algorithms,” _Rev. Mod. Phys._ , vol. 94, no. 1, 2022.
  * [72] F. Leymann and J. Barzen, “The bitter truth about gate-based quantum algorithms in the nisq era,” _Quantum Science and Technology_ , vol. 5, no. 4, p. 044007, 2020.
  * [73] F. G. Gemeinhardt, R. Wille, and M. Wimmer, “Quantum k-community detection: algorithm proposals and cross-architectural evaluation,” _Quantum Information Processing_ , vol. 20, no. 9, p. 302, 2021.
  * [74] E. Moguel, J. Berrocal, J. García-Alonso, and J. M. Murillo, “A roadmap for quantum software engineering: Applying the lessons learned from the classics.” in _Q-SET@ QCE_ , 2020, pp. 5–13.
  * [75] M. A. Serrano, R. Perez-Castillo, and M. Piattini, _Quantum Software Engineering_ , 2022.
  * [76] M. Piattini, G. Peterssen, R. Pérez-Castillo, J. L. Hevia, M. A. Serrano, G. Hernández, I. G. R. de Guzmán, C. A. Paradela, M. Polo, E. Murina _et al._ , “The talavera manifesto for quantum software engineering and programming.” in _QANSWER_ , 2020, pp. 1–5.
  * [77] J. Clark and S. Stepney, “Quantum software engineering,” in _Workshop on Grand Challenges for Computing Research, e-Science Institute, Edinburgh_ , 2002.
  * [78] J. Zhao, “Quantum software engineering: Landscapes and horizons,” _arXiv preprint arXiv:2007.07047_ , 2020.
  * [79] B. Weder, J. Barzen, F. Leymann, M. Salm, and D. Vietz, “The quantum software lifecycle,” in _Proceedings of the 1st ACM SIGSOFT International Workshop on Architectures and Paradigms for Engineering Quantum Software_ , 2020, pp. 2–9.
  * [80] J. L. Hevia, G. Peterssen, and M. Piattini, “Quantumpath: A quantum software development platform,” _Software: Practice and Experience_ , vol. 52, no. 6, pp. 1517–1530, 2022.
  * [81] M. Beisel, J. Barzen, S. Garhofer, F. Leymann, F. Truger, B. Weder, and V. Yussupov, “Quokka: a service ecosystem for workflow-based execution of variational quantum algorithms,” in _International Conference on Service-Oriented Computing_ , 2022, pp. 369–373.
  * [82] J. Barzen, F. Leymann, S. Feld, and M. Wimmer, “2nd workshop on quantum software architecture (qsa),” in _2022 IEEE 19th International Conference on Software Architecture Companion, ICSA-C 2022_ , 2022.
  * [83] M. Piattini, M. Serrano, R. Perez-Castillo, G. Petersen, and J. L. Hevia, “Toward a quantum software engineering,” _IT Professional_ , vol. 23, no. 1, pp. 62–66, 2021.
  * [84] M. Scheerer, J. Klamroth, S. Garhofer, F. Knäble, and O. Denninger, “Experiences in quantum software engineering,” in _2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)_ , 2023, pp. 552–559.
  * [85] M. Piattini, G. Peterssen, and R. Pérez-Castillo, “Quantum computing: A new software engineering golden age,” _ACM SIGSOFT Software Engineering Notes_ , vol. 45, no. 3, pp. 12–14, 2021.
  * [86] M. De Stefano, F. Pecorelli, D. Di Nucci, F. Palomba, and A. De Lucia, “The quantum frontier of software engineering: A systematic mapping study,” _arXiv preprint arXiv:2305.19683_ , 2023.
  * [87] L. S. Barbosa, “Software engineering for’quantum advantage’,” in _Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops_ , 2020, pp. 427–429.
  * [88] P. Bourque and R. E. Fairley, Eds., _SWEBOK: Guide to the Software Engineering Body of Knowledge_ , version 3.0 ed. IEEE Computer Society, 2014.
  * [89] E. W. Dijkstra, “The humble programmer,” _Commun. ACM_ , vol. 15, no. 10, p. 859–866, 10 1972.
  * [90] G. L. Steele, “Macaroni is better than spaghetti,” in _Proceedings of the 1977 Symposium on Artificial Intelligence and Programming Languages_ , 1977, p. 60–66.
  * [91] M. S. Mahoney, “The history of computing in the history of technology,” _Annals of the History of Computing_ , vol. 10, no. 2, pp. 113–125, 1988.
  * [92] M. Cerezo _et al._ , “Variational quantum algorithms,” _Nat. Rev. Phys._ , vol. 3, no. 9, 2021.
  * [93] M. Brambilla, J. Cabot, and M. Wimmer, _Model-driven software engineering in practice_ , 2017.
  * [94] F. Gemeinhardt, A. Garmendia, and M. Wimmer, “Towards model-driven quantum software engineering,” in _2nd International Workshop on Quantum Software Engineering (Q-SE)_ , 2021, pp. 13–15.
  * [95] M. R. E. aoun, H. Li, F. Khomh, and M. Openja, “Understanding quantum software engineering challenges an empirical study on stack exchange forums and github issues,” in _IEEE International Conference on Software Maintenance and Evolution, ICSME 2021, Luxembourg, September 27 - October 1, 2021_ , 2021, pp. 343–354.
  * [96] M. De Stefano, F. Pecorelli, D. Di Nucci, F. Palomba, and A. De Lucia, “Software engineering for quantum programming: How far are we?” _Journal of Systems and Software_ , vol. 190, p. 111326, 2022.
  * [97] M. A. Serrano, J. A. Cruz-Lemus, R. Perez-Castillo, and M. Piattini, “Quantum software components and platforms: Overview and quality assessment,” _ACM Computing Surveys_ , vol. 55, no. 8, pp. 1–31, 2022.
  * [98] P. B. Upama, M. J. H. Faruk, M. Nazim, M. Masum, H. Shahriar, G. Uddin, S. Barzanjeh, S. I. Ahamed, and A. Rahman, “Evolution of quantum computing: A systematic survey on the use of quantum computing tools,” in _2022 IEEE 46th Annual Computers, Software, and Applications Conference (COMPSAC)_ , 2022, pp. 520–529.
  * [99] A. Miranskyy and L. Zhang, “On testing quantum programs,” in _2019 IEEE/ACM 41st International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER)_. IEEE, 2019, pp. 57–60.
  * [100] A. Miranskyy, L. Zhang, and J. Doliskani, “On testing and debugging quantum software,” _arXiv preprint arXiv:2103.09172_ , 2021.
  * [101] A. García de la Barrera, I. García-Rodríguez de Guzmán, M. Polo, and M. Piattini, “Quantum software testing: State of the art,” _Journal of Software: Evolution and Process_ , vol. 35, no. 4, p. e2419, 2023.
  * [102] Y. Feng, R. Duan, Z. Ji, and M. Ying, “Proof rules for the correctness of quantum programs,” _Theoretical Computer Science_ , vol. 386, no. 1-2, pp. 151–166, 2007.
  * [103] H. Yang, Z. Luan, Q. Chen, M. Riaz, L. Tang, J. Mars, Z. Li, L. Liu, S. Yin, Y. Wang _et al._ , “Proceedings-international symposium on computer architecture,” 2017.
  * [104] A. Miranskyy, L. Zhang, and J. Doliskani, “Is your quantum program bug-free?” _arXiv preprint arXiv:2001.10870_ , 2020.
  * [105] K. N. Patel, J. P. Hayes, and I. L. Markov, “Fault testing for reversible circuits,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 23, no. 8, pp. 1220–1230, 2004.
  * [106] M. Zamani, M. B. Tahoori, and K. Chakrabarty, “Ping-pong test: Compact test vector generation for reversible circuits,” in _2012 IEEE 30th VLSI Test Symposium (VTS)_. IEEE, 2012, pp. 164–169.
  * [107] F. T. Chong, D. Franklin, and M. Martonosi, “Programming languages and compiler design for realistic quantum hardware,” _Nature_ , vol. 549, no. 7671, pp. 180–187, 2017.
  * [108] H. Fürntratt, P. Schnabl, F. Krebs, R. Unterberger, and H. Zeiner, “Towards higher abstraction levels in quantum computing,” in _International Conference on Service-Oriented Computing_. Springer, 2023, pp. 162–173.
  * [109] B. Bichsel, M. Baader, T. Gehr, and M. Vechev, “Silq: A high-level quantum language with safe uncomputation and intuitive semantics,” in _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_ , 2020, pp. 286–300.
  * [110] O. Di Matteo, “On the need for effective tools for debugging quantum programs,” _arXiv preprint arXiv:2402.09547_ , 2024.
  * [111] M. Sasakura and K. Iwata, “Potential of visualization to explain quantum algorithms,” in _2023 27th International Conference Information Visualisation (IV)_. IEEE, 2023, pp. 426–428.
  * [112] D. Cuomo, M. Caleffi, and A. S. Cacciapuoti, “Towards a distributed quantum computing ecosystem,” _IET Quantum Communication_ , vol. 1, no. 1, pp. 3–8, 2020.
  * [113] G. Bisicchia, J. García-Alonso, J. M. Murillo, and A. Brogi, “Dispatching shots among multiple quantum computers: An architectural proposal,” in _2023 IEEE International Conference on Quantum Computing and Engineering (QCE)_ , vol. 2. IEEE, 2023, pp. 195–198.
  * [114] ——, “Distributing quantum computations, by shots,” in _International Conference on Service-Oriented Computing_. Springer, 2023, pp. 363–377.


# Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized
KL information

Gholamali Aminian  Yuheng Bu  Laura Toni  Miguel R. D. Rodrigues  Gregory
Wornell

###### Abstract

Bounding the generalization error of a supervised learning algorithm is one of
the most important problems in learning theory, and various approaches have
been developed. However, existing bounds are often loose and lack of
guarantees. As a result, they may fail to characterize the exact
generalization ability of a learning algorithm. Our main contribution is an
exact characterization of the expected generalization error of the well-known
Gibbs algorithm in terms of symmetrized KL information between the input
training samples and the output hypothesis. Such a result can be applied to
tighten existing expected generalization error bound. Our analysis provides
more insight on the fundamental role the symmetrized KL information plays in
controlling the generalization error of the Gibbs algorithm.

Machine Learning, ICML

##  1 Introduction

Evaluating the generalization error of a learning algorithm is one of the most
important challenges in statistical learning theory. Various approaches have
been developed (Rodrigues & Eldar, 2021), including VC dimension-based bounds
(Vapnik, 1999), algorithmic stability-based bounds (Bousquet & Elisseeff,
2002), algorithmic robustness-based bounds (Xu & Mannor, 2012), PAC-Bayesian
bounds (McAllester, 2003), and information-theoretic bounds (Xu & Raginsky,
2017).

However, upper bounds on generalization error may not entirely capture the
generalization ability of a learning algorithm. One apparent reason is the
tightness issue, some upper bounds (Anthony & Bartlett, 2009) can be far away
from the true generalization error or even vacuous when evaluated in practice.
More importantly, existing upper bounds do not fully characterize all the
aspects that could influence the generalization error of a supervised learning
problem. For example, VC dimension-based bounds depend only on the hypothesis
class, and algorithmic stability-based bounds only exploit the properties of
the learning algorithm. As a consequence, both methods fail to capture the
fact that generalization behavior depends strongly on the interplay between
the hypothesis class, learning algorithm, and the underlying data-generating
distribution, as shown in (Zhang et al., 2016). This paper overcomes the above
limitations by deriving an exact characterization of the generalization error
for a specific supervised learning algorithm, namely the Gibbs algorithm.

###  1.1 Problem Formulation

Let $S=\\{Z_{i}\\}_{i=1}^{n}$ be the training set, where each $Z_{i}$ is
defined on the same alphabet $\mathcal{Z}$. Note that $Z_{i}$ is not required
to be i.i.d generated from the same data-generating distribution $P_{Z}$, and
we denote the joint distribution of all the training samples as $P_{S}$. We
denote the hypotheses by $w\in\mathcal{W}$, where $\mathcal{W}$ is a
hypothesis class. The performance of the hypothesis is measured by a non-
negative loss function
$\ell:\mathcal{W}\times\mathcal{Z}\to\mathbb{R}_{0}^{+}$, and we can define
the empirical risk and the population risk associated with a given hypothesis
$w$ as $L_{E}(w,s)\triangleq\frac{1}{n}\sum_{i=1}^{n}\ell(w,z_{i})$ and
$L_{P}(w,P_{S})\triangleq\mathbb{E}_{P_{S}}[L_{E}(w,S)],$ respectively.

A learning algorithm can be modeled as a randomized mapping from the training
set $S$ onto an hypothesis $W\in\mathcal{W}$ according to the conditional
distribution $P_{W|S}$. Thus, the expected generalization error that
quantifies the degree of over-fitting can be written as

$\overline{\text{gen}}(P_{W|S},P_{S})\triangleq\mathbb{E}_{P_{W,S}}[L_{P}(W,P_{S})-L_{E}(W,S)],$
(1)

where the expectation is taken over the joint distribution
$P_{W,S}=P_{W|S}\otimes P_{S}$.

The $(\alpha,\pi(w),f(w,s))$-Gibbs distribution, which was first investigated
by (Gibbs, 1902), is defined as:

$P_{{W}|S}^{\alpha}(w|s)\triangleq\frac{\pi({w})e^{-\alpha
f(w,s)}}{V(s,\alpha)},\quad\alpha\geq 0,$ (2)

where $\alpha$ is the inverse temperature, $\pi(w)$ is an arbitrary prior
distribution of $W$, $f(w,s)$ is energy function, and
$V(s,\alpha)\triangleq\int\pi(w)e^{-\alpha f(w,s)}dw$ is the partition
function.

If $P$ and $Q$ are probability measures over the space $\mathcal{X}$, and $P$
is absolutely continuous with respect to $Q$, the Kullback-Leibler (KL)
divergence between $P$ and $Q$ is given by
$D(P\|Q)\triangleq\int_{\mathcal{X}}\log\left(\frac{dP}{dQ}\right)dP$. If $Q$
is also absolutely continuous with respect to $P$, the symmetrized KL
divergence (a.k.a. Jeffrey’s divergence (Jeffreys, 1946)) is

$D_{\mathrm{SKL}}(P\|Q)\triangleq D(P\|Q)+D(Q\|P).$ (3)

The mutual information between two random variables $X$ and $Y$ is defined as
the KL divergence between the joint distribution and product-of-marginal
distribution $I(X;Y)\triangleq D(P_{X,Y}\|P_{X}\otimes P_{Y})$, or
equivalently, the conditional KL divergence between $P_{Y|X}$ and $P_{Y}$
averaged over $P_{X}$,
$D(P_{Y|X}\|P_{Y}|P_{X})\triangleq\int_{\mathcal{X}}D(P_{Y|X=x}\|P_{Y})dP_{X}(x)$.
By swapping the role of $P_{X,Y}$ and $P_{X}\otimes P_{Y}$ in mutual
information, we get the lautum information introduced by (Palomar & Verdú,
2008), $L(X;Y)\triangleq D(P_{X}\otimes P_{Y}\|P_{X,Y})$. Finally, the
symmetrized KL information between $X$ and $Y$ is given by (Aminian et al.,
2015):

$I_{\mathrm{SKL}}(X;Y)\triangleq I(X;Y)+L(X;Y).$ (4)

Throughout the paper, upper-case letters denote random variables, lower-case
letters denote the realizations of random variables, and calligraphic letters
denote sets. All the logarithms are the natural ones, and all the information
measure units are nats. $\mathcal{N}(\mu,\Sigma)$ denotes a Gaussian
distribution with mean $\mu$ and covariance matrix $\Sigma$.

###  1.2 Contributions

The core contribution of this paper (see Theorem 1) is an _exact_
characterization of the expected generalization error for the Gibbs algorithm
in terms of symmetrized KL information between the input training samples $S$
and the output hypothesis $W$, as follows:

$\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})=\frac{I_{\mathrm{SKL}}(W;S)}{\alpha}.$

This result highlights the fundamental role of such an information quantity in
learning theory that does not appear to have been recognized before. We also
discuss some general properties of the symmetrized KL information, which could
be used to prove the non-negativity and concavity of the expected
generalization error for the Gibbs algorithm.

Building upon this result, we further expand our contributions by tightening
existing expected generalization error for Gibbs algorithm under i.i.d and
sub-Gaussian assumptions by combining our symmetrized KL information
characterization with existing bounding techniques.

###  1.3 Motivations for Gibbs Algorithm

As we discuss below, the choice of the Gibbs algorithm is not arbitrary since
it arises naturally in many different applications and is sufficiently general
to model many learning algorithms used in practice:

Empirical Risk Minimization: The $(\alpha,\pi(w),L_{E}(w,s))$-Gibbs algorithm
can be viewed as a randomized version of the empirical risk minimization (ERM)
algorithm if we specify the energy function $f(w,s)=L_{E}(w,s)$. As the
inverse temperature $\alpha\to\infty$, the prior distribution $\pi(w)$ becomes
negligible, and the Gibbs algorithm converges to the standard ERM algorithm.

Information Risk Minimization: The $(\alpha,\pi(w),L_{E}(w,s))$-Gibbs
algorithm is the solution to the regularized ERM problem by considering
conditional KL-divergence $D(P_{W|S}\|\pi(W)|P_{S})$, as a regularizer to
penalize over-fitting in the information risk minimization framework (Xu &
Raginsky, 2017; Zhang, 2006; Zhang et al., 2006).

SGLD Algorithm: The Stochastic Gradient Langevin Dynamics (SGLD) can be viewed
as the discrete version of the continuous-time Langevin diffusion. In
(Raginsky et al., 2017), it is proved that under some conditions on loss
function, the learning algorithm induced by SGLD algorithm is close to
$(\alpha,\pi(W_{0}),L_{E}(w_{k},s))$-Gibbs distribution in 2-Wasserstein
distance for sufficiently large iterations, where $\pi(W_{0})$ is the
distribution over hypothesis in the first step. Under some conditions on the
loss function $\ell(w,z)$, (Chiang et al., 1987; Markowich & Villani, 2000)
shows that in the continuous-time Langevin diffusion, the stationary
distribution of hypothesis $W$ is the Gibbs distribution.

###  1.4 Other Related Works

Information-theoretic generalization error bounds: Recently, (Russo & Zou,
2019; Xu & Raginsky, 2017) proposed to use the mutual information between the
input training set and the output hypothesis to upper bound the expected
generalization error. However, those bounds are known not to be tight, and
multiple approaches have been proposed to tighten the mutual information-based
bound. (Bu et al., 2020a) provides tighter bounds by considering the
individual sample mutual information, (Asadi et al., 2018; Asadi & Abbe, 2020)
propose using chaining mutual information, and (Steinke & Zakynthinou, 2020;
Hafez-Kolahi et al., 2020; Haghifam et al., 2020) advocate the conditioning
and processing techniques. Information-theoretic generalization error bounds
using other information quantities are also studied, such as, $f$-divergence
(Jiao et al., 2017), $\alpha$-Réyni divergence and maximal leakage (Issa et
al., 2019; Esposito et al., 2019), Jensen-Shannon divergence (Aminian et al.,
2020) and Wasserstein distance (Lopez & Jog, 2018; Wang et al., 2019;
Rodríguez-Gálvez et al., 2021). Using rate-distortion theory, (Masiha et al.,
2021; Bu et al., 2020a) provide information-theoretic generalization error
upper bounds for model misspecification and model compression.

Generalization error of Gibbs algorithm: Both information-theoretic and PAC-
Bayesian approaches have been used to bound the generalization error of the
Gibbs algorithm. An information-theoretic upper bound with a convergence rate
of $\mathcal{O}\left(1/n\right)$ is provided in (Raginsky et al., 2016) for
the Gibbs algorithm with bounded loss function, and PAC-Bayesian bounds using
a variational approximation of Gibbs posteriors are studied in (Alquier et
al., 2016). (Kuzborskij et al., 2019) focus on the excess risk of the Gibbs
algorithm and a similar generalization bound with rate of
$\mathcal{O}\left(1/n\right)$ is provided under sub-Gaussian assumption.
Although these bounds are tight in terms of the sample complexity $n$, they
become vacuous when the inverse temperature $\alpha\to\infty$, hence are
unable to capture the behaviour of the ERM algorithm.

Our work differs from this body of research in the sense that we provide an
exact characterization of the generalization error of the Gibbs algorithm in
terms of the symmetrized KL information. Our work also further leverages this
characterization to tighten existing expected generalization error bounds in
literature.

##  2 Generalization Error of Gibbs Algorithm

Our main result, which characterizes the exact expected generalization error
of the Gibbs algorithm with prior distribution $\pi(w)$, is as follows:

######  Theorem 1.

For the $(\alpha,\pi(w),L_{E}(w,s))$-Gibbs algorithm, the expected
generalization error is given by

$\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})=\frac{I_{\mathrm{SKL}}(W;S)}{\alpha}.$
(5)

###### Sketch of Proof:.

It can be shown that the symmetrized KL information can be written as

$I_{\mathrm{SKL}}(W;S)=\mathbb{E}_{P_{W,S}}[\log(P_{W|S}^{\alpha})]-\mathbb{E}_{P_{W}\otimes
P_{S}}[\log(P_{W|S}^{\alpha})].$ (6)

Just like the generalization error, the above expression is the difference
between the expectations of the same function evaluated under the joint
distribution and the product-of-marginal distribution. Note that $P_{W,S}$ and
$P_{W}\otimes P_{S}$ share the same marginal distribution, we have
$\mathbb{E}_{P_{W,S}}[\log\pi(W)]=\mathbb{E}_{P_{W}}[\log\pi(W)]$, and
$\mathbb{E}_{P_{W,S}}[\log V(S,\alpha)]=\mathbb{E}_{P_{S}}[\log V(S,\alpha)]$.
Then, combining (2) with (6) completes the proof. More details are provided in
Appendix A. ∎

To the best of our knowledge, this is the first exact characterization of the
expected generalization error for the Gibbs algorithm. Note that Theorem 1
only assumes that the loss function is non-negative, and it holds even for
non-i.i.d training samples.

###  2.1 General Properties

By Theorem 1, some basic properties of the expected generalization error,
including non-negativity and concavity can be proved directly from the
properties of symmetrized KL information.

The non-negativity of the expected generalization error, i.e.,
$\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})\geq 0$, follows by the non-
negativity of the symmetrized KL information. Note that the non-negativity
result obtained in (Kuzborskij et al., 2019) requires more technical
assumptions, including i.i.d samples and a sub-Gaussian loss function.

It is shown in (Aminian et al., 2015) that the symmetrized KL information
$I_{\mathrm{SKL}}(X;Y)$ is a concave function of $P_{X}$ for fixed $P_{Y|X}$,
and a convex function of $P_{Y|X}$ for fixed $P_{X}$. Thus, we have the
following corollary.

######  Corollary 1.

For a fixed $(\alpha,\pi(w),L_{E}(w,s))$-Gibbs algorithm $P_{{W}|S}^{\alpha}$,
the expected generalization error
$\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})$ is a concave function of
$P_{S}$.

The concavity of the generalization error for the Gibbs algorithm
$P_{{W}|S}^{\alpha}$ can be immediately used to explain the well-known fact
why training a model by mixing multiple datasets from different domains leads
to poor generalization. Suppose that the data-generating distribution is
domain-dependent, i.e., there exists a random variable $D$, such that
$D\leftrightarrow S\leftrightarrow W$ holds. Then,
$P_{S}=\mathbb{E}_{P_{D}}[P_{S|D}]$ can be viewed as the mixture of the data-
generating distribution across all domains. From Corollary 1 and Jensen’s
inequality, we have

$\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})\geq\mathbb{E}_{P_{D}}\big{[}\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S|D})\big{]},$
(7)

which shows that the generalization error of Gibbs algorithm achieved with the
mixture distribution $P_{S}$ is larger than the averaged generalization error
for each $P_{S|D}$.

###  2.2 Example: Mean Estimation

We now consider a simple learning problem, where the symmetrized KL
information can be computed exactly, to demonstrate the usefulness of Theorem
1. All details are provided in Appendix B.

Consider the problem of learning the mean ${\bm{\mu}}\in\mathbb{R}^{d}$ of a
random vector $Z$ using $n$ i.i.d training samples $S=\\{Z_{i}\\}_{i=1}^{n}$.
We assume that the covariance matrix of $Z$ satisfies
$\Sigma_{Z}=\sigma^{2}_{Z}I_{d}$ with unknown $\sigma^{2}_{Z}$. We adopt the
mean-squared loss $\ell({\bm{w}},{\bm{z}})=\|{\bm{z}}-{\bm{w}}\|_{2}^{2}$, and
assume a Gaussian prior for the mean
$\pi({\bm{w}})=\mathcal{N}({\bm{\mu}}_{0},\sigma^{2}_{0}I_{d})$. If we set
inverse-temperature $\alpha=\frac{n}{2\sigma^{2}}$, then the
$(\frac{n}{2\sigma^{2}},\mathcal{N}({\bm{\mu}}_{0},\sigma^{2}_{0}I_{d}),L_{E}({\bm{w}},s))$-Gibbs
algorithm is given by the following posterior distribution (Murphy, 2007),

$P_{W|S}^{\alpha}({\bm{w}}|Z^{n})\sim\mathcal{N}\Big{(}\frac{\sigma_{1}^{2}}{\sigma_{0}^{2}}{\bm{\mu}}_{0}+\frac{\sigma_{1}^{2}}{\sigma^{2}}\sum_{i=1}^{n}Z_{i},\sigma_{1}^{2}I_{d}\Big{)},$
(8)

with
$\sigma_{1}^{2}=\frac{\sigma_{0}^{2}\sigma^{2}}{n\sigma_{0}^{2}+\sigma^{2}}.$

Since $P_{W|S}^{\alpha}$ is Gaussian, the mutual information and lautum
information are given by

$\displaystyle I(S;W)$
$\displaystyle=\frac{nd\sigma_{0}^{2}\sigma_{Z}^{2}}{(n\sigma_{0}^{2}+\sigma^{2})\sigma^{2}}-D\big{(}P_{W}\|\mathcal{N}({\bm{\mu}}_{W},\sigma_{1}^{2}I_{d})\big{)},$
(9) $\displaystyle L(S;W)$
$\displaystyle=\frac{nd\sigma_{0}^{2}\sigma_{Z}^{2}}{(n\sigma_{0}^{2}+\sigma^{2})\sigma^{2}}+D\big{(}P_{W}\|\mathcal{N}({\bm{\mu}}_{W},\sigma_{1}^{2}I_{d})),$
(10)

with
${\bm{\mu}}_{W}=\frac{\sigma_{1}^{2}}{\sigma_{0}^{2}}{\bm{\mu}}_{0}+\frac{n\sigma_{1}^{2}}{\sigma^{2}}{\bm{\mu}}.$
As we can see from the above expressions, symmetrized KL information
$I_{\mathrm{SKL}}(W;S)$ is independent of the distribution of $P_{Z}$, as long
as $\Sigma_{Z}=\sigma^{2}_{Z}I_{d}$.

From Theorem 1, the generalization error of this algorithm can be computed
exactly as:

$\displaystyle\overline{\text{gen}}(P_{W|S}^{\alpha},P_{S})=\frac{I_{\mathrm{SKL}}(W;S)}{\alpha}$
$\displaystyle=\frac{2d\sigma_{0}^{2}\sigma_{Z}^{2}}{n(\sigma_{0}^{2}+\frac{1}{2\alpha})},$
(11)

which has the decay rate of $\mathcal{O}\left(1/n\right)$. As a comparison,
the individual sample mutual information (ISMI) bound from (Bu et al., 2020b),
which is shown to be tighter than the mutual information-based bound in (Xu &
Raginsky, 2017, Theorem 1), gives a sub-optimal bound with order
$\mathcal{O}\left(1/\sqrt{n}\right)$, as $n\to\infty$, (see Appendix B.3).

##  3 Tighter Expected Generalization Error Upper Bound

In this section, we show that by combining Theorem 1 with the information-
theoretic bound proposed in (Xu & Raginsky, 2017) under i.i.d and sub-Gaussian
assumptions, we can provide a tighter generalization error upper bound for
Gibbs algorithm. This bound quantifies how the generalization error of the
Gibbs algorithm depends on the number of samples $n$, and is useful when
directly evaluating the symmetrized KL information is hard.

######  Theorem 2.

(proved in Appendix C) Suppose that the training samples
$S=\\{Z_{i}\\}_{i=1}^{n}$ are i.i.d generated from the distribution $P_{Z}$,
and the non-negative loss function $\ell(w,Z)$ is $\sigma$-sub-Gaussian on the
left-tail 111A random variable $X$ is $\sigma$-sub-Gaussian if
$\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{\sigma^{2}\lambda^{2}}{2}$,
$\forall\lambda\in\mathbb{R}$, and $X$ is $\sigma$-sub-Gaussian on the left-
tail if
$\log\mathbb{E}[e^{\lambda(X-\mathbb{E}X)}]\leq\frac{\sigma^{2}\lambda^{2}}{2}$,
$\forall\lambda\leq 0$. under distribution $P_{Z}$ for all $w\in\mathcal{W}$.
If we further assume $C_{E}\leq\frac{L(W;S)}{I(W;S)}$ for some $C_{E}\geq 0$,
then for the $(\alpha,\pi(w),L_{E}(w,s))$-Gibbs algorithm, we have

$0\leq\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})\leq\frac{2\sigma^{2}\alpha}{(1+C_{E})n}.$
(12)

Theorem 2 establishes the convergence rate $\mathcal{O}(1/n)$ of the
generalization error of Gibbs algorithm with i.i.d training samples, and
suggests that a smaller inverse temperature $\alpha$ leads to a tighter upper
bound. Note that all the $\sigma$-sub-Gaussian loss functions are also
$\sigma$-sub-Gaussian on the left-tail under the same distribution (loss
function in Section 2.2 is $\sigma$-sub-Gaussian on the left-tail, but not
sub-Gaussian). Therefore, our result also applies to any bounded loss function
$\ell:\mathcal{W}\times\mathcal{Z}\rightarrow[a,b]$, since bounded functions
are $(\frac{b-a}{2})$-sub-Gaussian.

######  Remark 1 (Previous Results).

Using the fact that Gibbs algorithm is differentially private (McSherry &
Talwar, 2007) for bounded loss functions $\ell\in[0,1]$, directly applying (Xu
& Raginsky, 2017, Theorem 1) gives a sub-optimal bound
$|\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})|\leq\sqrt{\frac{\alpha}{n}}$.
By further exploring the bounded loss assumption using Hoeffding’s lemma, a
tighter upper bound
$|\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})|\leq\frac{\alpha}{2n}$ is
obtained in (Raginsky et al., 2016), which has the similar decay rate order of
$\mathcal{O}\left(1/n\right)$. In (Kuzborskij et al., 2019, Theorem 1), the
upper bound
$\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})\leq\frac{4\sigma^{2}\alpha}{n}$
is derived with a different assumption, i.e., $\ell(W,z)$ is $\sigma$-sub-
Gaussian under Gibbs algorithm $P_{{W}|S}^{\alpha}$. In Theorem 2, we assume
the loss function is $\sigma$-sub-Gaussian on left-tail under data generating
distribution $P_{Z}$ for all $w\in\mathcal{W}$, which is more general as we
discussed above. Our upper bound is also improved by a factor of
$\frac{1}{2(1+C_{E})}$ compared to the result in (Kuzborskij et al., 2019).

######  Remark 2 (Choice of $C_{E}$).

Since $L(W;S)>0$ when $I(W;S)>0$, setting $C_{E}=0$ is always valid in Theorem
2, which gives
$\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S})\leq\frac{2\sigma^{2}\alpha}{n}$.
As shown in (Palomar & Verdú, 2008, Theorem 15), $L(S;W)\geq I(S;W)$ holds for
any Gaussian channel $P_{W|S}$. In addition, it is discussed in (Palomar &
Verdú, 2008, Example 1), if either the entropy of training $S$ or the
hypothesis $W$ is small, $I(S;W)$ would be smaller than $L(S;W)$ (as it is not
upper-bounded by the entropy), which implies that the lautum information term
is not negligible in general.

##  4 Conclusion

We provide an exact characterization of the expected generalization error for
the Gibbs algorithm using symmetrized KL information. We demonstrate the
versatility of our approach by tightening the existing information-theoretic
expected generalization error upper bound. This work motivates further
investigation of the Gibbs algorithm in a variety of settings, including
extending our results to characterize the generalization ability of a over-
parameterized Gibbs algorithm, which could potentially provide more
understanding of the generalization ability for deep learning.

##  5 Acknowledgment

Yuheng Bu is supported, in part, by NSF under Grant CCF-1717610 and by the
MIT-IBM Watson AI Lab. Gholamali Aminian is supported by the Royal Society
Newton International Fellowship, grant no. NIF\R1 \192656.

## References

  * Alquier et al. (2016) Alquier, P., Ridgway, J., and Chopin, N.  On the properties of variational approximations of gibbs posteriors.  _The Journal of Machine Learning Research_ , 17(1):8374–8414, 2016.
  * Aminian et al. (2015) Aminian, G., Arjmandi, H., Gohari, A., Nasiri-Kenari, M., and Mitra, U.  Capacity of diffusion-based molecular communication networks over lti-poisson channels.  _IEEE Transactions on Molecular, Biological and Multi-Scale Communications_ , 1(2):188–201, 2015.
  * Aminian et al. (2020) Aminian, G., Toni, L., and Rodrigues, M. R.  Jensen-shannon information based characterization of the generalization error of learning algorithms.  _2020 IEEE Information Theory Workshop (ITW)_ , 2020.
  * Anthony & Bartlett (2009) Anthony, M. and Bartlett, P. L.  _Neural network learning: Theoretical foundations_.  cambridge university press, 2009.
  * Asadi et al. (2018) Asadi, A., Abbe, E., and Verdú, S.  Chaining mutual information and tightening generalization bounds.  In _Advances in Neural Information Processing Systems_ , pp. 7234–7243, 2018.
  * Asadi & Abbe (2020) Asadi, A. R. and Abbe, E.  Chaining meets chain rule: Multilevel entropic regularization and training of neural networks.  _Journal of Machine Learning Research_ , 21(139):1–32, 2020.
  * Bousquet & Elisseeff (2002) Bousquet, O. and Elisseeff, A.  Stability and generalization.  _Journal of machine learning research_ , 2(Mar):499–526, 2002.
  * Bu et al. (2020a) Bu, Y., Gao, W., Zou, S., and Veeravalli, V.  Information-theoretic understanding of population risk improvement with model compression.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 3300–3307, 2020a.
  * Bu et al. (2020b) Bu, Y., Zou, S., and Veeravalli, V. V.  Tightening mutual information-based bounds on generalization error.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1):121–130, 2020b.
  * Chiang et al. (1987) Chiang, T.-S., Hwang, C.-R., and Sheu, S. J.  Diffusion for global optimization in r^n.  _SIAM Journal on Control and Optimization_ , 25(3):737–753, 1987.
  * Esposito et al. (2019) Esposito, A. R., Gastpar, M., and Issa, I.  Generalization error bounds via $\alpha$-réyni, $f$-divergences and maximal leakage.  _arXiv preprint arXiv:1912.01439_ , 2019.
  * Gibbs (1902) Gibbs, J. W.  Elementary principles of statistical mechanics.  _Compare_ , 289:314, 1902.
  * Hafez-Kolahi et al. (2020) Hafez-Kolahi, H., Golgooni, Z., Kasaei, S., and Soleymani, M.  Conditioning and processing: Techniques to improve information-theoretic generalization bounds.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Haghifam et al. (2020) Haghifam, M., Negrea, J., Khisti, A., Roy, D. M., and Dziugaite, G. K.  Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms.  _Advances in Neural Information Processing Systems_ , 2020.
  * Issa et al. (2019) Issa, I., Esposito, A. R., and Gastpar, M.  Strengthened information-theoretic bounds on the generalization error.  In _2019 IEEE International Symposium on Information Theory (ISIT)_ , pp. 582–586. IEEE, 2019.
  * Jeffreys (1946) Jeffreys, H.  An invariant form for the prior probability in estimation problems.  _Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences_ , 186(1007):453–461, 1946\.
  * Jiao et al. (2017) Jiao, J., Han, Y., and Weissman, T.  Dependence measures bounding the exploration bias for general measurements.  In _2017 IEEE International Symposium on Information Theory (ISIT)_ , pp. 1475–1479. IEEE, 2017.
  * Kuzborskij et al. (2019) Kuzborskij, I., Cesa-Bianchi, N., and Szepesvári, C.  Distribution-dependent analysis of gibbs-erm principle.  In _Conference on Learning Theory_ , pp. 2028–2054. PMLR, 2019\.
  * Lopez & Jog (2018) Lopez, A. T. and Jog, V.  Generalization error bounds using wasserstein distances.  In _2018 IEEE Information Theory Workshop (ITW)_ , pp. 1–5. IEEE, 2018.
  * Markowich & Villani (2000) Markowich, P. A. and Villani, C.  On the trend to equilibrium for the fokker-planck equation: an interplay between physics and functional analysis.  _Mat. Contemp_ , 19:1–29, 2000.
  * Masiha et al. (2021) Masiha, M. S., Gohari, A., Yassaee, M. H., and Aref, M. R.  Learning under distribution mismatch and model misspecification.  _arXiv preprint arXiv:2102.05695_ , 2021.
  * McAllester (2003) McAllester, D. A.  Pac-bayesian stochastic model selection.  _Machine Learning_ , 51(1):5–21, 2003.
  * McSherry & Talwar (2007) McSherry, F. and Talwar, K.  Mechanism design via differential privacy.  In _48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07)_ , pp. 94–103. IEEE, 2007.
  * Murphy (2007) Murphy, K. P.  Conjugate bayesian analysis of the gaussian distribution.  _def_ , 1(2$\sigma$2):16, 2007.
  * Palomar & Verdú (2008) Palomar, D. P. and Verdú, S.  Lautum information.  _IEEE transactions on information theory_ , 54(3):964–975, 2008.
  * Raginsky et al. (2016) Raginsky, M., Rakhlin, A., Tsao, M., Wu, Y., and Xu, A.  Information-theoretic analysis of stability and bias of learning algorithms.  In _2016 IEEE Information Theory Workshop (ITW)_ , pp. 26–30. IEEE, 2016.
  * Raginsky et al. (2017) Raginsky, M., Rakhlin, A., and Telgarsky, M.  Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis.  In _Conference on Learning Theory_ , pp. 1674–1703. PMLR, 2017\.
  * Rodrigues & Eldar (2021) Rodrigues, M. R. and Eldar, Y. C.  _Information-Theoretic Methods in Data Science_.  Cambridge University Press, 2021.
  * Rodríguez-Gálvez et al. (2021) Rodríguez-Gálvez, B., Bassi, G., Thobaben, R., and Skoglund, M.  Tighter expected generalization error bounds via wasserstein distance.  _arXiv preprint arXiv:2101.09315_ , 2021.
  * Russo & Zou (2019) Russo, D. and Zou, J.  How much does your data exploration overfit? controlling bias via information usage.  _IEEE Transactions on Information Theory_ , 66(1):302–323, 2019.
  * Steinke & Zakynthinou (2020) Steinke, T. and Zakynthinou, L.  Reasoning about generalization via conditional mutual information.  _arXiv preprint arXiv:2001.09122_ , 2020.
  * Vapnik (1999) Vapnik, V. N.  An overview of statistical learning theory.  _IEEE transactions on neural networks_ , 10(5):988–999, 1999.
  * Wang et al. (2019) Wang, H., Diaz, M., Santos Filho, J. C. S., and Calmon, F. P.  An information-theoretic view of generalization via wasserstein distance.  In _2019 IEEE International Symposium on Information Theory (ISIT)_ , pp. 577–581. IEEE, 2019.
  * Xu & Raginsky (2017) Xu, A. and Raginsky, M.  Information-theoretic analysis of generalization capability of learning algorithms.  In _Advances in Neural Information Processing Systems_ , pp. 2524–2533, 2017.
  * Xu & Mannor (2012) Xu, H. and Mannor, S.  Robustness and generalization.  _Machine learning_ , 86(3):391–423, 2012.
  * Zhang et al. (2016) Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O.  Understanding deep learning requires rethinking generalization.  _arXiv preprint arXiv:1611.03530_ , 2016.
  * Zhang (2006) Zhang, T.  Information-theoretic upper and lower bounds for statistical estimation.  _IEEE Transactions on Information Theory_ , 52(4):1307–1321, 2006.
  * Zhang et al. (2006) Zhang, T. et al.  From $\epsilon$-entropy to kl-entropy: Analysis of minimum information complexity density estimation.  _The Annals of Statistics_ , 34(5):2180–2210, 2006.

##  Appendix A Proof of Theorem 1

We start with the following two Lemmas:

######  Lemma 1.

We define the following $J_{E}(w,S)$ function as a proxy for the empirical
risk, i.e.,
$J_{E}(w,S)\triangleq\frac{\alpha}{n}\sum_{i=1}^{n}\ell(w,Z_{i})+g(w)+h(S)$,
where $\alpha\in\mathbb{R}_{0}^{+}$, $g:\mathcal{W}\to\mathbb{R}$,
$h:\mathcal{Z}^{n}\to\mathbb{R}$, and the function
$J_{P}(w,\mu)\triangleq\mathbb{E}_{P_{S}}[J_{E}(w,S)]$ as a proxy for the
population risk. Then,

$\mathbb{E}_{P_{W,S}}[J_{P}(W,\mu)-J_{E}(W,S)]=\alpha\cdot\overline{\text{gen}}(P_{W|S},P_{S}).$
(13)

###### Proof.

$\displaystyle\mathbb{E}_{P_{W,S}}[J_{P}(W,\mu)-J_{E}(W,S)]$
$\displaystyle=\mathbb{E}_{P_{W,S}}\Big{[}\mathbb{E}_{P_{Z^{n}}}[\frac{\alpha}{n}\sum_{i=1}^{n}\ell(W,Z_{i})]-\frac{\alpha}{n}\sum_{i=1}^{n}\ell(W,Z_{i})\Big{]}$
$\displaystyle\quad+\mathbb{E}_{P_{W}}\Big{[}g(W)+\mathbb{E}_{P_{S}}[h(S)]\Big{]}-\mathbb{E}_{P_{W,S}}\Big{[}g(W)+h(S)\Big{]}$
$\displaystyle=\alpha\cdot\mathbb{E}_{P_{W,S}}[L_{P}(W,\mu)-L_{E}(W,S)]$
$\displaystyle=\alpha\cdot\overline{\text{gen}}(P_{W|S},P_{S}).\qed$

######  Lemma 2.

Consider a learning algorithm $P_{W|S}$, if we set the function
$J_{E}(w,z^{n})=-\log P_{W|S}(w|s)$, then

$\mathbb{E}_{P_{W,S}}[J_{P}(W,\mu)-J_{E}(W,S)]=I_{\mathrm{SKL}}(W;S).$ (14)

###### Proof.

$\displaystyle I(W;S)+L(W;S)$
$\displaystyle=\mathbb{E}_{P_{W,S}}\Big{[}\log\frac{P_{W|S}(W|S)}{P_{W}(W)}\Big{]}+\mathbb{E}_{P_{W}\otimes
P_{S}}\Big{[}\log\frac{P_{W}(W)}{P_{W|S}(W|S)}\Big{]}$
$\displaystyle=\mathbb{E}_{P_{W,S}}\Big{[}\log{P_{W|S}(W|S)}\Big{]}-\mathbb{E}_{P_{W}\otimes
P_{S}}\Big{[}\log{P_{W|S}(W|S)}\Big{]}$
$\displaystyle=\mathbb{E}_{P_{W,S}}[-\mathbb{E}_{P_{S}}[\log
P_{W|S}(W|S)]+\log P_{W|S}(W|S)]$
$\displaystyle=\mathbb{E}_{P_{W,S}}[J_{P}(W,\mu)-J_{E}(W,S)].\qed$

Considering Lemma 1 and Lemma 2, we just need to verify that the function
$J_{E}(w,s)=-\log P_{{W}|S}(w|s)$ can be decomposed into
$J_{E}(w,s)=\frac{\alpha}{n}\sum_{i=1}^{n}\ell(w,z_{i})+g(w)+h(s)$, for
$\alpha>0$. Note that

$\displaystyle-\log P_{{W}|S}^{\alpha}(w|s)=\alpha
L_{E}(w,s)-\log\pi({w})+\log V(s,\alpha),$

then we have:

$\displaystyle I_{\mathrm{SKL}}(W;S)$
$\displaystyle=\mathbb{E}_{P_{W,S}}[J_{P}(W,P_{S})-J_{E}(W,S)]$
$\displaystyle=\alpha\cdot\overline{\text{gen}}(P_{{W}|S}^{\alpha},P_{S}).$
(15)

##  Appendix B Example Details: Estimating the Mean of Gaussian

###  B.1 Generalization Error

We first evaluate the generalization error of the learning algorithm in (8)
directly. Note that the output $W$ can be written as

$W=\frac{\sigma_{1}^{2}}{\sigma_{0}^{2}}{\bm{\mu}}_{0}+\frac{\sigma_{1}^{2}}{\sigma^{2}}\sum_{i=1}^{n}Z_{i}+N,$
(16)

where $N\sim\mathcal{N}(0,\sigma^{2}_{1}I_{d})$ is independent from the
training samples $S=\\{Z_{i}\\}_{i=1}^{n}$. Thus,

$\displaystyle\overline{\text{gen}}(P_{W|S},P_{Z})$
$\displaystyle=\mathbb{E}_{P_{W,S}}[L_{P}(W,\mu)-L_{E}(W,S)]$
$\displaystyle=\mathbb{E}_{P_{W,S}}\Big{[}\mathbb{E}_{P_{\widetilde{Z}}}\big{[}\|W-\widetilde{Z}\|_{2}^{2}\big{]}-\frac{1}{n}\sum_{i=1}^{n}\|W-Z_{i}\|_{2}^{2}\Big{]}$
$\displaystyle\overset{(a)}{=}\mathbb{E}_{P_{W,Z_{i}}\otimes
P_{\widetilde{Z}}}\Big{[}(2W-\widetilde{Z}-Z_{i})^{\top}(Z_{i}-\widetilde{Z})\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}2(\frac{\sigma_{1}^{2}}{\sigma_{0}^{2}}{\bm{\mu}}_{0}+\frac{\sigma_{1}^{2}}{\sigma^{2}}\sum_{i=1}^{n}Z_{i}+N)^{\top}(Z_{i}-\widetilde{Z})$
$\displaystyle\qquad\qquad\qquad-(Z_{i}+\widetilde{Z})^{\top}(Z_{i}-\widetilde{Z})\Big{]}$
$\displaystyle\overset{(b)}{=}\frac{2\sigma_{1}^{2}}{\sigma^{2}}\mathbb{E}\Big{[}Z_{i}^{\top}(Z_{i}-\widetilde{Z})\Big{]}$
$\displaystyle=\frac{2d\sigma_{1}^{2}\sigma_{Z}^{2}}{\sigma^{2}}=\frac{2d\sigma_{0}^{2}\sigma_{Z}^{2}}{n\sigma_{0}^{2}+\sigma^{2}},$
(17)

where $\widetilde{Z}\sim\mathcal{N}({\bm{\mu}},\sigma_{Z}^{2}I_{d})$ denotes
an independent copy of the training sample, $(a)$ follows due to the fact that
$Z^{n}$ are i.i.d, and $(b)$ follows from the fact that $Z_{i}-\widetilde{Z}$
has zero mean, and it is only dependent on $Z_{i}$.

###  B.2 Symmetrized KL divergence

The following lemma from (Palomar & Verdú, 2008) characterizes the mutual and
lautum information for the Gaussian Channel.

######  Lemma 3.

(Palomar & Verdú, 2008, Theorem 14) Consider the following model

${\bm{Y}}={\bm{A}}{\bm{X}}+{\bm{N}}_{\mathrm{G}},$ (18)

where ${\bm{X}}\in\mathbb{R}^{d_{X}}$ denotes the input random vector with
zero mean (not necessarily Gaussian), ${\bm{A}}\in\mathbb{R}^{d_{Y}\times
d_{X}}$ denotes the linear transformation undergone by the input,
${\bm{Y}}\in\mathbb{R}^{d_{Y}}$ is the output vector, and
${\bm{N}}_{\mathrm{G}}\in\mathbb{R}^{d_{Y}}$ is a Gaussian noise vector
independent of ${\bm{X}}$. The input and the noise covariance matrices are
given by ${\bm{\Sigma}}$ and ${\bm{\Sigma}}_{N_{\mathrm{G}}}$. Then, the
mutual information and lautum information are given by

$\displaystyle I({\bm{X}};{\bm{Y}})$
$\displaystyle=\mathrm{tr}\big{(}{\bm{\Sigma}}_{N_{\mathrm{G}}}^{-1}{\bm{A}}{\bm{\Sigma}}{\bm{A}}^{\top}\big{)}-D\big{(}P_{\bm{Y}}\|P_{N_{\mathrm{G}}}\big{)},$
(19) $\displaystyle L({\bm{X}};{\bm{Y}})$
$\displaystyle=\mathrm{tr}\big{(}{\bm{\Sigma}}_{N_{\mathrm{G}}}^{-1}{\bm{A}}{\bm{\Sigma}}{\bm{A}}^{\top}\big{)}+D\big{(}P_{\bm{Y}}\|P_{N_{\mathrm{G}}}).$
(20)

In our example, the output $W$ can be written as

$\displaystyle W$
$\displaystyle=\frac{\sigma_{1}^{2}}{\sigma_{0}^{2}}{\bm{\mu}}_{0}+\frac{\sigma_{1}^{2}}{\sigma^{2}}\sum_{i=1}^{n}Z_{i}+N,$
$\displaystyle=\frac{\sigma_{1}^{2}}{\sigma^{2}}\sum_{i=1}^{n}(Z_{i}-{\bm{\mu}})+\frac{\sigma_{1}^{2}}{\sigma_{0}^{2}}{\bm{\mu}}_{0}+\frac{n\sigma_{1}^{2}}{\sigma^{2}}{\bm{\mu}}+N,$
(21)

where $N\sim\mathcal{N}(0,\sigma^{2}_{1}I_{d})$. Then, setting
$P_{N_{\mathrm{G}}}\sim\mathcal{N}(\frac{\sigma_{1}^{2}}{\sigma_{0}^{2}}{\bm{\mu}}_{0}+\frac{n\sigma_{1}^{2}}{\sigma^{2}}{\bm{\mu}},\sigma^{2}_{1}I_{d})$,
${\bm{\Sigma}}=\sigma_{Z}^{2}I_{nd}$ and noticing that
${\bm{A}}{\bm{A}}^{\top}=\frac{n\sigma_{1}^{4}}{\sigma^{4}}I_{d}$ in Lemma 3
completes the proof.

###  B.3 ISMI bound

In this subsection, we evaluate the ISMI bound from (Bu et al., 2020b) for the
example discussed in Section 2.2 with i.i.d. samples generated from Gaussian
$P_{Z}\sim\mathcal{N}({\bm{\mu}},\sigma_{Z}^{2}I_{d})$.

######  Lemma 4.

(Bu et al., 2020b, Theorem 2) Suppose $\ell(\widetilde{W},\widetilde{Z})$
satisfies
$\Lambda_{\ell(\widetilde{W},\widetilde{Z})}(\lambda)\leq\psi_{+}(\lambda)$
for $\lambda\in[0,b_{+})$, and
$\Lambda_{\ell(\widetilde{W},\widetilde{Z})}(\lambda)\leq\psi_{-}(-\lambda)$
for $\lambda\in(b_{-},0]$ under $P_{\widetilde{Z},\widetilde{W}}=P_{Z}\otimes
P_{W}$, where $0<b_{+}\leq\infty$ and $-\infty\leq b_{-}<0$. Then,

$\displaystyle\mathrm{gen}(P_{W|S},P_{S})\leq\frac{1}{n}\sum_{i=1}^{n}\psi^{*-1}_{-}\big{(}I(W;Z_{i})\big{)},$
(22)
$\displaystyle-\mathrm{gen}(P_{W|S},P_{S})\leq\frac{1}{n}\sum_{i=1}^{n}\psi^{*-1}_{+}\big{(}I(W;Z_{i})\big{)}.$
(23)

First, we need to compute the mutual information between each individual
sample and the output hypothesis $I(W;Z_{i})$, and the cumulant generating
function (CGF) of $\ell(\widetilde{W},\widetilde{Z})$, where $\widetilde{W}$,
$\widetilde{Z}$ are independent copies of $W$ and $Z$ with the same marginal
distribution, respectively.

Since $W$ and $Z_{i}$ are Gaussian, $I(W;Z_{i})$ can be computed exactly as:

${\rm{Cov}}[Z_{i},W]=\left(\begin{array}[]{cc}\sigma_{Z}^{2}I_{d}&\frac{\sigma_{1}^{2}}{\sigma^{2}}\sigma_{Z}^{2}I_{d}\\\
\frac{\sigma_{1}^{2}}{\sigma^{2}}\sigma_{Z}^{2}I_{d}&\big{(}\frac{n\sigma_{1}^{4}}{\sigma^{4}}\sigma_{Z}^{2}+\sigma_{1}^{2}\big{)}I_{d}\\\
\end{array}\right),$ (24)

then, we have

$\displaystyle I(W;Z_{i})$
$\displaystyle=\frac{d}{2}\log\frac{\frac{n\sigma_{1}^{4}}{\sigma^{4}}\sigma_{Z}^{2}+\sigma_{1}^{2}}{\frac{(n-1)\sigma_{1}^{4}}{\sigma^{4}}\sigma_{Z}^{2}+\sigma_{1}^{2}}$
$\displaystyle=\frac{d}{2}\log\Big{(}1+\frac{\sigma_{1}^{2}\sigma_{Z}^{2}}{(n-1)\sigma_{1}^{2}\sigma_{Z}^{2}+\sigma^{4}}\Big{)}$
(25)
$\displaystyle=\frac{d}{2}\log\Big{(}1+\frac{\sigma_{0}^{2}\sigma_{Z}^{2}}{(n-1)\sigma_{0}^{2}\sigma_{Z}^{2}+n\sigma_{0}^{2}\sigma^{2}+\sigma^{4}}\Big{)},$

for $i=1,\cdots,n$, $n\geq 2$. In addition, since

$W\sim\mathcal{N}\Big{(}\frac{\sigma_{1}^{2}}{\sigma_{0}^{2}}{\bm{\mu}}_{0}+\frac{n\sigma_{1}^{2}}{\sigma^{2}}{\bm{\mu}},\big{(}\frac{n\sigma_{1}^{4}}{\sigma^{4}}\sigma_{Z}^{2}+\sigma_{1}^{2}\big{)}I_{d}\Big{)},$
(26)

it can be shown that
$\ell(\widetilde{W},\widetilde{Z})=\|\widetilde{Z}-\widetilde{W}\|^{2}$ is a
scaled non-central chi-square distribution with $d$ degrees of freedom, where
the scaling factor
$\sigma_{\ell}^{2}\triangleq(\frac{n\sigma_{1}^{4}}{\sigma^{4}}+1)\sigma_{Z}^{2}+\sigma_{1}^{2}$
and its non-centrality parameter
$\eta\triangleq\frac{\sigma^{2}}{n\sigma_{0}^{2}+\sigma^{2}}\|{\bm{\mu}}_{0}-{\bm{\mu}}\|_{2}^{2}$.
Note that the expectation of chi-square distribution with non-centrality
parameter $\eta$ and $d$ degrees of freedom is $d+\eta$ and its moment
generating function is
$\exp(\frac{\eta\lambda}{1-2\lambda})(1-2\lambda)^{-d/2}$. Therefore, the CGF
of $\ell(\widetilde{W},\widetilde{Z})$ is given by

$\Lambda_{\ell(\widetilde{W},\widetilde{Z})}(\lambda)=-(d\sigma_{\ell}^{2}+\eta)\lambda+\frac{\eta\lambda}{1-2\sigma_{\ell}^{2}\lambda}-\frac{d}{2}\log(1-2\sigma_{\ell}^{2}\lambda),$

for $\lambda\in(-\infty,\frac{1}{2\sigma_{\ell}^{2}})$. Since
$\mathrm{gen}(P_{W|S},P_{Z})\geq 0$, we only need to consider the case
$\lambda<0$. It can be shown that:

$\displaystyle\Lambda_{\ell(\widetilde{W},\widetilde{Z})}(\lambda)$
$\displaystyle=-d\sigma_{\ell}^{2}\lambda-\frac{d}{2}\log(1-2\sigma_{\ell}^{2}\lambda)+\frac{2\sigma_{\ell}^{2}\eta\lambda^{2}}{1-2\sigma_{\ell}^{2}\lambda}$
$\displaystyle=\frac{d}{2}(-u-\log(1-u))+\frac{2\sigma_{\ell}^{2}\eta\lambda^{2}}{1-2\sigma_{\ell}^{2}\lambda},$
(27)

where $u\triangleq 2\sigma_{\ell}^{2}\lambda$. Further note that

$\displaystyle-u-\log(1-u)\leq\frac{u^{2}}{2},\ u$ $\displaystyle<0,$ (28)
$\displaystyle\frac{2\sigma_{\ell}^{2}\eta\lambda^{2}}{1-2\sigma_{\ell}^{2}\lambda}\leq
2\sigma_{\ell}^{2}\eta\lambda^{2},\ \lambda$ $\displaystyle<0.$ (29)

We have the following upper bound on the CGF of
$\ell(\widetilde{W},\widetilde{Z})$:

$\Lambda_{\ell(\widetilde{W},\widetilde{Z})}(\lambda)\leq(d\sigma_{\ell}^{4}+2\sigma_{\ell}^{2}\eta)\lambda^{2},\quad\lambda<0,$
(30)

which means that $\ell(\widetilde{W},\widetilde{Z})$ is
$\sqrt{d\sigma_{\ell}^{4}+2\sigma_{\ell}^{2}\eta}$-sub-Gaussian for
$\lambda<0$. Combining the results in (B.3), Lemma 4 gives the following bound

$\displaystyle\overline{\text{gen}}(P_{W|S},P_{S})\leq$
$\displaystyle\quad\sqrt{\frac{d^{2}\sigma_{\ell}^{4}+2d\sigma_{\ell}^{2}\eta}{2}\log(1+\frac{\sigma_{0}^{2}\sigma_{Z}^{2}}{(n-1)\sigma_{0}^{2}\sigma_{Z}^{2}+n\sigma_{0}^{2}\sigma^{2}+\sigma^{4}})}.$

If $\sigma^{2}=\frac{n}{2\alpha}$ is fixed, i.e., $\alpha=\mathcal{O}(n)$,
then as $n\to\infty$, $\sigma_{\ell}^{2}=\mathcal{O}(1)$, and the above bound
is $\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)$.

##  Appendix C Proof of Theorem 2

Using the (Xu & Raginsky, 2017, Theorem 1) and considering the non-negativity
of generalization error, we have:

$\displaystyle\overline{\text{gen}}(P_{{W}|S},\mu)\leq\sqrt{\frac{2\sigma^{2}I(W;S)}{n}}$
(31)

By the Theorem 1, the following holds:

$\frac{I_{\mathrm{SKL}}(W;S)}{\alpha}\leq\sqrt{\frac{2\sigma^{2}I(W;S)}{n}}$
(32)

As the $C_{E}\times I(W;S)\leq L(W;S)$ we have:

$\frac{(1+C_{E})I(W;S)}{\alpha}\leq\sqrt{\frac{2\sigma^{2}I(W;S)}{n}}$ (33)

which is true for

$\sqrt{\frac{2\sigma^{2}I(W;S)}{n}}\leq\frac{2\sigma^{2}\alpha}{n(1+C_{E})}.$
(34)

It completes the proof.