# Gate Set Tomography

Erik Nielsen  Quantum Performance Laboratory, Sandia National Laboratories
John King Gamble  Microsoft Research  Kenneth Rudinger  Quantum Performance
Laboratory, Sandia National Laboratories  Travis Scholten  IBM Quantum, IBM
T.J. Watson Research Center  Kevin Young  Quantum Performance Laboratory,
Sandia National Laboratories  Robin Blume-Kohout  Quantum Performance
Laboratory, Sandia National Laboratories

###### Abstract

Gate set tomography (GST) is a protocol for detailed, predictive
characterization of logic operations (gates) on quantum computing processors.
Early versions of GST emerged around 2012-13, and since then it has been
refined, demonstrated, and used in a large number of experiments. This paper
presents the foundations of GST in comprehensive detail. The most important
feature of GST, compared to older state and process tomography protocols, is
that it is _calibration-free_. GST does not rely on pre-calibrated state
preparations and measurements. Instead, it characterizes all the operations in
a _gate set_ simultaneously and self-consistently, relative to each other.
Long sequence GST can estimate gates with very high precision and efficiency,
achieving Heisenberg scaling in regimes of practical interest. In this paper,
we cover GST’s intellectual history, the techniques and experiments used to
achieve its intended purpose, data analysis, gauge freedom and fixing, error
bars, and the interpretation of gauge-fixed estimates of gate sets. Our focus
is fundamental mathematical aspects of GST, rather than implementation
details, but we touch on some of the foundational algorithmic tricks used in
the pyGSTi implementation.

###### Contents

  1. I Introduction
    1. I.1 Gate set tomography
    2. I.2 Section guide & expert summary
  2. II Background
    1. II.1 Mathematical Preliminaries
      1. II.1.1 Quantum processors and quantum circuits
      2. II.1.2 States, measurements, and Hilbert-Schmidt space
      3. II.1.3 Quantum logic gates
      4. II.1.4 Gate sets
      5. II.1.5 Circuits
    2. II.2 State, Process, and Measurement Tomography
      1. II.2.1 Quantum state tomography
      2. II.2.2 Quantum process tomography
      3. II.2.3 Measurement tomography
    3. II.3 The role of calibration in tomography
  3. III Linear gate set tomography (LGST)
    1. III.1 Introduction to LGST
    2. III.2 The LGST algorithm
    3. III.3 Addressing overcompleteness with pseudo-inverses
    4. III.4 Preparing the fiducial vectors
    5. III.5 Improving LGST with maximum likelihood estimation
  4. IV Long-sequence Gate Set Tomography
    1. IV.1 Historical background
    2. IV.2 Experiment design for long-sequence GST
      1. IV.2.1 Selecting germs ($g$)
      2. IV.2.2 Defining base circuits
      3. IV.2.3 Putting it all together
    3. IV.3 Estimating gate set parameters in long-sequence GST
  5. V Advanced long-sequence GST
    1. V.1 Gate set models
      1. V.1.1 Gauge freedom in constrained gate sets
      2. V.1.2 TP and CPTP constrained models
    2. V.2 Fiducial-pair reduction
  6. VI Analyzing GST estimates
    1. VI.1 Goodness-of-fit and Markovianity
    2. VI.2 Gauge optimization
      1. VI.2.1 Why gauge optimization?
      2. VI.2.2 Metrics for gauge optimization
    3. VI.3 Error bars
      1. VI.3.1 General problems with region estimators
      2. VI.3.2 Bootstrapping
      3. VI.3.3 Confidence regions based on the Hessian of the likelihood
      4. VI.3.4 Dealing with gauge freedom
      5. VI.3.5 Gauge-fixing bootstrap regions
      6. VI.3.6 Gauge-fixing Hessian-based regions
  7. VII Summary
  8. A Gauge
    1. A.1 Gauge degrees of freedom
    2. A.2 Gauge considerations in error bars
  9. B The extended LGST (eLGST) protocol
  10. C Implementations in pyGSTi
    1. C.1 Circuit selection
      1. C.1.1 Fiducial selection
      2. C.1.2 Germ Selection
      3. C.1.3 Base circuit selection
      4. C.1.4 Fiducial pair reduction.
    2. C.2 Non-TP loglikelihood optimization
  11. D Numerical verification
  12. E $\chi^{2}$ estimator SPAM bias

##  I Introduction

Getting to useful quantum computation will require engineering quantum bits
(qubits) that support high-fidelity quantum logic operations, and then
assembling them into increasingly large quantum processors, with many coupled
qubits, that can run quantum circuits. But qubits are susceptible to noise.
High-fidelity logic operations are hard to perform, and failure rates as low
as $10^{-4}$ are rare and remarkable. Useful quantum computation may require
fault tolerant quantum error correction, which distills a few high-fidelity
logical qubits from many noisy ones. Threshold theorems Knill (2005); Aliferis
et al. (2006); Aliferis and Cross (2007); Aliferis and Preskill (2009) prove
that this is possible in realistic quantum processors – _if_ the processor’s
errors satisfy certain conditions. Each threshold theorem assumes different
conditions on the errors, but in general they must (1) be only of certain
types, and (2) occur at a rate below a certain value (generally around
$10^{-3}$ – $10^{-4}$ for the most common types). So it is not an exaggeration
to say that the entire program of practical quantum computing depends on
understanding and characterizing the errors that occur in as-built processors,
controlling their form, and reducing their rates.

Assessing how qubits, logic operations, and entire processors behave is the
central task of _quantum device characterization_ , a.k.a. “quantum
characterization, verification, and validation” (QCVV). There are many
protocols for this task, all of which share the same basic structure: a set of
experiments described by _quantum circuits_ are performed on the processor,
yielding data that is processed according to some algorithm, to produce an
estimate of an aspect of the processor’s behavior. Some protocols produce
highly detailed predictive models of each logic operation (tomography Gale et
al. (1968); Vogel and Risken (1989); Hradil (1997); Munro et al. (2001); James
et al. (2001); Artiles et al. (2005); Blume-Kohout (2010a, b); Christandl and
Renner (2012); Smolin et al. (2012); Banaszek et al. (2013); Granade et al.
(2016); Haah et al. (2017); Poyatos et al. (1997); Chuang and Nielsen (1997);
Fiurášek and Hradil (2001); D’Ariano and Lo Presti (2001); Childs et al.
(2001); Altepeter et al. (2003); O’Brien et al. (2004); Weinstein et al.
(2004); Mohseni and Lidar (2006); Riebe et al. (2006); Bendersky et al.
(2008); Lobino et al. (2008); Bialczak et al. (2010); Kimmel et al. (2014a);
Kim et al. (2014); Blume-Kohout et al. (2013); Greenbaum (2015); Kim et al.
(2015); Dehollain et al. (2016); Blume-Kohout et al. (2017a)). Others produce
semi-predictive partial characterizations (component benchmarking Emerson et
al. (2007); Knill et al. (2008); Wallman and Flammia (2014); Magesan et al.
(2011); Magesan et al. (2012a); Gaebler et al. (2012); Magesan et al. (2012b);
Gambetta et al. (2012); Córcoles et al. (2013); Barends et al. (2014); Wallman
et al. (2015a); Carignan-Dugas et al. (2015); Wallman et al. (2015b); Chasseur
and Wilhelm (2015); Sheldon et al. (2016); Wallman et al. (2016); Proctor et
al. (2017); Harper and Flammia (2017); Wallman (2018); Huang et al. (2019);
McKay et al. (2019); Proctor et al. (2019a); Erhard et al. (2019); Ekert et
al. (2002); Lévi et al. (2007); Tóth et al. (2010); Flammia and Liu (2011); da
Silva et al. (2011); Moussa et al. (2012); Reich et al. (2013); Kimmel et al.
(2015); Rudinger et al. (2017a); Aaronson (2018); Mayer and Knill (2018);
Huang and Kueng (2019); Helsen et al. (2019); Huang et al. (2020)). And some
assess the performance of entire processors (holistic benchmarking Bishop et
al. (2017); Linke et al. (2017); Michielsen et al. (2017); Neill et al.
(2018); Boixo et al. (2018); Hempel et al. (2018); Yeter-Aydeniz et al.
(2019); Blume-Kohout and Young (2019); Hamilton et al. (2019); Cross et al.
(2019); Arute et al. (2019); McCaskey et al. (2019); Wright et al. (2019)).

All of these methods are valuable parts of the QCVV toolbox, serving distinct
(though overlapping) purposes. Some tasks demand simple holistic summaries of
overall performance, while others are best served by partial characterization.
But for debugging, rigorous device modeling, and reliable prediction of
complex circuit performance (including the circuits that perform quantum error
correction) there is as yet no substitute for detailed tomography of
individual logic operations, a.k.a. quantum gates. The most powerful and
comprehensive technique for this task is currently gate set tomography (GST).
Developed around 2012-13, GST has been used in a variety of experiments Blume-
Kohout et al. (2013); Kim et al. (2015); Dehollain et al. (2016); Blume-Kohout
et al. (2017a); Ware et al. (2018); Proctor et al. (2019b); Song et al.
(2019); Hong et al. (2020); Joshi et al. (2020); Zhang et al. (2020),
discussed in the literature White et al. (2019); O’Brien et al. (2017);
Scholten et al. (2019); Cerfontaine et al. (2019); Rol et al. (2017); Mavadia
et al. (2018); Puchała et al. (2019); Lin et al. (2019a); Rudnicki et al.
(2018); Rudinger et al. (2017a); Kimmel et al. (2015); Endo et al. (2018), and
implemented in a large open-source software project Nielsen et al. (2016,
2020). But no comprehensive explanation of the theory behind GST has appeared
in the literature. This paper fills that gap.

###  I.1 Gate set tomography

The term “gate-set tomography” first appeared in a 2012 paper from IBM
Research Merkel et al. (2013) that introduced several of GST’s core concepts,
but the group did not pursue GST further. Around the same time, our group at
Sandia National Labs started pursuing an independent approach to the same
problem Blume-Kohout et al. (2013); Kim et al. (2015), which we have developed
extensively since then Dehollain et al. (2016); Blume-Kohout et al. (2017a);
Proctor et al. (2019b); Nielsen et al. (2020). This approach to GST, which has
been used in a number of additional experiments over the past 5 years Rol et
al. (2017); Mavadia et al. (2018); Ware et al. (2018); Song et al. (2019);
Hong et al. (2020); Joshi et al. (2020); Zhang et al. (2020); Cincio et al.
(2020), is the one that we discuss and present here. We discuss its
relationship to IBM’s original approach where appropriate.

“Tomography” means the reconstruction of a comprehensive model (of something)
from many partial cross-sections or slices, each of which provides only a
limited view that may be useless by itself. Tomographic techniques are
distinguished by their aspiration to construct a _comprehensive_ model for a
system or component, by _fitting_ that model to the data from many independent
experiments. Quantum tomographic methods include state tomography Gale et al.
(1968); Vogel and Risken (1989); Hradil (1997); Munro et al. (2001); James et
al. (2001); Artiles et al. (2005); Blume-Kohout (2010a, b); Christandl and
Renner (2012); Smolin et al. (2012); Banaszek et al. (2013); Granade et al.
(2016); Haah et al. (2017), process tomography Poyatos et al. (1997); Chuang
and Nielsen (1997); Fiurášek and Hradil (2001); D’Ariano and Lo Presti (2001);
Childs et al. (2001); Altepeter et al. (2003); O’Brien et al. (2004);
Weinstein et al. (2004); Mohseni and Lidar (2006); Riebe et al. (2006);
Bendersky et al. (2008); Lobino et al. (2008); Bialczak et al. (2010); Kimmel
et al. (2014a); Kim et al. (2014), detector or measurement tomography Luis and
Sánchez-Soto (1999); Fiurasek (2001); Lundeen et al. (2009); Blumoff et al.
(2016); Chen et al. (2019), Hamiltonian tomography Schirmer et al. (2004);
Cole et al. (2005); Di Franco et al. (2009); Granade et al. (2012); Ferrie et
al. (2013); Zhang and Sarovar (2014); Wang et al. (2015); Cole (2015);
Rudinger and Joynt (2015); Wang et al. (2017); Krastanov et al. (2019); Hou et
al. (2019) and GST.

Like process tomography, GST is intended to characterize _how logic operations
(e.g. gates) impact their target qubits_. Those gates’ target subsystem and
state space needs to be specified up front, and GST reconstructs the gate-
driven evolution of those targets only. GST is not designed to probe the
holistic performance of many-qubit processors, and as most commonly used, it
does not capture general crosstalk. (Although GST can easily be adapted to
focus on _specific_ types of crosstalk, and characterize them in detail.)

GST differs from state and process tomography, which we discuss later in Sec.
II.2, in two fundamental ways. First, it is almost entirely _calibration-free_
(or “self-calibrating”). When GST reconstructs a model of a quantum system, it
does not depend on a prior description of the measurements used (as does state
tomography) or the states that can be prepared (as does process tomography).
Second, GST reconstructs or estimates not a single logic operation (e.g.,
state preparation or logic gate), but an entire _set_ of logic operations – a
_gate set_ including one or more state preparations, measurements, and logic
gates. These two features are inextricably linked, and we discuss this
connection later in this paper.

GST’s independence from calibration is its original _raison d’etre_. As IBM
pointed out Merkel et al. (2013), state and process tomography become
systematically unreliable when the “reference frame” operations on which they
rely (pre-calibrated measurements for state tomography, pre-calibrated state
preparations _and_ measurements for process tomography) are either unknown, or
misidentified. This limits their practical utility and makes them unsuitable
for rigorous characterization.

GST is not the only calibration-free method. Today, new characterization
protocols are more or less expected to be calibration-free. The oldest
calibration-free protocol is randomized benchmarking (RB) Emerson et al.
(2007); Knill et al. (2008), which predates GST by almost 10 years. Detailed
comparisons between RB and GST have been given elsewhere Dehollain et al.
(2016); Blume-Kohout et al. (2017a), and they are complementary tools
addressing different needs.

This paper is not a GST “how-to” manual. We do provide some incidental
discussion of how to perform GST in practice, and how it is implemented in our
pyGSTi software Nielsen et al. (2016), but only inasmuch as it illustrates
aspects of the theory. Separately, we recently published a concise guide to
applying GST to characterize hardware Nielsen et al. (2020). In contrast, this
article is intended as a theory paper presenting GST’s mathematical
background, justifications, and derivations.

###  I.2 Section guide & expert summary

Because this paper attempts to be comprehensive, it is rather long. So we
begin here with a short expert-level summary of the major ideas and results,
which may help readers decide what parts to read. A reader who understands
_everything_ in this section may not need to read any further at all! Other
readers may wish to skip to the first part that discusses a statement (from
this summary) that is not obvious.

We begin in Section II by establishing mathematical and conceptual
foundations. We introduce quantum logic operations (II.1.1); the mathematical
representations of states and measurements (II.1.2); and superoperators as a
model of noisy quantum logic gates, including transfer matrix and Choi matrix
representations, and introduce super-Dirac (superbra / superket) notation
(II.1.3). We introduce gate sets, their representation as a collection of
superoperators and operators, and gauge freedom (II.1.4). Finally, we
establish notation and conventions for quantum circuits and the superoperator
$\tau(g)$ caused by a quantum circuit $g$ (II.1.5).

In the second part of Section II, we review standard forms of tomography for
states, processes, and measurements (II.2). We conclude this introduction by
explaining the role of calibration in standard tomography (II.3) to set the
stage for GST.

Section III is devoted to linear inversion GST (LGST). We start with the
history of GST, describing how LGST solved some of the problems with the
initial versions of GST (III.1). We then derive LGST, emphasizing parallels
with process tomography (III.2), and introducing techniques required for long-
sequence GST. Readers inclined to skip over the mathematics in Section III.2
should feel free to do so, as these derivations are not prerequisites for
subsequent material. In the last parts of Section III, we address three issues
left unanswered in the derivation; how to deal with overcomplete data (III.3),
how to prepare fiducial states and measurements (III.4), and how to fit LGST
data better with maximum likelihood estimation (III.5).

Section IV introduces long-sequence GST, the standard “GST” protocol. (LGST
came first, and is easier to analyze theoretically, but is rarely used alone
in practice). We introduce the two main motivations for long-sequence GST,
which are (1) much higher accuracy, and (2) the ability to impose constraints
such as complete positivity. After discussing early and obsolete versions of
long-sequence GST (IV.1), we explain how to construct circuits that amplify
errors and enable Heisenberg-limited accuracy (IV.2). Then, we define the GST
likelihood function and show how to maximize it to find the maximum likelihood
estimate of a gate set model (IV.3).

Section V’s two subsections cover two “advanced” aspects of long-sequence GST.
The first (V.1) conceptualizes gate sets as parameterized models, introducing
the term “gate set model”, and discusses how to impose constraints like trace
preservation or complete positivity. The second (V.2) describes “fiducial pair
reduction”, a method for eliminating redundancy among the standard set of GST
circuits and thereby reducing the number of circuits prescribed.

Section VI addresses the question “What can you do with a GST estimate once
you have it?” We start with the critical step of assessing goodness-of-fit and
detecting _model violation_ or non-Markovianity (VI.1). We also explain what
we mean by “Markovian” in this context, and why model violation is associated
with “non-Markovian” behavior. We then turn to the important problem of
extracting simplified metrics (e.g., fidelity) from a gate set, explain why
choosing a gauge is necessary, and explain how to do so judiciously using a
process we call “gauge optimization” (VI.2). Finally, we discuss how to place
error bars around that point estimate, including how to deal with the
complications induced by gauge freedom (VI.3).

Appendices address some of the most technical and tangential points. These
include the gauge (A), the historically-important eLGST algorithm (B),
specific implementation choices made in pyGSTi (C), numerical studies that
support claims made in the main text (D), and the bias we find in a particular
estimator (E). Appendices are referenced from the text where applicable.

##  II Background

###  II.1 Mathematical Preliminaries

We begin with a concise introduction to the mathematics, formalism, and
notation used to describe qubits, multiqubit processors, their logic
operations, and the programs (quantum circuits) that they perform.

####  II.1.1 Quantum processors and quantum circuits

An idealized quantum information processor comprises one or more qubits that
can be (i) initialized, (ii) transformed by quantum logic gates, and (iii)
measured or “read out” to provide tangible classical data DiVincenzo (2000).
Using such a processor is usually described by physicists as running
experiments, and by computer scientists as running programs. These are the
same thing. Experiments/programs are described by _quantum circuits_ (see
Figure 1a), which specify a schedule of logic operations.

In this paper, the experiments we consider correspond to circuits that begin
with initialization of all the qubits, conclude with measurement of all the
qubits, and apply zero or more logic gates in the middle.

Figure 1: (a) A fixed-input classical-output (FI/CO) quantum circuit begins by
preparing all the qubits and ends by measuring all the qubits. The intervening
circuit layers (dashed rectangles) each describe a set of simultaneous logic
gates (gray boxes) on the qubits (horizontal black lines). (b) Because the
models used by GST treat distinct layers as a separate $n$-qubit gates
(indicated by the arrow), FI/CO circuits are, for the purposes of this paper,
composed of: a $n$-qubit state preparation, a sequence of $n$-qubit gates
(layers), and a $n$-qubit measurement. The symbols $\rho$, $G_{\gamma}$ and
$M=\\{E_{j}\\}_{j}$ label these operations within a gate set (cf. Eq. 6). The
particlar circuit shown begins with preparation in the $i$-th available state,
proceeds with execution of gates indexed by $\gamma_{i},\ldots\gamma_{6}$, and
concludes with performance of the $m$-th available measurement.

If a processor contains just one qubit, then only one logic gate can be
performed at a time, and every circuit corresponds to a state preparation, a
sequence of logic gates, and a measurement. Circuits on two or more qubits
typically specify logic gates on one or two qubits to be performed in parallel
on disjoint subsets of qubits. In this case, the operations to be performed in
parallel during a single clock cycle constitute a _layer_ of the circuit, and
every circuit corresponds to a preparation, sequence of layers, and
measurement. Models of many-qubit circuits must then have a means of
describing the way a circuit layer propagates a $n$-qubit quantum state based
on the one- and two-qubit gates within that layer. Such modeling, when the
layers are composed of imperfect gates, is nontrivial Sarovar et al. (2019).

The implementation of GST described in this paper utilizes models where each
circuit layer is an independent operation. That is, the only models we
consider describe only $n$-qubit operations (gates) that never occur in
parallel. _Every circuit layer is an independent “gate”, and all gates act on
all the qubits._ This important connection motivates our synonymouse use of
“gate” and “circuit layer” throughout the text. For example, a GST model
assumes no _a priori_ relationship between the behavior of the following three
layers (labeled by $G$ for “gate”):

  * •

“$G_{XI}$” – An $X$ gate on qubit 1, in parallel with an idle gate on qubit 2.

  * •

“$G_{IX}$” – An idle gate on qubit 1, in parallel with an $X$ gate on qubit 2.

  * •

“$G_{XX}$” – An $X$ gate on qubit 1, in parallel with an $X$ gate on qubit 2.

This approach rapidly becomes unwieldy as the number of qubits grows, since
exponentially many distinct layers are generally possible. While this limits
the scalability of the GST protocol (which was developed in the context of
one- and two-qubit systems where modeling parallel gates wasn’t an issue),
much of the ideas and theory surrounding it can be extended to many-qubit
models Nielsen .

QCVV protocols, including tomography, seek to deduce properties of a
processor’s elementary logic operations from the results of running circuits.
Doing so requires a model for all three kinds of logic operations
(initialization, gates, and measurements) that has adjustable parameters, and
can be used to predict circuit results probabilistically. The most common
model, and the one used by GST, is based on _Hilbert-Schmidt space_.

####  II.1.2 States, measurements, and Hilbert-Schmidt space

A quantum system – e.g., an $n$-qubit processor – is initialized into a
particular _quantum state_. A quantum state enables predicting probabilities
of outcomes of any measurements that could be made on the system. After
initialization, the state evolves as gates are applied. The final state, just
before the processor is measured, determines the probabilities of all possible
measurement outcomes. So we model the three kinds of quantum logic operations
as follows: initialization is modeled by a quantum state; logic gates are
modeled by dynamical maps that transform quantum states; measurements are
described by linear functionals that map quantum states to probability
distributions.

A quantum system is described with the help of a $d$-dimensional _Hilbert
space_ $\mathcal{H}=\mathbb{C}^{d}$, where $d$ is the largest number of
distinct outcomes of a repeatable measurement on that system (and is therefore
somewhat subjective). For a single qubit, $d=2$ by definition, and for a
system of $n$ qubits, $d=2^{n}$. 111Formal quantum theory is complicated by
the possibility of infinite-dimensional Hilbert spaces, but these are rarely
required for quantum computing, so we will assume finite $d$.

A quantum state is described by a $d\times d$ positive semidefinite, trace-1
matrix $\rho$ that acts on its Hilbert space
($\rho:\mathcal{H}\to\mathcal{H}$) Nielsen and Chuang (2000). This is called a
_density matrix_. A matrix must be positive semidefinite and have trace 1 in
order to represent a physically valid state. Such density matrices form a
convex set, and it is very convenient to embed this set in the complex
$d^{2}$-dimensional vector space of $d\times d$ matrices. This vector space is
called _Hilbert-Schmidt space_ and denoted by $\mathcal{B}(\mathcal{H})$. We
are almost always only concerned with _Hermitian_ (self-adjoint) matrices,
which form a real $d^{2}$-dimensional subspace of Hilbert-Schmidt space. In
this paper we will often disregard the constraints on density matrices and use
the symbol $\rho$ to describe any element of Hilbert-Schmidt space, stating
explicitly if/when the trace and positivity constraints are to be assumed.

Hilbert-Schmidt space is equipped with an inner product $\langle
A,B\rangle\equiv\mathrm{Tr}(A^{\dagger}B)$ that is used often in quantum
tomography. We represent an element $B$ of Hilbert-Schmidt space by a column
vector denoted $|B\rangle\\!\rangle$, and an element of its (isomorphic) dual
space by a row vector denoted $\langle\\!\langle A|$, and so
$\langle\\!\langle A|B\rangle\\!\rangle=\mathrm{Tr}(A^{\dagger}B)$. We will
represent quantum states as Hilbert-Schmidt vectors, and linear functionals on
states (e.g., outcomes of measurements) as dual vectors.

Measuring a quantum system yields an outcome or “result” which we assume is
drawn from a discrete set of $k$ alternatives. Each outcome’s probability is a
linear function of the state $\rho$. Therefore, the $i$th outcome can be
represented by a dual vector $\langle\\!\langle E_{i}|$, so that
$\mathrm{Pr}(i|\rho)=\langle\\!\langle
E_{i}|\rho\rangle\\!\rangle=\mathrm{Tr}(E_{i}\rho)$. The laws of probability
require that $E_{i}\geq 0$ and $\sum_{i}{E_{i}}=1\\!\mathrm{l}$. The $E_{i}$
are called _effects_. The set $\\{E_{i}\\}$ completely describes the
measurement and is called a _positive operator-valued measure (POVM)_. As with
states, we sometimes relax positivity constraints on POVM effects for
convenience.

We find it useful to define a basis for Hilbert-Schmidt space,
$\left\\{B_{i}\right\\}$, with the following properties:

  1. 1.

Hermiticity: $B_{i}=B_{i}^{\dagger}$,

  2. 2.

Orthonormality: $\mathrm{Tr}(B_{i}B_{j})=\delta_{ij}$,

  3. 3.

Traceless for $i>0$: $B_{0}=1\\!\mathrm{l}/\sqrt{d}$ and
$\mathrm{Tr}(B_{i})=0\ \forall\ i>0$.

Here, $1\\!\mathrm{l}$ is the $d$-dimensional identity map. For a single
qubit, the normalized Pauli matrices
$\left\\{1\\!\mathrm{l}/\sqrt{2},\sigma_{x}/\sqrt{2},\sigma_{y}/\sqrt{2},\sigma_{z}/\sqrt{2}\right\\}$
constitute just such a basis. For $n$ qubits, the $n$-fold tensor products of
the Pauli operators satisfy these conditions.

Since states and effects are both Hermitian, choosing a Hermitian basis makes
it easy to represent states and effects in the $d^{2}$-dimensional _real_
subspace of $\mathcal{B}(\mathcal{H})$ containing Hermitian operators. This
trivializes the adjoint ($\dagger$) operation. We abuse notation slightly by
using “Hilbert-Schmidt space” and $\mathcal{B}(\mathcal{H})$ to denote this
real vector space, because we almost never use its complex extension.

We conclude with a brief observation about notation and representation of
matrices. Conventionally, states ($\rho$) and effects ($E$) are represented
and thought of as _matrices_. Matrices are closed under linear combination, so
they form a vector space – but they can also be multiplied. However,
multiplication is not especially relevant for states and effects. When it
appears [e.g., in Born’s Rule via $\mathrm{Tr}(E\rho)$], its role can be
filled by the Hilbert-Schmidt dot product. This allows us to represent states
and effects just as _vectors_ in $\mathcal{B}(\mathcal{H})$. As we explain in
the next section, operators that act on $\mathcal{B}(\mathcal{H})$ are called
_superoperators_. So, generalizing Dirac’s notation, we refer to
$|\rho\rangle\\!\rangle$ as a _superket_ and to $\langle\\!\langle E|$ as a
_superbra_.

####  II.1.3 Quantum logic gates

What happens between the beginning of a quantum circuit (initialization into a
state $\rho$) and its end (a measurement $\\{E_{i}\\}$), is defined by a
sequence of circuit layers (Figure 1a). Because we treat each circuit layer as
a unique and independent “gate” (cf. Sec. II.1.1), the middle portion of a
circuit can be seen as a sequence of _quantum logic gates_ (Figure 1b). Gates
are dynamical transformations on the set of quantum states. An _ideal_ quantum
logic gate is reversible and corresponds to a unitary transformation of
$\mathcal{H}$. Such a gate would transform $\rho$ as $\rho\to U\rho
U^{\dagger}$ for some $d\times d$ unitary matrix $U$. This is a linear
transformation from $\mathcal{B}(\mathcal{H})$ to itself, and is called a
_superoperator_. The superoperator describing an ideal (unitary) gate is
_orthogonal_. 222To be clear, the $d\times d$ unitary matrix $U$ is not a
superoperator – it’s an operator. The linear transformation $\rho\to U\rho
U^{\dagger}$ acting on Hilbert-Schmidt space is the superoperator.

Real logic gates are noisy, and not perfectly reversible. They still act
linearly on states, so they can be represented by superoperators on
$\mathcal{B}(\mathcal{H})$. But the superoperators for noisy gates are not
orthogonal, and are generally contractive. These superoperators are known as
_quantum processes_ or _quantum channels_. Given any superoperator $\Lambda$,
we can represent it as a $d^{2}\times d^{2}$ matrix that acts associatively
(by left multiplication) on
$|\rho\rangle\\!\rangle\in\mathcal{B}(\mathcal{H})$, by just choosing a basis
for $\mathcal{B}(\mathcal{H})$. This representation is often called the
_transfer matrix_ of $\Lambda$. We adopt this terminology, and denote it by
$\mathsf{S}_{\Lambda}$. Thus, we write

$\Lambda:|\rho\rangle\\!\rangle\mapsto\mathsf{S}_{\Lambda}|\rho\rangle\\!\rangle,$
(1)

where the column vector $\mathsf{S}_{\Lambda}|\rho\rangle\\!\rangle$ is
obtained by multiplying the column vector $|\rho\rangle\\!\rangle$ from the
left by the matrix $\mathsf{S}_{\Lambda}$. If $\rho$ is prepared, and then
$\Lambda$ is performed, and finally $\\{E_{i}\\}$ is measured, then the
probability of outcome $i$ is

$p_{i}=\langle\\!\langle
E_{i}|\mathsf{S}_{\Lambda}|\rho\rangle\\!\rangle=\mathrm{Tr}(E_{i}\mathsf{S}_{\Lambda}\rho).$
(2)

Not every linear superoperator describes a physically allowed operation. For
example, the summed-up probability of all measurement outcomes is given by
$\mathrm{Tr}(\rho)$, so $\mathrm{Tr}(\rho)$ must equal 1. A superoperator
$\Lambda$ that changes $\mathrm{Tr}(\rho)$ violates the law of total
probability. So only _trace-preserving_ superoperators are physically allowed.
Furthermore, if $\rho$ is not positive semidefinite, then some outcome of some
measurement will have negative probability. So states must satisfy $\rho\geq
0$. If there exists any $\rho\geq 0$ such that $\Lambda(\rho)$ is _not_ $\geq
0$, then that $\Lambda$ is not physically possible. A superoperator that
preserves $\rho\geq 0$ is called _positive_.

However, a stronger condition is actually required: when $\Lambda$ acts on
_part_ of a larger system, it must preserve the positivity of that extended
system. This corresponds to requiring $\Lambda\otimes
1\\!\mathrm{l}_{\mathcal{A}}$ to be positive for any _auxiliary_ state space
$\mathcal{A}$, and is called _complete positivity_ Choi (1975); Kraus (1983).
It is stronger than simple positivity; some positive maps aren’t completely
positive. Superoperators representing physically possible operations must be
_completely positive and trace-preserving_ (CPTP). The CPTP constraint turns
out to be both necessary _and_ sufficient; any CPTP superoperator can be
physically implemented given appropriate resources by the _Stinespring
dilation_ construction Nielsen and Chuang (2000).

The TP (trace-preserving) condition is easy to describe and impose in the
transfer matrix representation; it corresponds to $\langle\\!\langle
1\\!\mathrm{l}|\mathsf{S}_{\Lambda}=\langle\\!\langle 1\\!\mathrm{l}|$. If
$\mathsf{S}_{\Lambda}$ is written in a basis whose elements are traceless
except for the first one (as required earlier), then $\Lambda$ is TP if and
only if the first row of $\mathsf{S}_{\Lambda}$ equals $[1,0\ldots 0]$.

The CP condition is more easily described in a different representation, the
_operator sum representation_ Choi (1975); Kraus (1983):

$\Lambda:\rho\mapsto\sum_{ij}\chi^{\Lambda}_{ij}B_{i}\rho B_{j}^{\dagger}.$
(3)

Here, $\left\\{B_{i}\right\\}$ is a basis for $\mathcal{B}(\mathcal{H})$, and
$\chi^{\Lambda}_{ij}$ is a matrix of coefficients called the “Choi process
matrix” that represents $\Lambda$. This _Choi representation_ of $\Lambda$
provides the same information as the transfer matrix $S_{\Lambda}$. The
mapping between them is known as the Choi-Jamiolkowski isomorphism Cho :

$\chi^{\Lambda}=d(\mathsf{S}_{\Lambda}\otimes
1\\!\mathrm{l})|\Pi_{\mathrm{EPR}}\rangle\\!\rangle,$ (4)

where
$\Pi_{\mathrm{EPR}}=|\Psi_{\mathrm{EPR}}\rangle\langle\Psi_{\mathrm{EPR}}|$
and $|\Psi_{\mathrm{EPR}}\rangle$ is a maximally entangled state on a space
that is the tensor product of $\mathcal{B}(\mathcal{H})$ and a reference
auxiliary space of equal dimension. Note that Eq. 4 is technically
problematic: the right hand side is a super-ket, but the left hand side is a
matrix. Equality here means that, in a consistent basis, these two objects are
element-wise equal. This element-wise equality is the Choi-Jamiolkowski
isomorphism. _Krauss operators_ correspond to the eigenvectors of
$\chi^{\Lambda}$, and provide an intuitive picture of many common
superoperatorsNielsen and Chuang (2000).

The CP condition is elegant and simple in the Choi representation: $\Lambda$
is CP if and only if $\chi$ is positive semidefinite. This condition is
independent of the basis $\\{B_{i}\\}$ used to define $\chi$.

Hereafter, we use the transfer matrix representation almost exclusively, and
so we use the term “superoperator” to also refer to the superoperator’s
transfer matrix. Likewise, when we refer to a superoperator’s matrix
representation, this should be understood to be the transfer matrix. When we
use the Choi matrix representation (only to test/impose complete positivity),
we will state it explicitly. We use the term “quantum operation”
interchangeably with “gate” to refer to _general_ quantum operations (not
necessarily CP or TP), and will explicitly state when CP and/or TP conditions
are assumed.

####  II.1.4 Gate sets

Prior to GST, tomographic protocols sought to reconstruct individual logic
operations – states, gates, or measurements – in isolation. But in real qubits
and quantum processors, this isolation isn’t possible. Every processor has
initial states, gates, _and_ measurements, and characterizing any one of them
requires making use of the others. Underlying GST, RB, robust phase estimation
Kimmel et al. (2015), and other modern QCVV protocols is the simultaneous
representation of _all_ a processor’s operations as a single entity – a _gate
set_.

Most processors provide just one native state preparation and one native
measurement. Gates are used to prepare other states and perform other
measurements. For completeness, we consider the most general situation here.
Consider a processor that can perform $N_{\mathrm{G}}$ distinct gates,
$N_{\rho}$ distinct state preparations, and $N_{\mathrm{M}}$ distinct
measurements, and where the $m$-th measurement has $N^{(m)}_{\mathrm{E}}$
distinct outcomes. We define the following representations for those
operations:

$\displaystyle G_{i}:\mathcal{B}(\mathcal{H})\to\mathcal{B}(\mathcal{H})$ for
$\displaystyle i=1\ldots N_{\mathrm{G}},$
$\displaystyle|\rho^{(i)}\rangle\\!\rangle\in\mathcal{B}(\mathcal{H})$ for
$\displaystyle i=1\ldots N_{\rho},\mbox{ and}$ (5)
$\displaystyle\langle\\!\langle E^{(m)}_{i}|\in\mathcal{B}(\mathcal{H})^{*}$
for $\displaystyle m=1\ldots N_{\mathrm{M}},\,i=1\ldots N^{(m)}_{\mathrm{E}}.$

The collective set of symbols $G_{i}$, $|\rho^{(i)}\rangle\\!\rangle$, and
$\langle\\!\langle E^{(m)}_{i}|$ serve two distinct roles. First, by simply
naming a set of operations, they provide a specification of the quantum
processor’s capabilities. Secondly, each symbol represents a mathematical
_model_ for the behavior (ideal, estimated, or unknown, depending on context)
of the physical hardware device when the corresponding operation is performed
in a quantum circuit. The notation given above is used throughout this paper.
We refer to all these matrices and vectors collectively as a _gate set_ ,
denoted by $\mathcal{G}$, and defined as

$\mathcal{G}=\left\\{\left\\{|\rho^{(i)}\rangle\\!\rangle\right\\}_{i=1}^{N_{\rho}};\left\\{G_{i}\right\\}_{i=1}^{N_{\mathrm{G}}};\left\\{\langle\\!\langle
E^{(m)}_{i}|\right\\}_{m=1,i=1}^{N_{\mathrm{M}},N^{(m)}_{\mathrm{E}}}\right\\}.$
(6)

A gate set is a complete model and description of a quantum processor’s
behavior when running quantum circuits.

A gate set is more than just a convenient way to package together independent
gate, preparation, and measurement operations. The operations on a quantum
processor that a gate set describes are _relational and inter-dependent_. As a
consequence, the representation given above – where gates correspond to
$d^{2}\times d^{2}$ superoperators, state preparations to $d^{2}$-element
column vectors, and POVM effects to $d^{2}$-element row vectors – is an _over-
specification_ of the gate set. To see this, consider a transformation of the
gate set that acts as

$\displaystyle\langle\\!\langle E^{(m)}_{i}|$ $\displaystyle\to$
$\displaystyle\langle\\!\langle E^{(m)}_{i}|M^{-1}$
$\displaystyle|\rho^{(i)}\rangle\\!\rangle$ $\displaystyle\to$ $\displaystyle
M|\rho^{(i)}\rangle\\!\rangle$ $\displaystyle G_{i}$ $\displaystyle\to$
$\displaystyle MG_{i}M^{-1},$ (7)

where $M$ is any invertible superoperator. This transformation changes the
concrete representation of the gate set, but does not change any observable
probability (cf. Eq.10). Since absolutely nothing observable has changed,
these are equivalent descriptions or representations of the same physical
system.

The transformations defined by Eq. 7 form a continuous group, so the standard
representation of gate sets described above contains entire “orbits” of
equivalent gate sets. This degeneracy, referred to generically as “gauge
freedom”, is a perennial irritant and obstacle to characterization of quantum
processors Blume-Kohout et al. (2017a); Proctor et al. (2017); Lin et al.
(2019b); Matteo et al. (2020). More importantly, it shows that a gate set is
not just the sum of its parts, and that tomography on a gate set is not just
tomography on its components. GST is tomography of a novel entity.

####  II.1.5 Circuits

The term “quantum circuit” is used in many contexts to mean subtly different
things. For clarity, we find it helpful to distinguish two related but
distinct types of quantum circuits: fixed-input, classical-output (FI/CO) and
quantum-input, quantum-output (QI/QO) circuits.

Data for standard QCVV protocols – e.g., state/process tomography, RB, or GST
– consists of the counted outcomes of experiments. Each experiment is
described by a quantum circuit that begins by initializing and ends by
measuring of all the qubits. Because the input to such a circuit is “fixed” by
the state preparation and the output of the circuit is classical measurement
data, we call this type of circuit a _fixed-input classical-output circuit_. A
FI/CO circuit represents and describes a probability distribution over
classical bit strings, and a more-or-less concrete procedure for generating it
with a quantum processor.

A quantum circuit can _also_ describe an arrangement of unitary logic gates,
with no explicit initialization or measurement, that could be inserted into a
larger circuit as a subroutine. We call this kind of circuit a _quantum-input
quantum-output circuit_. It is a sequence of circuit layer operations, none of
which are preparation or measurement layers. A QI/QO circuit represents and
describes a quantum channel that maps an input quantum state to an output
quantum state.

Thus, each FI/CO circuit comprises (1) one of the $N_{\rho}$ possible state
preparations, (2) a QI/QO circuit (a sequence of layers), and (3) one of the
$N_{m}$ measurements, which generates a specific outcome. On a processor that
has just one state preparation and one measurement operation, every FI/CO
circuit can be described completely by the QI/QO circuit composed of all its
circuit layers.

Let $\gamma$ be an index (or label) for available circuit layers (gates). When
we define a QI/QO circuit $S$ as $S=(\gamma_{1},\gamma_{2},...\gamma_{L})$, it
means “do layer $\gamma_{1}$, then do gate $\gamma_{2}$, etc.” When the layer
indexed (labeled) by $\gamma$ is performed, it transforms the quantum
processor’s state. This transformation is represented by a superoperator
$G_{\gamma}$. Performing an entire QI/QO circuit, e.g. $S$, also applies a
superoperator. We denote the transfer matrix for QI/QO circuit $S$ by
$\tau(S)$. It denotes the map from
$\mathcal{B}(\mathcal{H})\to\mathcal{B}(\mathcal{H})$ formed by composing the
elements of $S$, i.e., $\tau(S)=G_{\gamma_{L}}\cdots
G_{\gamma_{2}}G_{\gamma_{1}}$. Because it is a common source of confusion, we
emphasize that gates appear in chronological order in layer sequences ($S$),
but in reverse chronological order in matrix products $\tau(S)$, because
that’s how matrix multiplication works. For later reference, the general
action of $\tau$ on a layer sequence can be written

$\tau\left((\gamma_{1},\gamma_{2},...\gamma_{L})\right)=G_{\gamma_{L}}\cdots
G_{\gamma_{2}}G_{\gamma_{1}},$ (8)

where $1\leq\gamma_{i}\leq N_{\mathrm{G}}$ is an integer index into the set
$\left\\{G_{i}\right\\}_{i=1}^{N_{\mathrm{G}}}$ of corresponding gates
(quantum processes). We use integer exponentiation of a QI/QO circuit to
denote repetition. So, if $S=(\gamma_{1},\gamma_{2})$ then
$S^{2}=SS=(\gamma_{1},\gamma_{2},\gamma_{1},\gamma_{2})$. It follows that

$\tau(S^{n})=\tau(S)^{n}.$ (9)

Data sets are generated by defining a set of FI/CO circuits, repeating each
one $N$ times, and recording the results. Results from each specific circuit
are summarized by observed frequencies, $f_{k}=n_{k}/N$, where $n_{k}$ is the
number of times the $k$th measurement outcome was observed, for $k=1\ldots
N^{(m)}_{\mathrm{E}}$. These frequencies are usually close to their
corresponding probabilities,

$f_{k}\approx\langle\\!\langle E^{(m)}_{k}|G_{\gamma_{L}}\cdots
G_{\gamma_{2}}G_{\gamma_{1}}|\rho^{(i)}\rangle\\!\rangle\quad\forall k,$ (10)

and can be used to estimate them. More sophisticated estimators exist, but Eq.
10 motivates the idea that some or all of $|\rho^{(i)}\rangle\\!\rangle$,
$\langle\\!\langle E^{(m)}_{k}|$ and $G_{j}$ can be inferred from the observed
frequencies. Doing so is tomography. Each kind of tomography treats some
operations as known, and uses them as a reference frame to estimate the
others.

It is usually apparent from context whether a FI/CO or QI/QO circuit is being
referenced. In the remainder of this paper, we only specify the type of
circuit in cases when it may be ambiguous.

###  II.2 State, Process, and Measurement Tomography

In this section we review standard state and process tomography. We also
briefly describe the (straightforward) generalization to measurement
tomography. These methods establish the context for GST, but they also
introduce the mathematical machinery and notation that we will use for GST.

Figure 2: Structure of the circuits required for state, process, and
measurement tomography. Each of these protocols reconstructs an unknown entity
(a state $\rho$, process $G$, or measurement $\mathrm{M}$) by placing that
entity in circuits with an assumed-known reference frame formed by an
informationally complete set of state preparations or measurements (or both).
Primed symbols ($\rho^{\prime}$ and $\mathrm{M}^{\prime}$) are meant to
connote _effective_ state preparations and measurements, which are often
implemented by applying gate operations after or before a native state
preparation or measurement. A critical problem with these standard tomographic
techniques is that $\rho^{\prime}$ and $\mathrm{M}^{\prime}$ are in practice
never known exactly.

####  II.2.1 Quantum state tomography

The goal of quantum state tomography Gale et al. (1968); Vogel and Risken
(1989); Hradil (1997); Munro et al. (2001); James et al. (2001); Artiles et
al. (2005); Blume-Kohout (2010a, b); Christandl and Renner (2012); Smolin et
al. (2012); Banaszek et al. (2013); Granade et al. (2016); Haah et al. (2017)
is to construct a full description of a quantum state $\rho$, from
experimental data. It is assumed that some quantum system can be repeatedly
prepared in the unknown state $\rho$, that various _fiducial measurements_ can
be performed on it, that those measurements are collectively _informationally
complete_ , and that the POVMs representing those measurements are _known_
(see Figure 2).

“Fiducial” means “accepted as a fixed basis of reference”, and the
measurements used in state tomography constitute a frame of reference. A set
of measurements $\\{E^{(m)}_{i}\\}_{m,i}$ is informationally complete if and
only if, for any state $\rho$, the probabilities

$p^{(m)}_{i}(\rho)=\mathrm{Tr}\left[\rho E^{(m)}_{i}\right]$

_uniquely_ identify $\rho$ – i.e., there is no other $\rho$ consistent with
them. This implies a simple linear-algebraic condition: the
$\\{E^{(m)}_{i}\\}$ must span the entire space of effects, forming a complete
dual basis for states.

To perform state tomography, many copies of $\rho$ are made available, and
divided into $M$ pools. The $m$th fiducial measurement is applied to all the
copies in the $m$th pool. The observed frequencies $f^{(m)}_{i}$ are recorded,
and used to estimate the corresponding probabilities

$p^{(m)}_{i}(\rho)=\mathrm{Tr}\left[\rho E^{(m)}_{i}\right].$

Then $\rho$ is deduced from these probabilities.

Practical state tomography is more complicated (and interesting) because only
finitely many copies can be measured, so each observed frequency isn’t
generally equal to the corresponding probability. Those probabilities have to
be _estimated_ from the data. One option is to estimate $\hat{p}_{i}=f_{i}$
(where $\hat{\cdot}$ over a variable indicates an estimate). This is called
_linear inversion_. It’s not very accurate, and often yields an estimate
$\hat{\rho}$ that isn’t positive, but despite these practical drawbacks it’s a
theoretical cornerstone of tomography. Linear inversion underlies the concept
of informational completeness, which captures whether an experiment design
(here, a set of measurements) is sufficient for estimation. These ideas also
underly GST, and are used directly in linear GST. So we now present a concise
overview of linear inversion state tomography and informational completeness.

Let the Hilbert-Schmidt space vector $|\rho\rangle\\!\rangle$ denote an
unknown quantum state that we want to reconstruct. Let
$\\{E^{(m)}_{i}\\}_{m,i}$ represent the set of $M$ _known_ fiducial
measurements, indexed by $m=1\ldots M$, with $i=1\ldots N^{(m)}$ indexing the
outcomes of the $m$th measurement. We represent each of these effects as a
dual vector $\langle\\!\langle E^{(m)}_{i}|$ in Hilbert-Schmidt space. Only
the list of effects matters, not which measurement $m$ a given effect
$E^{(m)}_{i}$ belongs to, so we simply list all the effects as $\\{E_{j}:\
j=1\ldots N_{f1}\\}$, where $N_{f1}$ is the total number of distinct
measurement outcomes for _all_ measurements performed.

Now, let us assume that we have learned the exact probabilities of each
measurement outcome in state $\rho$ (ignoring the entire process of performing
measurements on samples, collating the results, and estimating probabilities
from frequencies). These probabilities are given by Born’s rule,

$p_{j}=\mathrm{Tr}\left[E_{j}\rho\right].$ (11)

We can we write this as a Hilbert-Schmidt space inner product,

$p_{j}=\langle\\!\langle E_{j}|\rho\rangle\\!\rangle,$ (12)

and then stack all the row vectors $\langle\\!\langle E_{j}|$ atop each other
to form an $N_{f1}\times d^{2}$ matrix

$A=\left(\begin{array}[]{c}\langle\\!\langle E_{1}|\\\ \langle\\!\langle
E_{2}|\\\ \vdots\\\ \langle\\!\langle E_{N_{f1}}|\\\ \end{array}\right).$ (13)

Now, $\vec{p}=A|\rho\rangle\\!\rangle$ is a vector whose $j$th element is
$p_{j}$ (the probability of $E_{j}$, as defined above). In the context of
state tomography, all the measurement effects $E_{j}$ are assumed to be known
_a priori_ , so the entire matrix $A$ is known. $A$ also has full column rank
($d^{2}$), because the $\\{\langle\\!\langle E^{(m)}_{i}|\\}$ are
informationally complete and therefore span Hilbert-Schmidt space. Therefore,
we can reconstruct $\rho$ using linear algebra. If $A$ is square, it has an
inverse, and $|\rho\rangle\\!\rangle=A^{-1}\vec{p}$. If $N_{f1}$ is greater
than $d^{2}$, then the $\\{\langle\\!\langle E^{(m)}_{i}|\\}$ form an
overcomplete basis and $A$ is not square. In this case, we can solve for
$|\rho\rangle\\!\rangle$ using a pseudo-inverse:

$|\rho\rangle\\!\rangle=(A^{T}A)^{-1}A^{T}\vec{p}.$ (14)

####  II.2.2 Quantum process tomography

The goal of quantum process tomography Poyatos et al. (1997); Chuang and
Nielsen (1997); Fiurášek and Hradil (2001); D’Ariano and Lo Presti (2001);
Childs et al. (2001); Altepeter et al. (2003); O’Brien et al. (2004);
Weinstein et al. (2004); Mohseni and Lidar (2006); Riebe et al. (2006);
Bendersky et al. (2008); Lobino et al. (2008); Bialczak et al. (2010); Kimmel
et al. (2014a); Kim et al. (2014) is to construct a full description of a
quantum process (e.g., a gate) from experimental data. This is done by
constructing an informationally complete set of known _fiducial states_ ,
preparing many copies of each of them, passing those copies through the
process to be tomographed, and performing state tomography on the output
states (see Figure 2). All the same caveats and complications mentioned for
state tomography apply here. As above, we ignore them and focus on the
underlying math problem of reconstructing an unknown process from exactly
measured probabilities.

Let $G$ be the superoperator (transfer matrix) representing the process we
want to reconstruct. Let $\\{\langle\\!\langle E_{j}|\\}$ be the list of POVM
effects representing all the outcomes of all the fiducial measurements, as in
state tomography. And let $\\{|\rho_{i}\rangle\\!\rangle\\}$ be a list of
$N_{f2}$ fiducial quantum states that will be repeatedly prepared as inputs to
$G$.

If state $\rho_{i}$ is prepared, $G$ is applied, and a measurement is
performed with possible outcomes $\\{E_{j}\\}$, then the probability of
observing outcome $E_{j}$ is

$\displaystyle P_{j,i}$ $\displaystyle=$
$\displaystyle\mathrm{Tr}\left(E_{j}G[\rho_{i}]\right)$ (15) $\displaystyle=$
$\displaystyle\langle\\!\langle E_{j}|G|\rho_{i}\rangle\\!\rangle.$ (16)

In addition to the $A$ matrix defined previously, we define a new $d^{2}\times
N_{f2}$ matrix $B$ from the column vectors representing the fiducial states
$|\rho_{i}\rangle\\!\rangle$:

$B=\left(\begin{array}[]{cccc}|\rho_{1}\rangle\\!\rangle&|\rho_{2}\rangle\\!\rangle&\cdots|\rho_{N_{f2}}\rangle\\!\rangle\\\
\end{array}\right).$ (17)

Now, we can write the $N_{f1}\times N_{f2}$ matrix $P$ whose elements are
$P_{j,i}$ as

$P=AGB.$ (18)

In the context of process tomography, both the fiducial states and the
fiducial measurement effects are known, so all the elements of both $A$ and
$B$ are known. $A$ must have full column rank and $B$ must have full row rank,
because the $\\{\rho_{i}\\}$ and $\\{E_{j}\\}$ were assumed to be
informationally complete. If they are square ($N_{f1}=N_{f2}=d^{2}$), then
they are invertible, and we can immediately reconstruct the original process
as

$G=A^{-1}PB^{-1}.$ (19)

If there are more than $d^{2}$ input states and/or measurement outcomes, then
(as before) we use a pseudo-inverse to obtain a least-squares solution:

$G=(A^{T}A)^{-1}A^{T}PB^{T}(BB^{T})^{-1}.$ (20)

More sophisticated estimators – i.e., maps from $\\{p_{i,j}\\}$ data to
estimates of $G$ – exist. They are important when finite-sample errors in the
estimated probabilities are significant. But the linear inversion tomography
described here is the essence of process tomography.

####  II.2.3 Measurement tomography

Using tomographic techniques to characterize measurements gets much less
attention than state and process tomography – partly, perhaps, because it’s a
straightforward generalization of state tomography.

Measurement tomography Luis and Sánchez-Soto (1999); Fiurasek (2001); Lundeen
et al. (2009); Blumoff et al. (2016); Chen et al. (2019) uses pre-calibrated
fiducial states to reconstruct the POVM effects for an unknown measurement
(see Figure 2). This is easy to represent using the framework already
developed for process tomography. If $\\{\rho_{i}\\}$ are known fiducial
states, and $\\{E_{j}\\}$ is the unknown POVM, then we can define one vector
of observable probabilities $\vec{p_{j}}$ for each unknown effect:

$\displaystyle[p_{j}]_{i}$ $\displaystyle=$
$\displaystyle\mathrm{Tr}[\rho_{i}E_{j}]$ (21) $\displaystyle=$
$\displaystyle\langle\\!\langle E_{j}|\rho_{i}\rangle\\!\rangle.$ (22)

Using the $B$ matrix defined in the preceding discussion of process
tomography, this is simply

$\vec{p_{j}}^{T}=\langle\\!\langle E_{j}|B,$ (23)

which means that each effect $E_{j}$ can be reconstructed by linear inversion
as

$\langle\\!\langle E_{j}|=\vec{p_{j}}^{T}B^{-1},$ (24)

where $B^{-1}$ is a matrix inverse or pseudo-inverse, as appropriate.

###  II.3 The role of calibration in tomography

State, process, and measurement tomography are conceptually straightforward,
but rely on a critical (and unrealistic) assumption. They reconstruct the
unknown operation _relative_ to some reference operations – fiducial
measurements and/or states – that are assumed to be perfectly known. Often,
the reference operations are also assumed to be noiseless.

These assumptions are never satisfied in practice. Identifying the exact POVMs
that describe the fiducial measurements for state tomography – i.e.,
_calibrating_ them – would require perfectly known states. But identifying
those states, by state tomography, relies on known measurements. This leads to
an endless loop of self-referentiality. In the same way, process tomography
relies on fiducial states and measurements that are almost always produced by
applying quantum logic gates (specific quantum processes) to just a few native
states and measurements Takahashi et al. (2013). A process tomographer’s
knowledge of those fiducial objects can be no more precise than their
knowledge of the gates used to prepare them – which would have to be
characterized with process tomography.

Ref. Merkel et al., 2013 articulated this problem clearly. It also
demonstrated that this concern is real, and has practical consequences. In
realistic scenarios, errors in state preparation and measurement (SPAM)
dominate inaccuracy in process tomography.

Several forms of “calibration-free” tomography Brańczyk et al. (2012);
Mogilevtsev et al. (2012); Blume-Kohout et al. (2013); Medford et al. (2013);
Quesada et al. (2013a, b, c); Straupe et al. (2013); Stark (2014); Kimmel et
al. (2014b); Mohammadi and Brańczyk (2014); Schwemmer et al. (2015); Jackson
and Van Enk (2015); Hou et al. (2016); Chapman et al. (2016); Blume-Kohout et
al. (2017a); McCormick et al. (2017); Keith et al. (2018) were proposed either
independently from, or in response to, Ref. Merkel et al., 2013. Each sought
to characterize quantum gates, state preparations, and/or measurements self-
consistently _without_ any prior calibration. Gate set tomography has emerged
as the most widely adopted of these, and is now a _de facto_ standard for
performing calibration-free tomography. However, it comes with certain costs,
which have motivated the continued use of state and process tomography in some
experiments. While we recognize the costs and drawbacks of GST, the risks of
traditional state and process tomography are so clear that they should not be
used, except under remarkable circumstances (e.g., where there are very good
reasons to believe the reference operations are known to higher precision than
is needed in the final estimate).

##  III Linear gate set tomography (LGST)

GST offers two benefits. It resolves the circularity inherent to state and
process tomography, and achieves higher accuracy with lower experimental cost
than process tomography. These features are only loosely linked. Linear GST
(LGST) resolves the pre-calibration problem, but has the same accuracy/effort
scaling as process tomography. In this section, we use LGST to introduce the
basic concepts and methods of GST.

###  III.1 Introduction to LGST

Linear-inversion gate set tomography (LGST) is basically a calibration-free
amalgamation of state, process, and measurement tomography. It constructs a
low-precision estimate of a gate set $\mathcal{G}$ using the data from a
specific set of short circuits. LGST demonstrates the feasibility of avoiding
pre-calibrated reference frames, and also why doing so creates gauge freedom.

LGST was developed roughly contemporaneously with IBM’s “overkill” approach to
gate set tomography Merkel et al. (2013). IBM identified the pre-calibration
problem, recognized that circuit outcome probabilities are given by
expressions of the form $p_{S}=\langle\\!\langle
E|G\ldots|\rho\rangle\\!\rangle$, and observed that a sufficiently large set
of such probabilities should be sufficient to reconstruct the gate set. They
proposed performing _all_ circuits of 3 or fewer gates to generate data, then
fitting a gate set to that data by numerical maximization of the likelihood
function (maximum likelihood estimation, or MLE)

$\mathcal{L}(\mathcal{G})=\mathrm{Pr}(\mathrm{data}|\mathcal{G}).$ (25)

But this likelihood function is not well-behaved. It is not quasi-convex
(i.e., its level sets are not convex), because (1) the probabilities for the
experimental observations are not linear functions of the parameters, and (2)
the existence of the gauge makes the likelihood’s maximum very degenerate.
Plotting the likelihood would reveal, instead of a unimodal “hill”, an
assortment of winding “ridges” with perfectly level crests. Standard
optimization methods Boyd and Vandenberghe (2004) often fail to find global
maxima on such functions, getting stuck in local maxima. The IBM “overkill”
algorithm therefore relied on starting with a good initial guess for the gate
set, that would lie with high probability in a local neighborhood of the
likelihood’s maximum.

LGST avoids this problem by using a very different, structured, experiment
design. Instead of an unstructured set of short circuits, LGST prescribes a
specific set of them. The resulting data can be analyzed using only linear
algebra, and the analysis is very similar to that used for process tomography.

As LGST looks very much like process tomography, it’s important to recognize
that it is doing something significantly different. If LGST _was_ trying to
reconstruct transfer matrices for individual gates, it would fail, because
reconstructing individual gates without a pre-calibrated reference frame is
not possible. LGST reconstructs gates _up to gauge freedom_. Actually, it does
more – it reconstructs the entire gate set up to the _global_ gauge freedom
given in Eq. 7, recapitulated below:

$\displaystyle\langle\\!\langle E^{(m)}_{i}|$ $\displaystyle\to$
$\displaystyle\langle\\!\langle E^{(m)}_{i}|M^{-1}$
$\displaystyle|\rho^{(i)}\rangle\\!\rangle$ $\displaystyle\to$ $\displaystyle
M|\rho^{(i)}\rangle\\!\rangle$ (26) $\displaystyle G_{i}$ $\displaystyle\to$
$\displaystyle MG_{i}M^{-1}.$

Such transformations change the elements of the gate set, but not any
observable probability. So it’s not possible to distinguish between gauge-
equivalent gate sets, and reconstructing a gate set up to arbitrary $M$
constitutes success.

Since a gate set comprises states, gates, and measurements, it’s tempting to
say that LGST characterizes all of them simultaneously. But this is not quite
right. A gate set is not a collection of _unrelated_ quantum operations.
Quantum operations are usually described relative to an implicit and absolute
reference frame. But in most experiments, no such reference frame is
available. So GST characterizes all these operations _relative to each other_
, and estimates every property of a gate set that _can_ be measured without a
reference frame. But some properties of gate sets can’t be measured, even in
principle, and they correspond to gauge degrees of freedom.

Gauge freedom makes some familiar properties of gates unmeasurable. Other
properties of gates turn out to be not associated with a single operation, but
purely _relational_ properties – i.e., they are properties of the gate set,
but not of any individual gate within it. This awkwardness is the unavoidable
price of avoiding pre-calibrated reference frames. GST outputs a self-
consistent representation of the available states, processes, and
measurements, _but that representation is generally not unique_. If finite-
sample errors did not exist, LGST would be a perfect estimator of the gate
set, and this paper would be much shorter. But real experiments always suffer
from finite sample error. $N$ trials of an event with probability $p$ does
_not_ generally yield exactly $pN$ successes, so estimating $p$ from data
generally yields $\hat{p}=p\pm O(1/\sqrt{N})$. As a result, LGST’s estimation
error scales as $O(1/\sqrt{N})$, just like process tomography. So estimating a
gate set to within $\pm 10^{-5}$ with LGST would require repeating each
circuit $N\approx 10^{10}$ times, which is impractical. The “long-sequence
GST” protocol described in Section IV is much more efficient, and makes
standalone LGST preferable only when there are severe resource constraints.
But LGST remains important both pedagogically and as a key first step in long-
sequence GST’s analysis pipeline.

###  III.2 The LGST algorithm

In this section, we present the core LGST algorithm. We focus on (1) what LGST
seeks to estimate, (2) what data is required for LGST, and (3) how to
transform that data into an estimate under ideal circumstances. At first, we
make some idealized simplifying assumptions in order to maximize clarity.
After presenting the core algorithm, we return to these assumptions, relax
them, and show how to make this algorithm practical and robust. The
simplifying assumptions are:

  1. 1.

We assume the ability to create informationally complete sets of fiducial
states $\left\\{|\rho^{\prime}_{j}\rangle\\!\rangle\right\\}$ and measurement
effects $\left\\{\langle\\!\langle E^{\prime}_{i}|\right\\}$ (see Section
III.4).

  2. 2.

We ignore finite sample error in estimated probabilities, and its effects (see
Section III.5).

  3. 3.

We assume that the fiducial states and effects are exactly informationally
complete, not overcomplete, so that $N_{f1}=N_{f2}=d^{2}$ (see Section III.3).

We use the notation of Eq. 6 to denote the contents of a generic gate set
$\mathcal{G}$:

$\mathcal{G}=\left\\{\left\\{|\rho^{(i)}\rangle\\!\rangle\right\\}_{i=1}^{N_{\rho}};\left\\{G_{i}\right\\}_{i=1}^{N_{\mathrm{G}}};\left\\{\langle\\!\langle
E^{(m)}_{i}|\right\\}_{m=1,i=1}^{N_{\mathrm{M}},N^{(m)}_{\mathrm{E}}}\right\\}.$
(27)

As in Sec. II.1.4, $N_{\rho}$, $N_{\mathrm{G}}$ and $N_{\mathrm{M}}$ are the
number of distinct state preparations, gates, and measurements, and
$N^{(m)}_{\mathrm{E}}$ is the number of possible outcomes for the $m$-th
distinct measurement.

Figure 3: Structures of the two types of circuits required by the LGST
algorithm. Upper panel: Each native gate, $G_{i}$, is sandwiched between the
elements of informationally complete sets of _effective state preparations_ ,
$\\{\rho^{\prime}\\}$, and of _effective measurements_ ,
$\\{\mathrm{M}^{\prime}\\}$. These are the same circuits that process
tomography requires to characterize $G_{i}$. Line (a) shows these circuits in
their simplest form, with each informationally complete set displayed as a
unit. Line (b) depicts the common case when the set of effective preparations
(measurements) is implemented by following (preceding) a single native
preparation (measurement) operation with a _fiducial circuit_ $F$ ($H$), see
Eqs. 52 and 53. Line (c) makes it clear that the fiducial circuits are
composed of native gates, and gives the circuit entirely in terms of native
operations. Lower panel: Because LGST does not assume knowledge of the
$\rho^{\prime}$ and $\mathrm{M}^{\prime}$, it requires circuits that sandwich
nothing between pairs of fiducials in order to be self-calibrating. The
circuit diagrams in lines (d), (e), and (f) parallel those in (a)-(c). LGST
also requires the circuits that perform state (measurement) tomography on
$\rho$ ($\mathrm{M}$), but these are not explicitly shown. They are similar to
(d)-(f) (just replace $\rho^{\prime}$ with $\rho$ or $\mathrm{M}^{\prime}$
with $\mathrm{M}$), and are actually included as a subset of these circuits
when the gate set contains only a single native state preparation
(measurement) and one of the preparation (measurement) fiducial circuits is
the empty (do-nothing) cirucit.

To perform process tomography on an operation $G$ in Sec. II.2.2, we
constructed a matrix $P$ of observable probabilities using informationally
complete fiducial states and effects. For LGST, we will do the same thing. But
although we assume the existence and implementability of fiducial sets, we do
_not_ assume that we know them. They still form a reference frame, but we
don’t know what that frame is.

To reconstruct a _set_ of gates (processes) $\\{G_{k}\\}$, we will need one
such matrix $P_{k}$ for each gate:

$[P_{k}]_{i,j}=\langle\\!\langle
E^{\prime}_{i}|G_{k}|\rho^{\prime}_{j}\rangle\\!\rangle.$ (28)

These probabilities are directly measurable – we don’t know what
$\rho^{\prime}_{j}$ and $E^{\prime}_{i}$ are, but we can prepare/measure them.
The first line of Figure 3 illustrates the circuit corresponding to Eq. 28.

We can construct $A$ and $B$ matrices from the fiducial vectors exactly as for
process tomography. The difference, of course, is that although those matrices
exist, their entries are not known to the tomographer. Just as before, we can
write

$P_{k}=AG_{k}B.$ (29)

Since we do not know $A$ or $B$, we cannot solve this equation for $G_{k}$.
Instead, to compensate for our ignorance about $\rho^{\prime}_{j}$ and
$E^{\prime}_{i}$, we measure some additional probabilities that correspond to
process tomography on the null operation. We arrange these into a _Gram
matrix_ for the fiducial states/effects:

$\tilde{1\\!\mathrm{l}}_{i,j}=\langle\\!\langle
E^{\prime}_{i}|\rho^{\prime}_{j}\rangle\\!\rangle.$ (30)

The second line of Figure 3 depicts the circuits whose outcome probabilities
make up $\tilde{1\\!\mathrm{l}}$. This matrix can also be written in terms of
the $A$ and $B$ matrices, as

$\tilde{1\\!\mathrm{l}}=AB.$ (31)

We assumed that these matrices are square ($N_{f1}=N_{f2}=d^{2}$) and
invertible (which follows from informational completeness). So we can invert
the Gram matrix to get $\tilde{1\\!\mathrm{l}}^{-1}=B^{-1}A^{-1},$ multiply
Eq. 29 on the left by it,

$\tilde{1\\!\mathrm{l}}^{-1}P_{k}=B^{-1}G_{k}B,$ (32)

and solve for $G_{k}$ to get

$G_{k}=B\tilde{1\\!\mathrm{l}}^{-1}P_{k}B^{-1}.$ (33)

This may not look like the solution – there’s still an unknown $B$ involved –
but it is. We’ve reconstructed $G_{k}$ _up to a similarity transformation_ by
the unknown $B$. Moreover, we can do this in exactly the same way for _all_
the gates $G_{k}$, and get estimates of them all up to the _same_ $B$.

We also need to reconstruct the native states $\rho^{(l)}$ and measurement
effects $\\{E_{l}^{(m)}\\}$ in the gate set. To do so, we construct the
following vectors (denoted by $\vec{\cdot}$) of observable probabilities:

$\displaystyle\left[\vec{R}^{(l)}\right]_{j}$ $\displaystyle=$
$\displaystyle\langle\\!\langle E^{\prime}_{j}|\rho^{(l)}\rangle\\!\rangle$
(34) $\displaystyle\left[\vec{Q}^{(m)}_{l}\right]_{j}$ $\displaystyle=$
$\displaystyle\langle\\!\langle
E^{(m)}_{l}|\rho^{\prime}_{j}\rangle\\!\rangle.$ (35)

Measuring these probabilities corresponds to performing state tomography on
each native state $\rho^{(l)}$, and measurement tomography on every native
effect $\\{E_{l}^{(m)}\\}$ – in the unknown frame defined by the fiducial
effects and states. They can be written using $A$ and $B$ as

$\displaystyle\vec{R}^{(l)}$ $\displaystyle=$ $\displaystyle
A|\rho^{(l)}\rangle\\!\rangle$ (36) $\displaystyle\vec{Q}_{l}^{(m)T}$
$\displaystyle=$ $\displaystyle\langle\\!\langle E^{(m)}_{l}|B,$ (37)

and by using the identity $\tilde{1\\!\mathrm{l}}=AB$ in Eq. 36, we get the
following equations for _all_ the elements of the gate set:

$\displaystyle G_{k}$ $\displaystyle=$ $\displaystyle
B\tilde{1\\!\mathrm{l}}^{-1}P_{k}B^{-1}$ (38)
$\displaystyle|\rho^{(l)}\rangle\\!\rangle$ $\displaystyle=$ $\displaystyle
B\tilde{1\\!\mathrm{l}}^{-1}\vec{R}^{(l)}$ (39)
$\displaystyle\langle\\!\langle E^{(m)}_{l}|$ $\displaystyle=$
$\displaystyle\vec{Q}^{(m)T}_{l}B^{-1}.$ (40)

Perhaps surprisingly, this is the answer – we’ve recovered the original gate
set _up to a gauge_. The unknown $B$ is now a gauge transformation (see Eq.
7). It’s not just unknown, but unknowable, and irrelevant. The tomographer can
set $B$ equal to _any_ invertible matrix and get back the original gate set,
up to gauge freedom. Equivalently, $B$ indexes different (but equivalent)
representations of the gate set. The simplest choice is $B=1\\!\mathrm{l}$,
but the resulting representation is not very useful. The best _a priori_
choice is to choose a $B$ corresponding to the tomographer’s best _a priori_
guess for the fiducial states (see Eq. 17), because that (implicitly) defines
the gauge in which the tomographer is expecting to work. But although this is
the best _a priori_ choice, it is almost never satisfactory. Reliable analysis
of the estimate requires _a posteriori_ gauge-fixing, which we discuss in
Section VI.2.

###  III.3 Addressing overcompleteness with pseudo-inverses

Although using exactly $N_{f1}=N_{f2}=d^{2}$ fiducial states and effects makes
the mathematics convenient, there are practical advantages to using more than
$d^{2}$ fiducials. They include

  * •

Redundancy: overcomplete fiducials provide more information and allow self-
consistency checking,

  * •

Precision: with some gate sets, such as Clifford gates, optimal fiducial sets
(2-designs) can only be generated with more than $d^{2}$ fiducials,

  * •

Feasibility: if only projective measurements with $d$ effects are used, then
at least $d+1$ of them are required for informational completeness, which
yields $d^{2}+d$ effects.

Overcomplete fiducials yield vector spaces of observable probabilities whose
dimension exceeds that of Hilbert-Schmidt space. The $A$, $B$, and (generally)
$P_{k}$ matrices are not square, and therefore not invertible. However, all
the steps from the previous derivation still hold – they just require slightly
more complicated linear algebra.

Let us return to the derivation at Eq. 29. We have measured all the
$N_{f1}\times N_{f2}$ elements of $P_{k}$ and $\tilde{1\\!\mathrm{l}}$, and we
want to solve for $G_{k}$ in these two equations:

$\displaystyle P_{k}$ $\displaystyle=$ $\displaystyle AG_{k}B$
$\displaystyle\tilde{1\\!\mathrm{l}}$ $\displaystyle=$ $\displaystyle AB.$

The elements of $P_{k}$ and $\tilde{1\\!\mathrm{l}}$ will experience small
random perturbations because of finite sample errors in estimates of
probabilities. So in general, these equations will have no exact solutions –
the rank of $P_{k}$ and $1\\!\mathrm{l}$ will be higher than $d^{2}$, but $AB$
can only have rank $d^{2}$ (because we demand reconstructed gates of this
dimension). Therefore, we seek the best _approximate_ solution. A simple and
elegant criterion for “best” (though not actually _the_ best criterion; see
“Maximum likelihood estimation” below) is least-squares. We seek the $G_{k}$
(and also $A$ and $B$) that minimize $|P_{k}-AG_{k}B|^{2}$ and
$|\tilde{1\\!\mathrm{l}}-AB|^{2}$.

To find $A$ and $B$, we start with the identity

$|\tilde{1\\!\mathrm{l}}-AB|^{2}=\mathrm{Tr}\left[\tilde{1\\!\mathrm{l}}^{T}\tilde{1\\!\mathrm{l}}-\tilde{1\\!\mathrm{l}}^{T}AB-B^{T}A^{T}\tilde{1\\!\mathrm{l}}+B^{T}A^{T}AB\right],$
(41)

differentiate with respect to $A$ (using the rule that
$\nabla_{A}\mathrm{Tr}[AX]=X^{T}$ and $\nabla_{A}\mathrm{Tr}[A^{T}X]=X$), set
the resulting gradient to zero and solve. This yields

$A=\tilde{1\\!\mathrm{l}}B^{T}(BB^{T})^{-1}.$ (42)

Some useful observations about this expression:

  * •

This is a valid generalization of the expression derived previously
($A=\tilde{1\\!\mathrm{l}}B^{-1}$), because $B^{T}(BB^{T})^{-1}$ is a right
inverse of $B$ – i.e., multiplying it on the left by $B$ yields
$1\\!\mathrm{l}$.

  * •

Furthermore, if $B$ is square and invertible, then this inverse is unique, so
this expression reduces to $A=\tilde{1\\!\mathrm{l}}B^{-1}$ in that case.

  * •

This inverse is well-conditioned. Although $B$ is generally singular, $BB^{T}$
is square and full-rank (by informational completeness).

Next, we write out $|P_{k}-AG_{k}B|^{2}$ the same way, take the gradient with
respect to $G_{k}$, set it to zero, and solve for $G_{k}$. This yields

$G_{k}=(A^{T}A)^{-1}A^{T}P_{k}B^{T}(BB^{T})^{-1},$ (43)

and substituting $A$ from Eq. 42 yields

$G_{k}=B\left[B^{T}\left(B\tilde{1\\!\mathrm{l}}^{T}\tilde{1\\!\mathrm{l}}\right)^{-1}B\right]\tilde{1\\!\mathrm{l}}^{T}P_{k}\left[B^{T}(BB^{T})^{-1}\right].$
(44)

This, again, is a valid generalization of the expression derived earlier
($G_{k}=B\tilde{1\\!\mathrm{l}}^{-1}P_{k}B^{-1}$). If $B$ is invertible, then
this entire expression reduces to the earlier one. But this expression _only_
requires inverting $d^{2}\times d^{2}$ matrices that have full rank if the
fiducials are informationally complete.

One problem remains; $B$ (which is still unknown) appears in the estimate. In
the previous derivation, where $B$ was assumed to be square and invertible, we
showed that although the final expression for $G_{k}$ involved $B$, it _only_
determined the gauge, and had no impact on any predicted probability.

In Eq. 44, this is not _quite_ true. $B$ does affect the estimate…but _only
through its support_. Recall that $B$’s dimensions are now $d^{2}\times
N_{f1}$. If the fiducial states are informationally complete, then $B$ has
rank $d^{2}$. Its columns span the entire $d^{2}$-dimensional state space, but
its rows only span a $d^{2}$-dimensional subspace of the $N_{f1}$-dimensional
space of observable probabilities.

We can write $B$ as $B=B_{0}\Pi$, where $\Pi$ is a $d^{2}\times N_{f1}$
projector onto _some_ $d^{2}$-dimensional subspace, and $B_{0}$ is an
arbitrary full-rank $d^{2}\times d^{2}$ matrix. Substituting this into Eq. 44
yields a remarkable simplification:

$G_{k}=B_{0}\left(\Pi\tilde{1\\!\mathrm{l}}^{T}\tilde{1\\!\mathrm{l}}\Pi^{T}\right)^{-1}\left(\Pi\tilde{1\\!\mathrm{l}}^{T}P_{k}\Pi^{T}\right)B_{0}^{-1}.$
(45)

Here, $B_{0}$ clearly determines the gauge and _only_ the gauge. $\Pi$, on the
other hand, has a real effect. What’s happening here is simple: the high-
dimensional information contained in the data ($\tilde{1\\!\mathrm{l}}$ and
$P_{k}$) has to be compressed into the lower-dimensional space of the estimate
$G_{k}$. The estimator is a linear map, so the only way to do this is by
projection, and $\Pi$ (the projector onto the support of $B$) is that
projection. So we are free to choose $B$ more or less arbitrarily (as long as
it has rank $d^{2}$) – but its support _will_ affect the estimate, while its
form on that support affects only the gauge.

To choose $\Pi$ optimally, we recall that $A$ and $B$ are chosen to minimize
$|\tilde{1\\!\mathrm{l}}-AB|^{2}$. If we write out $AB$ using Eq. 42 and the
identity $B=B_{0}\Pi$, we get

$AB=\tilde{1\\!\mathrm{l}}B^{T}(BB^{T})^{-1}B=\tilde{1\\!\mathrm{l}}\Pi^{T}\Pi,$
(46)

and if we define the complement projector
$\Pi_{c}=1\\!\mathrm{l}_{N_{f1}\times N_{f1}}-\Pi^{T}\Pi$, then

$|\tilde{1\\!\mathrm{l}}-AB|^{2}=\mathrm{Tr}\left[\Pi_{c}\tilde{1\\!\mathrm{l}}^{T}\tilde{1\\!\mathrm{l}}\Pi_{c}\right].$
(47)

This is uniquely minimized by choosing $\Pi$ to be the projector onto the
$d^{2}$ right singular vectors of $\tilde{1\\!\mathrm{l}}$ with the largest
singular values. With this specification for $\Pi$, Eq. 45 is a completely
specified LGST estimator for $G_{k}$.

A more or less identical (but easier) calculation yields linear inversion
estimates of the native states and effects, in terms of the directly
observable probability vectors $\vec{R}^{(l)}$ and $\vec{Q}^{(m)}_{l}$:

$\displaystyle|\rho^{(l)}\rangle\\!\rangle$ $\displaystyle=$ $\displaystyle
B_{0}\left(\Pi\tilde{1\\!\mathrm{l}}^{T}\tilde{1\\!\mathrm{l}}\Pi^{T}\right)^{-1}\Pi\tilde{1\\!\mathrm{l}}^{T}\vec{R}^{(l)},$
(48) $\displaystyle\langle\\!\langle E^{(m)}_{l}|$ $\displaystyle=$
$\displaystyle\left[\vec{Q}^{(m)}_{l}\right]^{T}\Pi^{T}B_{0}^{-1}.$ (49)

###  III.4 Preparing the fiducial vectors

In Section III.2 above, we assumed by fiat that informationally complete sets
of fiducial states $\\{\rho^{\prime}_{j}\\}$ and effects
$\\{E^{\prime}_{i}\\}$ could be prepared. But most processors admit just _one_
native state preparation, and one measurement. So fiducial states and
measurements are implemented using gates from the gate set itself (as shown in
Figure 3 (b-c,e-f)).

To do this, we define two small sets of QI/QO “fiducial circuits”. Each
fiducial state is prepared by applying one of the _preparation fiducial
circuits_ to a native state preparation. Each fiducial measurement is
performed by performing one of the _measurement fiducial circuits_ before a
native measurement. In the common case where the native state preparation and
measurement are unique, the $\\{|\rho^{\prime}_{j}\rangle\\!\rangle\\}$ and
$\\{\langle\\!\langle E^{\prime}_{i}|\\}$ are entirely determined by the
corresponding fiducial circuits:

$\displaystyle\langle\\!\langle E^{\prime}_{i}|$ $\displaystyle=$
$\displaystyle\langle\\!\langle E^{(0)}_{\lfloor
i/M\rfloor}|\tau\left(H_{i\mod M}\right),$ (50)
$\displaystyle|\rho^{\prime}_{j}\rangle\\!\rangle$ $\displaystyle=$
$\displaystyle\tau\left(F_{j}\right)|\rho^{0}\rangle\\!\rangle.$ (51)

Equation 50 uses $M\equiv N^{(0)}_{\mathrm{E}}$ as shorthand to avoid too
cumbersome a notation.

In the more general case of multiple state preparations and measurements,
these expressions become:

$\displaystyle\langle\\!\langle E^{\prime}_{i}|$ $\displaystyle=$
$\displaystyle\langle\\!\langle E^{(m(i))}_{t(i)}|\tau\left(H_{h(i)}\right),$
(52) $\displaystyle|\rho^{\prime}_{j}\rangle\\!\rangle$ $\displaystyle=$
$\displaystyle\tau\left(F_{f(j)}\right)|\rho^{r(j)}\rangle\\!\rangle,$ (53)

They must include simple functions that map each effective-item index ($i$ or
$j$) to the native preparation index ($r(j)$), measurement index ($m(i)$), or
fiducial index ($f(j)$ or $h(i)$)) corresponding to that item. Equations 52
and 53 (or 50 and 51) introduce and define measurement fiducial circuits,
$\left\\{H_{k}\right\\}$, and preparation fiducial circuits,
$\left\\{F_{k}\right\\}$ that result in the sets
$\\{|\rho^{\prime}_{j}\rangle\\!\rangle\\}$ and $\\{\langle\\!\langle
E^{\prime}_{i}|\\}$ being informationally complete. Their essential function
is describe how effective preparations and measurements are constructed from
native operations, and are referred for this purpose in remainder of this
work. This is shown pictorially in Figure 3, where indices have been omitted
to increase clarity.

This construction has no consequences for the linear inversion analysis
described above – how the fiducial states/effects are produced doesn’t matter,
as long as they are consistent. But it does have other consequences.

First, it ensures that every “observable probability” required by LGST can be
obtained by running a specific circuit, composed from operations in the gate
set itself.

Second, it subtly reduces the number of free parameters in the model, because
(e.g.) $\rho^{\prime}_{1}$ and $\rho^{\prime}_{2}$ are _not_ entirely
independent, but are actually generated by the same set of operations applied
in a different order. The LGST linear inversion algorithm is blind to this
correlation, but more careful statistical analysis can extract it and provide
a somewhat more accurate estimate (see below).

Third, this construction places the burden of ensuring informational
completeness of the fiducial states/effects onto the choice of fiducial
circuits. This choice is not “canonical” for GST – it depends on the gates
available in the gate set. In practice, “fiducial selection” is usually done
by (1) modeling the gates as error-free, and then (2) using that model to find
a sets of fiducial circuits that produce informationally complete
states/effects. The goal is to have a Gram matrix $\tilde{1\\!\mathrm{l}}$
that is well-conditioned, so that its inverse doesn’t inflate finite-sample
errors. Optimal condition number is achieved when the fiducial states/effects
form a 2-designScott (2006).

Of course, the gates are not necessarily error-free, and fiducial selection
may fail if they are sufficiently erroneous. Fortunately, post-hoc validation
is straightforward, by computing the singular values of the measured
$\tilde{1\\!\mathrm{l}}$ before inverting it. If the $d^{2}$ largest singular
values are not all sufficiently large, then different (or additional)
fiducials should be added (and more data taken). If _no_ fiducials are found
to produce informationally complete sets, then the operations in the gate set
are not capable of exploring the system’s nominal state space, and tomography
must be limited to a subspace thereofBengtsson and Zyczkowski (2017).

###  III.5 Improving LGST with maximum likelihood estimation

In the preceding sections, we have described the goal of tomography (including
GST, and specifically LGST) as “reconstructing” states, processes, or gate
sets. This language has a long history in the tomography literature. But
admitting the existence of finite sample errors – observed _frequencies_ of
circuit outcomes will not exactly match their underlying _probabilities_ –
disrupts this paradigm. The objects that we “reconstruct” are not quite the
true ones. Worse yet, in general there _is_ no “true” state or process!
Quantum states and quantum processes are mathematical _models_ for real
physical systems. Those models rely on assumptions (e.g., Markovianity), which
are never quite true in practice.

“Reconstructing” is a flawed term, and at this point we leave it behind. It is
more accurate to say that GST _estimates_ the gate set. The goal of GST is to
fit a gate set to data – i.e., to find the gate set that fits the observed
data best. This description is more consistent with the least-squares
generalization of linear inversion derived above. But, having rephrased the
problem this way, it is very reasonable to ask “Is least-squares the _right_
way to fit the data?” The LGST algorithms derived above minimize a sum of
squared differences between predicted probabilities and observed frequencies:

$f(\mathrm{gate\ set})=\sum_{j}{\left(p_{j}^{(\mathrm{gate\
set})}-f_{j}^{(\mathrm{observed})}\right)^{2}}.$ (54)

But while minimizing this sum of squared residuals is very convenient, it’s
not especially well-motivated. Furthermore, the LGST algorithms given above
don’t _actually_ minimize the average squared error over the entire dataset –
i.e., all the circuits performed to obtain LGST data – because the projector
$\Pi$ is chosen specifically to capture the support of the Gram matrix
$\tilde{1\\!\mathrm{l}}$, without regard for the other directly observed
probabilities (e.g., those in the $P_{k}$).

The best way to fit the observed data optimally is to set aside traditional
tomography and linear algebra, and focus directly on (1) the actual data
(outcome frequencies of quantum circuits), and (2) the model being fit to it
(gate sets). The set of all possible gate sets can be viewed as a
parameterized manifold. Each point on that manifold is a gate set that
predicts specific, computable probabilities for each quantum circuit. It is
therefore possible to write the objective function from Eq. 54 precisely –
with $j$ ranging over every circuit performed – as a function of the gate set,
and minimize it numerically to find a gate set that really _does_ minimize the
total squared error.

There’s no particularly compelling reason to minimize the total squared error,
though. An objective function that _is_ very well motivated in statistics is
the _likelihood function_ :

$\mathcal{L}(\mathrm{gate\ set})=\mathrm{Pr}(\mathrm{data}|\mathrm{gate\
set}).$ (55)

Although not immediately obvious, the sum-of-squares objective function in Eq.
54 can be seen as an approximation to the likelihood. Maximizing the
likelihood function is the apotheosis of linear inversion – it’s what linear
inversion wants to be when it grows up. If we numerically vary over gate sets
to find the one that maximizes $\mathcal{L}$, that is _maximum likelihood
estimation_ (MLE), and it is a strictly better and more accurate way of
analyzing LGST data than the linear inversion methods defined above.

In the rest of this paper, we will adopt this approach. We will view the data
as a list of circuits with observed outcome frequencies. We will view gate
sets as statistical models that predict circuit probabilities. And we will
find good _estimates_ of real-world gate sets by fitting that model’s
parameters to observed data, using MLE or approximations to it.

A natural question, then, is “Why develop the whole linear-inversion LGST
framework, if having done so we immediately move beyond it?” There are several
good reasons. The most practical is that the linear-inversion LGST algorithm
developed above is actually a critical _first_ step in any numerical MLE
algorithm! Because circuit probabilities are nonlinear functions of the gate
set parameters, both Eq. 54 and the likelihood function itself have unpleasant
_global_ behavior, including local extrema. Linear-inversion LGST is a very
fast algorithm to obtain a _pretty good_ estimate, which can serve as a
starting point for (and be refined by) numerical MLE.

But LGST also serves as a critical _conceptual_ foundation. Regardless of what
estimator we use (linear inversion, MLE, or something else), we can’t estimate
the gate set’s parameters unless the experiments that generated the data are
sensitive to them. LGST constructs a set of experiments guaranteed to be
sensitive to all the parameters in the gate set. Deeper circuits, introduced
in the next section, _amplify_ those parameters and allow greater sensitivity
– but the experiments that we use in long-sequence GST are clearly derivative
of the ones in LGST, and rely on the same structure to guarantee sensitivity
to all amplified parameters.

##  IV Long-sequence Gate Set Tomography

Traditional process tomography on a gate $G_{k}$ uses circuits in which
$G_{k}$ appears just once. Observed probabilities depend linearly on $G_{k}$,
making it very easy to invert Born’s rule to estimate $G_{k}$. LGST bends this
rule – a given $G_{k}$ may appear both in the middle of the circuit _and_ in
the fiducial circuits – but the circuits are short, and each gate appears only
$O(1)$ times. This enables the relatively straightforward analysis presented
in the previous section, but it also limits precision. If $A$ and $B$ (Eqs. 13
and 17) are well-conditioned [condition number $O(1)$] then each matrix
element of $G_{k}$ is very close to a linear combination of observed
probabilities.

If each circuit is performed $N$ times, then finite sample fluctuations cause
estimation errors in each probability,

$\hat{p}=p\pm\frac{O(1)}{\sqrt{N}},$ (56)

and the accuracy of $\hat{G}_{k}$ is also limited to $\pm O(1)/\sqrt{N}$.
Under certain circumstances, some of these probabilities (with $p\approx 0$)
can be estimated to within $O(1/N)$ Mahler et al. (2013), but the resulting
improvement in overall accuracy is limited by SPAM noise and by the fact that
only a few of the circuits can be chosen to have $p\approx 0$.

A completely different way to break the $1/\sqrt{N}$ boundary is to
incorporate data from _deep_ circuits, in which a gate appears many times. The
circuits must be designed so that their outcome probabilities depend more
sensitively on the elements of $G_{k}$, with sensitivity proportional to the
number of times $G_{k}$ appears in the circuit. For example, the outcome
probabilities for

$\Pr=\langle\\!\langle E|G_{k}G_{k}G_{k}G_{k}|\rho\rangle\\!\rangle,$ (57)

are four times as sensitive to changes in $G_{k}$ as the outcome probabilities
for

$\Pr=\langle\\!\langle E|G_{k}|\rho\rangle\\!\rangle,$ (58)

and therefore allow four times the precision in estimating some aspects of
$G_{k}$. Long-sequence GST turns this simple idea into a practical algorithm
for characterizing gate sets.

The original motivation for long-sequence GST was precision and accuracy, but
another advantage emerged later. Unlike traditional tomography and LGST, long-
sequence GST is easily adaptable to a wide range of noise models. In process
tomography and LGST, each noisy gate is specifically described by an arbitrary
transfer matrix. Even small extensions – e.g., focusing on _low rank_ transfer
matrices – require conceptual and practical modifications of tomography Gross
et al. (2010); Shabani et al. (2011); Flammia et al. (2012); Heinosaari et al.
(2013). But long-sequence GST only requires a parameterized model for the
noisy gates that can be _embedded_ into transfer matrices. The gate set of Eq.
6 is such a model, with one parameter per element of
$|\rho^{(i)}\rangle\\!\rangle$, $G_{i}$, and $\langle\\!\langle E^{(m)}_{i}|$
expressed in a chosen basis. But a gate set can, more generally, be described
by any mapping between a parameter space and the aforementioned operations.
Long-sequence GST can be used to estimate a gate set that is parameterized in
any reasonable way. This flexibility can be used to model various features and
constraints on the gate set, including complete positivity (CP) and trace
preservation (TP). We defer a discussion of this flexibility until section
V.1, as these details are not essential to understanding long-sequence GST.
Presently, it is sufficient to note that a gate set is a mapping from a
parameter space (e.g., the direct sum of the vector spaces for each operator)
to a set of operations capable of predicting circuit outcomes.

The core long-sequence GST protocol used by our research group has remained
largely unchanged since about 2017. But between 2013 and 2017, it morphed
repeatedly as we discovered that certain things didn’t work, or found better
ways to solve certain problems. Its current stable form is the result of a
nontrivial evolution process. Like most products of evolution, it contains
both historical artifacts and necessary solutions to non-obvious problems.
Rather than present the state of the art as a _fait accompli_ , we introduce
it by outlining the historical path that led to it (Section IV.1), emphasizing
some of the techniques that _didn’t_ work. Next, we explain how to construct a
good long-sequence GST _experiment design_ , a set of circuits of depth at
most $O(L)$ that enables estimating gate set parameters to precision $O(1/L)$
(Section IV.2). We conclude this presentation of long-sequence GST by showing
how to estimate those parameters by efficiently maximizing the likelihood
function, and discuss a variety of technical insights that make the numerical
methods reliable in practice (Section IV.3).

###  IV.1 Historical background

Our first attempt to achieve higher accuracy involved performing random,
unstructured circuits and fitting gate set models to the resulting count data
Blume-Kohout et al. (2013). We augmented the set of circuits prescribed by
LGST with a variety of random circuits (much like those used in direct
randomized benchmarking Proctor et al. (2019a)) of various depths, and then
used numerical MLE to fit a gate set to the resulting data. This approach
produces a likelihood function that is generically messy – it is not a quasi-
convex function of the gate set, usually has local maxima, and has no
particular structure. However, it is straightforward to evaluate, and its
derivative can be computed efficiently from the data. Moreover, a subset of
the data enable LGST, which provides a “pretty close” starting point for local
gradient maximization of $\mathcal{L}(\mathcal{G})$.

Investigation of this approach revealed two problems.

  1. 1.

Random circuits provided surprisingly low precision. Although estimation error
decreased with $L$, it declined as $O(1/\sqrt{L})$, not $O(1/L)$.

  2. 2.

The lack of structure in the likelihood function made numerical MLE
problematic. Local gradient optimization worked only unreliably, and was
highly dependent on starting location. We achieved reasonable success in
simulations by starting with LGST, and then refining this estimate by adding
successively deeper circuits to the likelihood function. However, this
technique proved less reliable in experiments, where the underlying model was
less valid. Running the optimizer repeatedly with different starting
conditions, and incorporating more global-optimization techniques, often
revealed better local maxima of the likelihood. This suggested that even the
best estimates we found might not be global maxima.

We concluded that (1) as the IBM group had observed earlier, brute-force MLE
on unstructured GST data was not a satisfactory solution, and (2) we needed to
choose circuits more cleverly (as with LGST) to make the analysis easier and
more reliable.

We developed an approach called _extended LGST_ (eLGST). It relied on two
critical modifications to the original “unstructured MLE” approach, which
impose additional structure to the experiment design and data analysis
(respectively).

First, instead of performing random circuits, we constructed a set of circuits
corresponding to performing LGST – not on the gates $G_{k}$ themselves, but on
a small set of “base” circuits, $\\{S_{l}\\}$. We took each $S_{l}$ and
sandwiched it between fiducial circuits (just as we did with each $G_{k}$ for
LGST). Originally, the base circuits were simple repetitions of individual
gates, e.g. $G_{k}^{p}$ for $p=1,2,4,8,\ldots$. We found that this amplified
some, but not all, parameters of the gate set.

This extended-LGST (eLGST), experiment design eventually evolved into one
where the base circuits were chosen to be a set of short “germ” circuits
($g_{i}$) repeated $p$ times ($g_{i}^{p}$). This spawned the “germ selection”
procedure used today in long-sequence GST, which we discuss in detail in
Section IV.2. This structure ensures that each base circuit amplifies _some_
set of deviations from the target gates, so that these deviations change the
observed probabilities for the circuits based on that base circuit by $O(L)$.
The germs are chosen so that they amplify different deviations, and so that
collectively they amplify _all_ deviations. This careful, non-random
experiment design allowed eLGST to achieve consistent, reliable, and
predictable accuracy that scales as $1/L$.

Second, instead of using MLE to fit a gate set directly to the data, eLGST
fits the gates indirectly via a 2-step process. In the first step, we
estimated the transfer matrix for each base circuit,
$\widehat{\tau(g_{i}^{p})}$. Then, those estimates were used to back out a
transfer matrix for each gate. The eLGST protocol is a precursor to the long-
sequence GST we now describe. Appendix B gives a full description of eLGST.

###  IV.2 Experiment design for long-sequence GST

A long-sequence GST experiment is designed to enable high accuracy with
minimal experimental effort. LGST can estimate a gate set to arbitrary
accuracy, but because uncertainty in the estimated parameters scales as
$O(1/\sqrt{N})$ if each circuit is repeated $N$ times, achieving precision
$\epsilon$ requires $O(1/\epsilon^{2})$ repetitions. This makes precisions of
$\epsilon\approx 10^{-5}$, as demonstrated in Blume-Kohout et al. (2017b),
practically impossible to reach.

Long-sequence GST overcomes this barrier by specifying a different _experiment
design_ – a set of quantum circuits to be run – containing circuits that
amplify errors in the gate set. This experiment design retains the basic
structure of LGST: each of a list of “operations of interest” is probed by
constructing circuits that sandwich it between pre- and post-operation
fiducial circuits. But instead of a single gate, the middle of each sandwich
is a more complicated base circuit that amplifies certain errors so they can
be measured more precisely by tomography. In this section, we present the
long-sequence GST experiment design. We use the term _experiment_ to mean an
experiment design along with the data obtained by repeating each of its
circuits many times.

Figure 4: The structure of circuits in the standard GST experiment design,
shown in increasing detail. (a) Each GST circuit consists of an effective
state preparation $\rho^{\prime}$ (Eq. 53), followed by a _germ_ circuit $g$
repeated $p$ times, followed by an effective measurement
$\mathrm{M}^{\prime}=\\{E^{\prime}_{i}\\}$ (Eq. 52). (b) Effective
preparations are often implemented by a native state preparation $\rho$
followed by a _preparation fiducial circuit_ $F$, and similarly effective
measurements are often implemented by _measurement fiducial circuit_ $H$
followed by a native measurement $\mathrm{M}$. (c) Writing the fiducials and
germ in terms of native gate operations reveals how the native operations of a
gate set compose to form a GST circuit.

Each long-sequence GST circuit constitutes three consecutive parts (see Figure
4):

  1. 1.

Prepare a particular state, $|\rho^{\prime}_{k}\rangle\\!\rangle$ by
performing a native preparation followed by a fiducial circuit.

  2. 2.

Perform $p$ repetitions of a short circuit $g$ that we call a _germ_.

  3. 3.

Perform a particular measurement $\\{\langle\\!\langle E^{\prime(m)}_{i}|\\}$
by performing a fiducial circuit and then a native POVM measurement.

The outcome statistics from repeating such a circuit many times allow
estimating probabilities like

$p=\langle\\!\langle
E^{\prime(m)}_{i}|\tau(g_{j}^{p})|\rho^{\prime}_{k}\rangle\\!\rangle.$ (59)

If the states and measurements are each informationally complete, these
probabilities are sufficient for tomography on $\tau(g_{j}^{p})$. All GST
experiments are derived from this basic structure, and every circuit performed
for GST is specified by an $(j,k,p,m)$ tuple.

We call the short circuit $g$ a _germ_ because, like a germ of wheat or the
germ of an idea, it serves as the template for something larger – here, an
arbitrarily deep circuit built by repetition. We refer to $g^{p}$, the object
of tomography, as a _base circuit_ and $p$ as a _germ power_. Repeating $g$
amplifies errors in $g$. For example, if $g$ is a single unitary gate $G$, and
$G$ over-rotates by angle $\theta$, then $\tau(g^{p})$ will over-rotate by
$p\theta$. By varying the input state and final measurement ($k$ and $m$) over
informationally complete sets, we probe the operation between them, just as in
process tomography or LGST. If this tomography on $g^{p}$ measures $p\theta$
to precision $\pm\epsilon$, then we’ve measured $\theta$ itself to precision
$\pm\epsilon/p$.

Simple germs comprising a single gate $G$ are not sufficient to amplify every
error. Some errors can only be amplified by first constructing a multi-gate
circuit, e.g., $g=G_{1}G_{2}$, and then repeating _it_. Repeating $g$ many
times amplifies errors that _commute_ with $\tau(g)$. In the example above, an
over-rotation error in $G$ is an error that commutes with $G$, so it is
amplified. But suppose that $G$ rotates by the correct angle, but around the
wrong axis, e.g., instead of a rotation around $\hat{z}$, $G$ performs a
rotation around $\hat{z}\cos\phi+\hat{x}\sin\phi$. This _tilt_ error is not
amplified by repeating $G$, but it can be amplified by a more complex germ
that includes $G$ together with other gates.

To achieve high precision estimates efficiently, we need to amplify every
parameter in the gate set that _can_ be amplified. Two kinds of parameters
cannot be amplified. Gauge parameters cannot be measured at all, and
properties of the SPAM operations cannot be amplified because SPAM operations
only appear once in each circuit. So germs amplify errors in gates. Therefore,
as we discuss selection of germs, we will focus exclusively on the gates and
ignore SPAM operations.

In the following sections we describe how to select a set of base circuits –
germs and powers to raise them to that amplify all of the amplifiable
parameters of a given “target” gate set. This target gate set is typically
taken to be the ideal gates a device is designed to implement. More details
may be found in Appendix C.1.

Figure 5: Overview of how to design a GST experiment. Step 1. Choose _germ_
circuits that amplify _all_ gauge-invariant parameters in the processor’s gate
set. Step 2. Define _base circuits_ by raising each germ to powers chosen so
that the base circuits’ depths are as close as possible to being
logarithmically spaced. Step 3. Sandwich each base circuit between each of
$N_{f1}\times N_{f2}$ _fiducial pairs_ defined by $N_{f1}$ preparation and
$N_{f2}$ measurement fiducial circuits. Step 4. Optionally apply _fiducial
pair reduction_ (FPR) to eliminate redundant circuits from the experiment
design, leaving just enough to ensure sensitivity to each base circuit’s
amplified parameters. Final result 5. A GST experiment design can be
visualized as a grid of plaquettes. The plaquettes correspond to base
circuits, are arranged by germ and $L$, the maximum depth used to construct
the base circuit from the germ. Within a plaquette, squares indicate different
fiducial pairs, and the plaquette will be “sparse” when FPR has been applied.

####  IV.2.1 Selecting germs ($g$)

To estimate a gate set efficiently and accurately, every variation in the gate
set, except those corresponding to SPAM and gauge directions, must be
amplified by some germ. We call a set of germs that achieves this goal
_amplificationally complete_ , in direct analogy to “informationally complete”
sets of states or measurements.

To evaluate (and ensure) amplificational completeness, we model errors in the
gate set as small perturbations to the target gate set. Each germ $g$, when
repeated, will amplify certain errors. Specifically, any small perturbation to
a gate set’s parameters that causes a change in $\tau(g)$ that _commutes_ with
$\tau(g)$ will be amplified by $g$. The set of all such perturbations is
easily shown to be closed under linear combination, so each germ $g$ amplifies
error vectors that lie in a _subspace_ of the gate set’s parameter space. This
subspace can be easily constructed from the target gate set and the germ.

It is also straightforward to construct the tangent subspace of _gauge_
variations. It contains all small perturbations around the target gate set
that do not change any observable probability at all. Its complement is the
subspace of physical errors that need to be amplified. Now we can define
amplificational completeness precisely: _a set of germs $\\{g_{j}\\}$ is
amplificationally complete for a target gate set $\mathcal{G}$ if and only if
the union of the error subspaces amplified by each $g_{j}$ span the complement
of the subspace of gauge variations._

Amplificational completeness defines a concrete condition that germs must
satisfy for GST. However, it depends on the target gate set, so each new
target gate set requires finding a new set of germs. Furthermore, different
desiderata may motivate different amplificationally complete sets of germs
(e.g., it is reasonable to prioritize the _smallest_ set of germs, or the
_shortest_ possible germs, or the set that achieves the highest precision for
a given maximum depth). In the pyGSTi implementation of GST Nielsen et al.
(2016, 2020), we use a particular search algorithm to evaluate sets of short
germs and find the smallest amplificationally complete set. Algorithmic and
mathematical details can be found in Appendix C.1. We require that a chosen
germ set always includes each gate $G_{i}$ in the gate set as an independent
germ.

####  IV.2.2 Defining base circuits

Once a set of germs is selected, a set of _base circuits_ is constructed by
raising each germ to several powers $p$. We begin by selecting $p=1$. Since
each gate $G_{i}$ is also germ, this ensures that each individual gate appears
as a base circuit. What remains is to choose all the _other_ values of $p$
that will appear in the experiment.

Large values of $p$ amplify errors more. But including _only_ large powers $p$
would create an aliasing problem. If $\tau(g)$ over-rotates by
$\theta=\pi/16$, then repeating it $p=32$ times creates an over-rotation by
$2\pi$, which appears to be no error at all! So, exactly as in phase
estimation, smaller powers $p$ are needed too. Since this is essentially a
binary search, logarithmically spaced values of $p$ are optimal.

More generally, a base circuit’s $p$ is less relevant than its overall
_depth_. If germ $g_{1}$ has depth 1, while $g_{2}$ has depth 5, then
$g_{1}^{10}$ and $g_{2}^{2}$ both have depth 10. So in describing GST
experiments, we typically organize base circuits by their approximate depth
$l$ rather than $p$. If we denote the depth of germ $g$ by $|g|$, then the
depth-$l$ base circuit based on $g$ is $g^{\lfloor l/|g|\rfloor}$. Our
intuition to use logarithmically spaced $p$ above leads us to choose
logarithmically spaced $l$ – i.e., $l=1,m,m^{2},m^{3},\ldots$ – to choose the
base circuits.

Making $m$ larger reduces the total number of circuits to be run, but requires
higher precision (more repetitions) at each value of $l$. Empirically, we have
found $m=2$ to work reliably – i.e., $l=1,2,4,8,16\ldots$ – but other choices
are possible. Germs of depth $d>1$ do not have realizations for depths $l<d$,
so a germ of depth 5 would appear first at $l=8$ (with 1 repetition), then
$l=16$ (with 3 repetitions), etc. Thus, the depth of a “depth $l$” base
circuit is not necessarily equal to $l$, but is always in the interval
$(l/m,l]$.

Any given experiment can only include finitely many circuits, so for each germ
there must be a maximum depth $L$ at which it appears. This is configurable.
Selecting $L$ should be guided by three facts. First, increasing $L$ amplifies
errors more and yields more precision (all else being equal). Second,
increasing $L$ makes the experiment larger (more circuits), which requires
more time to obtain and analyze. Third, there is essentially no benefit to
increasing $L$ beyond the point where decoherence and stochastic errors
dominate. If the rate of decoherence in each gate is $\eta$, then circuits of
depth $\gg 1/\eta$ generally all produce the same equilibrium state, and
little or nothing will be learned from circuits of depth $L>O(1)/\eta$. If
different gates have very different rates of stochastic errors, then it is
useful to let $L$ vary from germ to germ.

####  IV.2.3 Putting it all together

The circuits for a full GST experiment are constructed as follows. First a set
of amplificationally complete germs is selected (cf. IV.2.1, Fig. 5 step 1).
Next a set of base circuits is chosen (cf. IV.2.2, Fig. 5 step 2). Let these
be given by $\mathcal{O}=\left\\{g_{i}^{p_{i,j}}\right\\}_{i,j}$, where $i$
indexes a germ and $p_{i,j}$ is the $j$-th power that we apply to the $i$-th
germ. As explained above, to amplify the desired errors it is sufficient that
the GST circuits estimate the probabilities

$p_{abij}=\langle\\!\langle
E^{\prime}_{a}|\tau(g_{i})^{p_{i,j}}|\rho^{\prime}_{b}\rangle\\!\rangle,$ (60)

where $a=1\ldots N_{f1}$ and $b=1\ldots N_{f2}$ range over the indices of the
effective preparations and effects (Fig. 5 step 3 and 5). Writing the
effective state preparations and POVM effects in terms of their constituent
fiducial circuits (Eqs. 52 and 53) gives the probabilities entirely in terms
of native operations, i.e. elements of the gate set:

$p_{abij}=\langle\\!\langle
E^{m(a)}_{t(a)}|\tau\left(H_{h(a)}\right)\tau\left(g_{i}\right)^{p_{i,j}}\tau\left(F_{f(b)}\right)|\rho^{r(b)}\rangle\\!\rangle.$
(61)

The corresponding circuit (which can be read off directly, from right to left
because the matrix-ordering of Eq. 61 is reversed from time-ordering) is
repeated $N$ times to approximate $p_{abij}$. The steps of this circuit are:

  1. 1.

prepare the $r(b)$-th state

  2. 2.

perform the (QI/QO) circuit $F_{f(b)}g_{i}^{p_{i,j}}H_{h(a)}$

  3. 3.

measure using the $m(a)$-th type of measurement

The frequency $f_{t(a)}=n_{t(a)}/N$, where $n_{t(a)}$ is the number of times
the $t(a)$th outcome was observed, estimates $p_{abij}$. In this way, a
circuit’s outcome data can estimate all of the $p_{abij}$ that differ only in
their $t(a)$ (POVM effect) index.

Letting $a$, $b$, $i$ and $j$ range over their allowed values in the steps
above defines all the circuits needed to run long-sequence GST. These circuits
constitute a GST experiment design. Their structure is show schematically in
Figure 4, where again we omit the many indices (cf. Eq. 61) for clarity. (For
later analysis of the circuits’ outcome data, it is helpful to separately keep
track of the fiducial and germ circuits, and the germ powers.) In appendix D
we show that a set of so-chosen circuits (using the particular pyGSTi
algorithms discussed in appendix C.1) result in a Heisenberg-like accuracy
scaling with respect to circuit depth and total number of circuits.

Finally, we note that arriving at a definite list of circuits (an experiment
design) required information based on the experimental circumstances. The sets
of fiducials and germs were based on the available native gates (specified by
a target gate set), and the maximum depth of the circuits was based on a
tradeoff between resources and accuracy (longer experiments are more resource-
intensive, because they require more and deeper circuits, but they give more
accuracy – although only up to a maximum useful depth that is roughly the
inverse of the decoherence rate). GST experiments are tailored to a hardware’s
capabilities.

###  IV.3 Estimating gate set parameters in long-sequence GST

A gate set is a parameterized statistical model. The parameterization may be
simple (e.g., every gate element is a parameter) or nontrivial (see section
V.1). Fitting a gate set model to data from the experiments described in
Section IV.2 is an example of _parameter estimation_. There are many ways to
do this (cf. section III.5). In this paper, we focus on maximum likelihood
estimation (MLE), which requires varying the gate set’s parameters to maximize
the probability of the data (or, for practical simplicity, its logarithm).

The loglikelihood function can be constructed as follows. Let $\mathcal{G}$
denote the model, $s$ index a circuit of the experiment design, and $N_{s}$ be
the total number of times circuit $s$ was repeated in the GST experiment.
Furthermore, let $m_{s}$ be the number of outcomes of $s$, and
$N_{s,\beta_{s}}$ denote the number of times outcome $\beta_{s}$ was observed.
The contribution to the total loglikelihood from $s$ is simply the multinomial
likelihood function for an $m_{s}$-outcome Bernoulli scheme,

$\log\mathcal{L}_{s}=N_{s}\sum_{\beta_{s}}{f_{s,\beta_{s}}\log(p_{s,\beta_{s}})},$
(62)

where $p_{s,\beta_{s}}$ is the _probability_ predicted by $\mathcal{G}$ of
getting outcome $\beta_{s}$ from circuit $s$, and
$f_{s,\beta_{s}}=N_{s,\beta_{s}}/N_{s}$ is the corresponding observed
_frequency_. The total loglikelihood for the entire GST experiment is just the
sum

$\log\mathcal{L}=\sum_{s}{\log\mathcal{L}_{s}}=\sum_{s,\beta_{s}}N_{s}f_{s,\beta_{s}}\log(p_{s,\beta_{s}}),$
(63)

where $s$ ranges over all of the circuits in the experiment design. This
derivation assumes that $\mathcal{G}$ is trace-preserving (TP), so that
$\forall s\,\sum_{\beta_{s}}p_{s,\beta_{s}}=1$. An extension to non-TP gate
sets requires some technical tricks and is explained in appendix C.2.

Maximizing $\log\mathcal{L}$ is made nontrivial by the structure of the
problem. This contrasts with state and process tomography, where the
parameterized model is a density matrix $\rho$ or a superoperator $G$, each
observable probability is a _linear_ function of the parameter, and the
loglikelihood is a sum of logarithms of linear functions. This means MLE
state/process tomography is a straightforward convex optimization problem.

In contrast, the GST likelihood function (Eq. 63) is extremely non-convex.
Because gates appear repeatedly in circuits, the probabilities
$p_{s,\beta_{s}}$ are nonlinear functions of gate elements (and, more
generally, the parameters of $\mathcal{G}$). The construction outlined
previously causes the $p_{s,\beta_{s}}$ to _oscillate_ , creating a
loglikelihood function that looks like an egg crate or optical lattice, with
many local maxima. Finding global maxima of such functions is generally hard.

The gauge freedom creates more problems, by turning unique maxima into
“ridges” that trace out gauge orbits. Constraining the optimization to CP gate
sets creates complexity, because the CP condition does not respect gauge
symmetry and can create local maxima. Ignoring the CP constraint makes
optimization easier, but allows unphysical gate sets that can have zero or
negative likelihood.

We have developed a particular pipeline of MLE and related estimators that
reliably maximize Eq. 63 when $\mathcal{G}$ is parameterized in one of several
common ways (including with TP and CPTP constraints). We present this method,
not as the _only_ way to perform the parameter-estimation step of long-
sequence GST, but as _a_ way of implementing this crucial step of the
protocol.

Our approach is outlined in Algorithm 1. Here $\vec{\theta}$ is the vector of
$\mathcal{G}$’s parameters being optimized, $\mathcal{D}$ is a data set,
$\mbox{Truncate}(\mathcal{D},L)$ is the subset of $\mathcal{D}$’s data
corresponding to circuits whose germ-power has depth $\leq L$, and
$\mbox{Argmin}(S,\mathcal{G},\mathcal{D},\vec{\theta}_{1})$ yields the
$\vec{\theta}$ at which statistic $S(\mathcal{G}(\vec{\theta}),\mathcal{D})$
is minimal using a local optimizer seeded at $\vec{\theta}_{1}$.
$\mathcal{D}_{0}$ is the full GST data set, and $\vec{\theta}_{0}$ is the
initial vector of model parameters, often provided by LGST (Section III). We
have found $m=2$ to work well in practice.

Algorithm 1 Long-sequence GST

$\vec{\theta}\leftarrow\vec{\theta}_{0}$

for $L\in 1,m,m^{2},m^{3},\ldots$ do

$\mathcal{D}\leftarrow\mbox{Truncate}(\mathcal{D}_{0},L)$

$\vec{\theta}\leftarrow\mbox{Argmin}(\chi^{2},\mathcal{G},\mathcal{D},\vec{\theta})$

end for

$\vec{\theta}\leftarrow\mbox{Argmin}(-\log\mathcal{L},\mathcal{G},\mathcal{D}_{0},\vec{\theta})$

We highlight three important elements to this approach that we believe are
particularly important to its success:

Optimization Stages. Our approach proceeds in multiple “stages”. At each
stage, we run a traditional local optimization method (we find the Levenberg-
Marquardt technique to give good results) on a _subset_ of all the data. Each
stage sets a maximum base circuit depth $L$, and at that stage only data from
base sequences with depth less than or equal to $L$ are incorporated into the
likelihood function (Eq. 63). We choose $L=1,m,m^{2},m^{3},\ldots$, so that
the stage corresponding to $L$ contains the circuits whose base circuits are
$g^{\lfloor l/|g|\rfloor}$ for $l=1,m,m^{2}\ldots,L$. Successive stages add
deeper circuits, while keeping all the shorter circuits. By using the best-fit
output of a stage as the starting point of the next we create a daisy chain of
estimations that avoids local minima. As long as finite sample fluctuations
are kept small enough (by repeating each circuit enough times) the previous
stage’s best-fit estimate lies with high probability in the correct basin of
the next stage’s objective function, rendering its oscillatory nature benign.

Use of $\chi^{2}$ as a $\log\mathcal{L}$ proxy. At every stage except the last
one, the $\chi^{2}$ statistic is optimized instead of loglikelihood. The
$\chi^{2}$ is a weighted-sum-of-squares function that (like likelihood)
quantifies goodness-of-fit. Using our definitions above, it can be written as

$\chi^{2}=\sum_{s,\beta_{s}}{N_{s}\frac{(p_{s,\beta_{s}}-f_{s,\beta_{s}})^{2}}{p_{s,\beta_{s}}}}=\sum_{s}{\chi^{2}_{s}},$
(64)

where

$\chi^{2}_{s}=\sum_{\beta_{s}}{N_{s}\frac{(p_{s,\beta_{s}}-f_{s,\beta_{s}})^{2}}{p_{s,\beta_{s}}}}$
(65)

is the contribution from a single circuit $s$. The weights
($1/p_{s,\beta_{s}}$) ensure that $\chi^{2}$ is a local quadratic
approximation to the negative loglikelihood. Compared with the loglikelihood,
$\chi^{2}$ can be computed faster, and is more well-behaved as an objective
function. It has one significant disadvantage: its minimum is a slightly
biased estimator (see appendix E). Optimizing the loglikelihood in the final
stage renders this a non-issue, and we find minimizing $\chi^{2}$ to be more
robust at seeding the final $\log\mathcal{L}$ maximization than performing
$\log\mathcal{L}$ maximizations all the time. One notable exception to this
occurs when the number of circuit repetitions is low and $\chi^{2}$ becomes a
poor proxy for $\log\mathcal{L}$.

Regularization. We increase the reliability of optimization by regularizing
both $\log\mathcal{L}$ and $\chi^{2}$. Both functions have poles when
probabilities are zero, which can lead to numerical instabilities when
probabilities are near zero. By slightly altering each function, we make them
more amenable to optimization. A simple and effective way to regularize Eq. 64
is to limit the least-squares weights to a maximum cutoff, e.g. $1/p_{min}$.
Since $\chi^{2}$ is already just a proxy for the negative loglikelihood, this
has no effect on the final fit. The $\log\mathcal{L}$ function needs to be
tweaked more carefully, by replacing Eq. 62 with its second-order Taylor
series when $p_{s,\beta_{s}}<p_{min}$, where $p_{min}$ is chosen to be much
less than the smallest possible non-zero frequency (e.g., $10^{-4}$ if each
circuit is repeated 1000 times). Because this alters the $\log\mathcal{L}$
function only when a probability is much different than its observed
frequency, it distorts the objective’s value (and thereby the rigor of its
interpretation) only for particularly bad fits. We have evidence that these
small adjustments to the standard $\log\mathcal{L}$ and $\chi^{2}$ cause local
optimization methods to be more robust, presumably because they avoid regions
with very large gradient and widen basins of convergence.

The method outlined above is not guaranteed to find a global maximum of
$\log\mathcal{L}$, but does so impressively often in practice. Improvements to
the algorithm are a deserving area for future work, but the algorithm
described above demonstrates that the parameter estimation problem lying at
the heart of long-sequence GST is tractable, enabling its practical use.

The long-sequence GST protocol described above – designing an experiment,
running that experiment to produce data, and finally analyzing the data via
multi-stage MLE – produces a best-fit gate set in an unknown gauge. The gauge
is irrelevant when predicting circuit outcomes, so the estimated gate set can
be used immediately for this purpose. (For example, it is possible to predict
the success probabilities of RB circuits and extract the RB number.) However,
computing standard metrics such as fidelity and diamond-distance requires an
additional step called _gauge optimization_. We discuss this, and other common
post-processing, in Section VI. Readers should feel free to jump to that
section, if desired. Section V covers several advanced topics that were
omitted from our presentation thus far of long-sequence GST.

##  V Advanced long-sequence GST

This section discusses two additional topics related to long-sequence GST.
Although they are not essential to the protocol as a whole, they infuse it
with significant additional capability. First, we formalize the notion of a
gate set model, and suggest a natural path to extending long-sequence GST by
creating additional models. Second, we describe how the number of circuits in
the GST experiment design (Section IV.2) can be sizeably reduced by taking
advantage of overcompleteness present in the standard design. The material
here is not required by any of the remaining main text.

###  V.1 Gate set models

Gate sets, as we have defined them, contain general state, measurements, and
superoperators. A gate set $\mathcal{G}$ (Eq. 6) represents each gate as a
$d^{2}\times d^{2}$ real-valued matrix, and each state preparation or
measurement effect as a $d^{2}$-dimensional real-valued vector or dual vector,
respectively. Let us define _matrix space_ as $\mathcal{M}\
\sim\mathbb{R}^{N_{\mathrm{e}}}$, where

$N_{\mathrm{e}}=d^{4}N_{\mathrm{G}}+d^{2}\left(N_{\rho}+\sum_{m=1}^{N_{\mathrm{M}}}N^{(m)}_{\mathrm{E}}\right)$
(66)

is the total number of (real) elements in a gate set. $\mathcal{M}$ is thus
isomorphic to the direct sum of the vector spaces containing each gate set
operation’s matrix, vector, or dual vector. Any gate set (as defined by Eq. 6)
is a point in matrix space, $\mathcal{G}\in\mathcal{M}$, with coordinates
given by the elements of each gate set operation.

A gate set is a statistical model that assigns probabilities to the outcomes
of quantum circuits.333Technically, a gate set is a _factory_ , which can
produce a statistical model for any set of circuits. Since such a set of
circuits is always implied by context in which gate sets are used, we allow
ourselves to abuse terminology slightly.

We use the term _gate set model_ to mean a mapping between a parameter space
$\mathcal{P}\sim\mathbb{R}^{N_{\mathrm{p}}}$ and $\mathcal{M}$. The dimension
of parameter space, $N_{\mathrm{p}}$, is typically less than $N_{\mathrm{e}}$.
Formally, a gate set model corresponds to a choice of $\mathcal{P}$ and a map

$W:\mathcal{P}\to\mathcal{M}.$ (67)

A gate set model is a parameterized statistical model that associates with
every point in parameter space a gate set. Long-sequence GST finds an optimal
gate set by searching over this parameter space, optimizing over
$\vec{\theta}\in\mathcal{P}$. So by using different gate set models, we can
constrain this optimization to subsets of the entire matrix space. Informally,
a basis for $\mathcal{P}$ defines “knobs” that can be adjusted – e.g., by the
MLE optimization, but also by hand if so desired – to vary a gate set and make
it more consistent with the observed data.

If we set $\mathcal{P}=\mathcal{M}$ and $W(x)=x$ then each element of every
operation in the gate set is an independent parameter. We call this the _fully
parameterized gate set model_ , and we can use it for GST (as in Sec. IV).
However, it includes _all_ gate sets, even wildly nonphysical ones that
violate complete positivity and/or trace preservation. So it is useful to
define _smaller_ gate set models that parameterize strict subsets of
$\mathcal{M}$ (e.g., only CPTP gate sets).

####  V.1.1 Gauge freedom in constrained gate sets

Gate set models may have gauge freedoms. A gauge freedom exists if there is a
transformation that can be applied to $\vec{\theta}\in\mathcal{P}$ that
changes $\vec{\theta}$ but does not change any observable probability that can
be computed from the corresponding gate set $W(\vec{\theta})$. We have already
discussed the gauge freedoms of the fully parameterized gate set model; they
correspond to similarity transformations by invertible matrices $M$ that act
on each gate matrix as $G_{k}\to MG_{k}M^{-1}$ (cf. Eq. 7). For any given
$\mathcal{G}$, the action of _all_ possible $M$ on $\mathcal{G}$ traces out a
_gauge orbit_ containing all the gate sets
$\mathcal{G^{\prime}}\in\mathcal{M}$ that are equivalent to $\mathcal{G}$. For
general gate set models, one must consider the pullback of Eq. 7 to
$\mathcal{P}$. As we discuss below, this can make the analysis more
complicated. In $\mathcal{M}$, gauge freedoms correspond to gauge orbits –
sets of equivalent gate sets. But in $\mathcal{P}$, these freedoms can map
onto a different construct. Still, it is helpful to picture the parameter
space as being foliated into gauge orbits, like an onion or layered pastry.
Appendix A.1 describes gauge transformations in more detail.

It can be useful to count the gauge degrees of freedom for a given gate set
model. All the gauge orbits, except for a set of measure zero, are manifolds
of this fixed dimension. (If one or more gates in a gate set have degenerate
spectra, then they remain invariant under certain gauge transformations; the
corresponding orbits have lower dimension, like the center of an onion). Since
$\mathcal{P}$ has dimension $N_{\mathrm{p}}$, then any point $\vec{\theta}$
can be varied in $N_{\mathrm{p}}$ linearly independent directions. These
define a local tangent space at $\theta$, which we can partition into
orthogonal subspaces of $N_{\mathrm{p}}^{\mathrm{gauge}}$ _gauge directions_
that are tangent to the gauge orbit on which $\vec{\theta}$ lies, and
$N_{\mathrm{p}}^{\mathrm{nongauge}}$ _non-gauge directions_ that are normal to
the gauge orbit (see appendix A.1). It follows trivially that
$N_{\mathrm{p}}^{\mathrm{gauge}}+N_{\mathrm{p}}^{\mathrm{nongauge}}=N_{\mathrm{p}}$.
This partition of $N_{\mathrm{p}}$ is same at almost all points $\vec{\theta}$
(the exceptions are the singular points corresponding to gate sets with
degenerate gates), allowing us to view $\mathcal{P}$ mathematically as a
_fiber bundle_.

The fully parameterized gate set model has a parameter space with dimension

$N_{\mathrm{p}}^{\mathrm{full}}=N_{\mathrm{G}}d^{4}+\left(N_{\rho}+\sum_{m=1}^{N_{\mathrm{M}}}N^{(m)}_{\mathrm{E}}\right)d^{2},$
(68)

and it generally has $d^{2}$ gauge degrees of freedom exceptions occur when
one or more operators commute with every operation in the gate set.

####  V.1.2 TP and CPTP constrained models

Quantum theory requires density matrices to have unit trace, and the
operations acting on them to be trace-preserving (TP). These are constraints
on $\mathcal{G}$ which can be used to define a smaller gate set model. The TP
constraint corresponds to locking the first row of every superoperator to be
$[1,0,\ldots 0]$ and the first element of every state preparation vector to
equal $1/\sqrt{d}$ (since $\mathrm{Tr}(B_{0})=d/\sqrt{d}=\sqrt{d}$, cf. Sec.