Graphically Structured Diffusion Models

Christian Weilbach William Harvey Frank Wood

Department of Computer Science University of British Columbia Vancouver,
Canada<EMAIL_ADDRESS>
###### Abstract

We introduce a framework for automatically defining and learning deep
generative models with problem-specific structure. We tackle problem domains
that are more traditionally solved by algorithms such as sorting, constraint
satisfaction for Sudoku, and matrix factorization. Concretely, we train
diffusion models with an architecture tailored to the problem specification.
This problem specification should contain a graphical model describing
relationships between variables, and often benefits from explicit
representation of subcomputations. Permutation invariances can also be
exploited. Across a diverse set of experiments we improve the scaling
relationship between problem dimension and our model’s performance, in terms
of both training time and final accuracy.

##  1 Introduction

There has been a recent wave of progress in deep generative modelling,
especially with the emergence of diffusion models (DMs) [Sohl-Dickstein et
al., 2015, Ho et al., 2020]. Compelling conditional variants can take as input
text [Rombach et al., 2022], previous video frames [Ho et al., 2022], or
subsets of their output dimensions [Tashiro et al., 2021]. These successes
come from the considerable effort that has been spent developing models to
process data streams matching the human sensorium. In short, within a certain
problem domain, DMs provide a flexible mapping from inputs to outputs. It
remains unclear how similar models can be applied to the highly-structured
problem domains more typically considered the domain of algorithms. Take the
example of matrix factorization, where the input is a matrix and the desired
output is two matrices which multiply to give the input. A typical approach to
tackle matrix factorization is then to acquire a real or synthetic dataset of
input-output pairs to train a mapping. Unlike traditional algorithm design,
this approach must learn all necessary problem structure from data. For highly
structured problem domains, the required training compute will therefore be
large and scale poorly with problem dimensionality.

A natural framework to reason about structure in the probabilistic setting of
deep generative models is that of graphical models [Koller and Friedman,
2009]. We propose Graphically Structured Diffusion Models, or GSDMs, which
have an architecture based on a graphical model representation of a dataset.
We find that incorporating structure from the graphical model can lead to
architectures that scale well with problem dimension. This includes the
ability to deal with problems of varying dimension by scaling the graphical
model correspondingly. We design the framework to be accessible and widely-
applicable and therefore do not prescribe a specific form of graphical model.
We find that the quality of the GSDM model is consistent across reasonable
choices of graphical model.

Structured computation graphs often contain “intermediate variables,”
variables (stochastic or deterministic) whose values are computed as part of a
model or algorithm, but that do not directly form the input or output. When
these are present in a graphical model, GDSM is able to leverage both their
values and the relevant graphical structure to, roughly speaking, break down
the learning of a complex problem into the learning of multiple simpler
problems. This helps GSDM to exhibit a more graceful scaling with problem
dimension than pure DM baselines.

Figure 1: An application of our framework to binary-continuous matrix
factorization. In the first panel the computational graph of the
multiplication of the continuous matrix ${\bm{A}}\in{\mathbb{R}}^{6\times 2}$
and the binary matrix ${\bm{R}}\in{\mathbb{R}}^{2\times 5}$ is expanded as a
probabilistic graphical model in which intermediate products ${\bm{C}}$ are
summed to give ${\bm{E}}={\bm{A}}{\bm{R}}$. This graph is used to create a
structured attention mask ${\bm{M}}$, in which we highlight 1’s with the color
of the corresponding graphical model edge and self-edges in white. In the
third panel the projection into the sparsely-structured neural network guiding
the diffusion process is illustrated. In the bottom the translation of
permutation invariances of the probability distribution into the embeddings of
${\mathbf{x}}_{t}$ and ${\mathbf{y}}$ is shown (Section 3.6).

To summarize our contributions, we (1) describe how to automatically derive a
structured, sparse attention mechanism from a graphical model representation,
and release an efficient implementation (Appendix
C)111https://github.com/plai-group/gsdm.. (2) We showcase the integration of a
generative model’s intermediate variables into GSDM and empirically
demonstrate their benefits. (3) We present a method for translating known
permutation invariances of a model into permutation invariances of GSDM. (4)
We demonstrate that GSDM architectures can solve hard combinatorial problems.
(5) As part of the experiments we also provide a new approximate algorithm for
binary continuous matrix factorization.

##  2 Background

###  2.1 Conditional diffusion models

Defining ${\mathbf{x}}_{0}$ to be data sampled from a data distribution
$q({\mathbf{x}}_{0})$, a diffusion process constructs a chain
${\mathbf{x}}_{0:T}$ with noise added at each stage by the transition
distribution

$q({\mathbf{x}}_{t}|{\mathbf{x}}_{t-1})={\mathcal{N}}({\mathbf{x}}_{t};\sqrt{1-\beta_{t}}{\mathbf{x}}_{t-1},\beta_{t}{\mathbf{I}})$
(1)

leading to the joint distribution

$q({\mathbf{x}}_{0:T})=q({\mathbf{x}}_{0})\prod_{t=1}^{T}q({\mathbf{x}}_{t}|{\mathbf{x}}_{t-1}).$
(2)

The sequence $\beta_{1:T}$ controls the amount of noise added at each step
and, along with $T$ itself, is chosen to be large enough that the marginal
$q({\mathbf{x}}_{T}|{\mathbf{x}}_{0})$ resulting from Eq. 1 is approximately a
unit Gaussian for any ${\mathbf{x}}_{0}$.

This diffusion process inspires a diffusion model [Sohl-Dickstein et al.,
2015, Ho et al., 2020, Song et al., 2021b], or DM, which approximately
“inverts” it using a neural network that outputs
$p_{\theta}({\mathbf{x}}_{t-1}|{\mathbf{x}}_{t})\approx
q({\mathbf{x}}_{t-1}|{\mathbf{x}}_{t})$. We can sample from a diffusion model
by first sampling ${\mathbf{x}}_{T}\sim
p({\mathbf{x}}_{T})={\mathcal{N}}(\mathbf{0},\mathbf{I})$ and then sampling
${\mathbf{x}}_{t-1}\sim p_{\theta}(\cdot|{\mathbf{x}}_{t})$ for each
$t=T,\ldots,1$, eventually sampling ${\mathbf{x}}_{0}$. In the conditional DM
variant [Tashiro et al., 2021] the neural network is additionally conditioned
on information ${\mathbf{y}}$ so that the modelled distribution is

$p_{\theta}({\mathbf{x}}_{0:T}|{\mathbf{y}})=p({\mathbf{x}}_{T})\prod_{i=1}^{T}p_{\theta}({\mathbf{x}}_{t-1}|{\mathbf{x}}_{t},{\mathbf{y}}).$
(3)

The transitions $p_{\theta}({\mathbf{x}}_{t-1}|{\mathbf{x}}_{t},{\mathbf{y}})$
are typically approximated by a Gaussian with non-learned diagonal covariance,
and so the learning problem is simply to fit the Gaussian’s mean. Ho et al.
[2020] parameterize this mean as an affine function of
$\mathbb{E}[{\mathbf{x}}_{0}|{\mathbf{x}}_{t},{\mathbf{y}}]$ and, by doing so,
reduce the problem to fitting an estimator of ${\mathbf{x}}_{0}$ from
${\mathbf{x}}_{t}$ and ${\mathbf{y}}$ with the loss

$\mathcal{L}(\theta)=\sum_{t=1}^{T}\mathbb{E}_{q({\mathbf{x}}_{0},{\mathbf{x}}_{t},{\mathbf{y}})}\left[\lambda(t)\cdot\lVert\hat{{\mathbf{x}}}_{\theta}({\mathbf{x}}_{t},{\mathbf{y}},t)-{\mathbf{x}}_{0}\rVert_{2}^{2}\right].$
(4)

Ho et al. [2020], Song et al. [2021a] show that there exists a weighting
function $\lambda(t)$ such that this loss is (the negative of) a lower-bound
on the marginal log-likelihood $\log
p_{\theta}({\mathbf{x}}_{0}|{\mathbf{y}})$. We instead use uniform weights
$\lambda(t)=1$ which has been shown to give better results in practice [Ho et
al., 2020].

###  2.2 Transformer architecture

Figure 2: Circuit diagram for $\hat{{\mathbf{x}}}_{\theta}$ evaluated at time
$t$ as described in Section 2.2. The dashed box represents one repeatable
attention layer $i$ that acts on an embedding (its residual connection is not
shown). The light grey boxes show parts of the circuit that operate on each
dimension independently while the dark grey box shows the masked pairwise
attention mechanism.

A detailed circuit diagram of our neural architecture for
$\hat{{\mathbf{x}}}_{\theta}$ is shown in Figure 2, where learnable neural
network mappings are denoted by $m$’s. The following is happening at a fixed
diffusion time step $t$. We view the neural network’s input
$({\mathbf{x}}_{t},{\mathbf{y}})$ as a list $\\{x_{1},\ldots,x_{n}\\}$, for
which each element $x_{j}$ corresponds to one node in the graphical model of
interest and comes with side-information denoting which node it corresponds to
and whether or not it is observed (i.e. whether it belongs to
${\mathbf{x}}_{t}$ or ${\mathbf{y}}$). Interactions between these elements are
governed by self-attention based transformer layers [Vaswani et al., 2017].
Before the first attention layer we embed $x_{j}$ as $e_{j}^{0}=m_{e}(x_{j})$,
add an embedding $e_{v,j}$ describing which graphical model node it belongs to
and, for observed variables (like $x_{n}$ in Figure 2), also add a single
globally-shared embedding $e_{o}$. Each transformer layer $i\in\\{1,...,L\\}$
first applies a residual neural network [He et al., 2016] $m^{i}_{r}$ on each
of the embedded dimensions $e^{i-1}_{j}$ independently,
$r^{i}_{j}=m^{i}_{r}(e^{i-1}_{j},t)$. Inside the attention each $r^{i}_{j}$ is
then projected into a query $q^{i}_{j}=m^{i}_{q}(r^{i}_{j})$, key
$k^{i}_{j}=m^{i}_{k}(r^{i}_{j})$ and value $v^{i}_{j}=m^{i}_{v}(r^{i}_{j})$,
all in $\mathbb{R}^{d}$. Stacking these $n$ values yields the matrices
${\bm{Q}}^{i},{\bm{K}}^{i},{\bm{V}}^{i}\in\mathbb{R}^{n\times d}$. The self-
attention, shown in the dark grey box in Figure 2, is then calculated as

$\displaystyle{{\bm{e}}}^{i}$
$\displaystyle={{\bm{e}}}^{i-1}+{\bm{W}}^{i}{\bm{V}}^{i}={{\bm{e}}}^{i-1}+\mathrm{softmax}\left({\bm{Q}}^{i}{\bm{K}}^{iT}\right){\bm{V}}^{i}$
(5)

where the addition of ${{\bm{e}}}^{i-1}$ corresponds to a residual connection.
We note that ${\bm{Q}}^{i}{\bm{K}}^{iT}$ yields a pairwise interaction matrix
which lets us impose an additional attention mask ${\bm{M}}$ before
calculating the output
${{\bm{e}}}^{i}={{\bm{e}}}^{i-1}+\mathrm{softmax}\left({\bm{M}}\odot{\bm{Q}}^{i}{\bm{K}}^{iT}\right){\bm{V}}^{i}$.
This masking interface is central to structure the flow of information between
graphical model nodes in Section 3.1 .

###  2.3 Permutation invariance

Large probabilistic models often contain permutation invariance, in the sense
that the joint probability density $q({\mathbf{x}}_{0})$ is invariant to
permutations of certain indices [Bloem-Reddy and Teh, 2020]. For example the
matrix multiplication in Fig. 1 is invariant with respect to permutations of
any of the plate indices.222In general, plate notation implies permutation
invariance as long as no link functions depend on the plate indices
themselves. If the joint probability density is invariant to a particular
permutation, this can be enforced in a distribution modelled by a DM by making
the neural network architecture equivariant to the same permutation [Hoogeboom
et al., 2022]. We show how to encode such equivariances in GSDM in Section
3.6.

##  3 Method

A GSDM is a DM which operates over the nodes of a graphical model and whose
architecture reflects side information, chiefly in the form of a graphical
model structure. This section describes both how to provide useful side
information and the process for constructing GSDM from given side information.

###  3.1 Structure from graphical models

Integrating a graphical model for the data distribution speeds up learning and
increases computational efficiency, and these benefits scale with problem
dimension. If only a data set without a generative model is available,
additional reasoning is required to define a graphical structure. We emphasize
that there is considerable flexibility in the specification of this structure.
It can be written as a directed graphical model, undirected graphical model,
factor graph (where group constraints are represented by connecting all nodes
within the group) or a combination of these. We find in Section 4.3 that GSDM
is not sensitive to small changes in the specification of the graphical model
and that there can be multiple modeling perspectives yielding similar GSDM
performance. In general, we use the most intuitive graphical model that we can
come up with for each problem, whether directed or undirected. One way to
derive a directed model is to follow the definition of a causal forward model
for an inverse problem where the terminal node will be the input to our
approximate algorithm, as for BCMF in Fig. 1. An undirected graphical model
can be seen as implicitly grouping nodes by constraints, e.g. for Sudoku with
row, column and block constraints (Appendix D). Note that if the data is
simulated and source code is available then we can automatically extract the
simulator’s compute graph as a graphical model (Appendix B).

Given a graphical model, we train a DM to model the joint distribution of its
nodes, and use the edges to construct attention masks ${\bm{M}}$ for the DM’s
transformer layers. Precisely, we allow variable $i$ to attend to variable $j$
iff there is an edge between node $i$ and node $j$, and irrespective of the
direction of the edge or whether it has a direction.

###  3.2 Faithful structured attention

Figure 3: Example graphical model of
$q({\mathbf{x}}_{0})q({\mathbf{x}}_{t}|{\mathbf{x}}_{0})$. Nodes are
latent/blue if in ${\mathbf{x}}_{0}$, observed/orange if in
${\mathbf{x}}_{t}$.

According to the DM loss in Eq. 4, the neural network
$\hat{{\mathbf{x}}}_{\theta}$ is tasked at each timestep $t=t^{\prime}$ with
predicting ${\mathbf{x}}_{0}$ from ${\mathbf{x}}_{t^{\prime}}$. Figure 3 shows
an example graphical model factorization for
$q({\mathbf{x}}_{0}|{\mathbf{x}}_{t^{\prime}})$ corresponding to this task.
Since ${\mathbf{x}}_{t^{\prime}}$ can be generated by adding independent noise
to each dimension of ${\mathbf{x}}_{0}$, this graphical model is derived from
the graphical model of the data distribution $q({\mathbf{x}}_{0})$ by simply
adding an edge from each variable in ${\mathbf{x}}_{0}$ to the corresponding
variable in ${\mathbf{x}}_{t^{\prime}}$.

######  Theorem 1 (Dependence in diffusion models).

Given that the data distribution $q({\mathbf{x}}_{0})$ is represented by a
connected graphical model ${\mathcal{G}}=({\mathcal{X}},{\mathcal{A}})$, with
nodes ${\mathcal{X}}$ and edges ${\mathcal{A}}$, we can represent the
temporally combined graphical model at times $t=0$ and $t=t^{\prime}$ as
${\mathcal{G}}_{DM}=(\\{{\mathbf{x}}_{t^{\prime}}^{i}\\}_{i}\cup\\{{\mathbf{x}}_{0}^{i}\\}_{i},\\{({\mathbf{x}}_{0}^{i},{\mathbf{x}}_{t^{\prime}}^{i})\\}_{i}\cup{\mathcal{A}})$.
Then there are no pairs $i,j$ such that ${\mathbf{x}}_{0}^{i}$ can be assumed
independent of ${\mathbf{x}}_{t^{\prime}}^{j}$ after conditioning on all other
dimensions of ${\mathbf{x}}_{t^{\prime}}$. In other words, for any $i,j$ pair,
we have to assume
${\mathbf{x}}_{0}^{i}\not\\!\perp\\!\\!\\!\perp{\mathbf{x}}_{t^{\prime}}^{j}\mid{\mathbf{x}}_{t^{\prime}}^{-j}$,
where ${\mathbf{x}}_{t^{\prime}}^{-j}$ stands for all nodes in
${\mathbf{x}}_{t^{\prime}}$ except node $j$.

###### Proof.

For any $j$, ${\mathbf{x}}_{t^{\prime}}^{j}$ is directly connected to
${\mathbf{x}}_{0}^{j}$. Since we assumed that the graphical model for
$q({\mathbf{x}}_{0})$ is connected, there will further be a path from
${\mathbf{x}}_{0}^{j}$ to ${\mathbf{x}}_{0}^{i}$ which does not pass through
any conditioned on nodes for any $i$. Therefore
${\mathbf{x}}_{t^{\prime}}^{j}$ cannot be d-separated from
${\mathbf{x}}_{0}^{i}$ [Koller and Friedman, 2009]. ∎

The consequence of Theorem 1 is that every node in the neural network output
$\hat{{\mathbf{x}}}_{\theta}({\mathbf{x}}_{t},{\mathbf{y}},t)$ should depend
on every node in its input ${\mathbf{x}}_{t}$. Neural network architectures
without this property might not be able to faithfully predict
${\mathbf{x}}_{0}$ given ${\mathbf{x}}_{t}$ and so might not faithfully model
$q({\mathbf{x}}_{0})$. This consideration motivated our previously-described
design choice that variable $i$ can attend to $j$ if there is any edge between
them, irrespective of the direction of the edge. Otherwise, if the graphical
model is directed and acyclic there will not be a path between every pair of
nodes. This would cause GSDM to make false independence assumptions, which we
show impacts performance in Appendix H. We also note that if node $i$ is not
directly connected to node $j$ in our attention mask, information about node
$i$ may have to be passed to node $j$ via other nodes. Since messages are only
passed along one edge per transformer layer, the number of transformer layers
should be chosen to be at least as great as the maximum path length in the
symmetrized graphical model.

To reduce our memory usage and computation compared to a dense matrix
multiplication of the masked matrix we provide an efficient sparse attention
implementation as described in Appendix C. The computational cost of our
approximate algorithms is ${\mathcal{O}}(nmL)$ for $L$ attention layers, where
$n$ is the number of dimensions and $m$ is the number of entries in the
densest row of ${\bm{M}}$.

Figure 4: Number of iterations to reach 100% accuracy, validating on 16
examples every 500 iterations.

###  3.3 Intermediate variables

When translating a generative model into a graphical model, the modeler must
choose how fine or coarse the graphical representation should be by selecting
which, and how many, “intermediate” variables are included and therefore
modelled by GSDM. The optimal choice of granularity is model-specific but we
argue that fine-grained representations are often better for GSDMs due to (1)
the better learning signal that we describe below and (2) the reduced
computational cost of sparse attention that is related to the number of
graphical model edges more so than the number of nodes, and so is not
necessarily increased by adding intermediate variables.

Experiment | Graphical model | Conditioned on | Struct. attn. | Interm. vars | Disc. & cont. | Emb. sharing
---|---|---|---|---|---|---
BCMF | directed | ${\bm{E}}$ | ✓ | ✓ | ✓ | (✓)
Sudoku | factor graph | random subset | (✓) | - | - | (✓)
Sorting | mixed | ${\bm{u}}$ | ✓ | ✓ | ✓ | (✓)
Boolean | directed | input | ✓ | ✓ | - | -
Table 1: Problems tackled. A tick, ✓, highlights where our contributions were
necessary to learn at all or scale with problem dimension and (✓) where they
improved performance. The improvements from structured attention and
intermediate variables are shown in Fig. 4 and Fig. 7.

GSDM can be much easier to train using a fine-grained representation because
each node in a fine-grained graphical model will typically have few parents
and be a relatively simple function of its parents.333To take this argument to
an extreme, we could represent a generative model with a compute graph where
each node represents a single output of a CPU’s arithmetic logic unit (ALU).
Since the ALU operates on pairs of inputs, each node will have at most two
parents and each link function will be simple enough to execute in one CPU
cycle. Since the DM training objective involves predicting (and receiving
supervision for) the value of every node, approximately we can imagine each
link function as being learned in parallel during training. From this
perspective, making the link functions very simple means that DM training is
similar to learning many very simple functions in parallel rather than, e.g.,
one complex function that would require many training steps.

As an illustrative example, consider a Boolean logic circuit which takes an
input of size $2^{n}$. The input is split into pairs and each pair is mapped
through a logic gate to give an output of size $2^{n-1}$. After $n$ layers and
a total of $2^{n}-1$ logic gates, there is a single output. Suppose that you
know that each gate is randomly assigned to be either an OR gate or an AND
gate, and you wish to infer which from data. If the data contains only the
inputs and the single output, it contains only 1 bit of information. Inferring
the function computed by each of the ${\mathcal{O}}(2^{n})$ gates will
therefore require ${\mathcal{O}}(2^{n})$ data points. On the other hand, if
the data contains intermediate variables in the form of the output of every
logic gate, each data point contains ${\mathcal{O}}(2^{n})$ bits of
information so the task may be solvable with few data points. Figure 4 shows
that this reasoning holds up when we train a DM on this example. Without
intermediate variables, the number of training iterations needed scales
exponentially with $n$. With the combination of intermediate variables and
structured attention, however, the training behaviour is fundamentally changed
to scale more gracefully with $n$.

###  3.4 Handling mixed continuous/discrete variables

Our simple approach to combining discrete and continuous variables in a DM is
to map the discrete variables to one-hot encodings in a continuous space
before running the diffusion process. Sampled one-hot encodings can then be
mapped back to the discrete space with an $\operatorname*{arg\,max}$. We
project the entire (diffused) one-hot encoding for each discrete variable into
a single embedding before passing it into the transformer, so that the
transformer performs the same amount of computation for a discrete variable as
for a continuous variable.

###  3.5 Flexible conditioning

Optimizing the DM loss in Eq. 4 requires a partitioning of data into latent
variables (outputs) ${\mathbf{x}}_{0}$, and observed variables (inputs)
${\mathbf{y}}$. While traditional amortized inference requires choosing this
partitioning before training [Gershman and Goodman, 2014, Ritchie et al.,
2016, Le et al., 2017], our approach allows for flexible conditioning by
training over a distribution of partitions so that certain variables can be
latent in some test examples and observed in others. The neural network
distinguishes between variables in ${\mathbf{x}}_{t}$ and ${\mathbf{y}}$ via a
learned observation embedding vector ${{\bm{e}}}_{o}$ that is added to the
embeddings of observed variables. This approach also naturally allows us to
deal with missing values at inference time, something that neither standard
algorithms nor traditional amortized inference artifacts can deal with.

###  3.6 Embeddings and varying dimensionality

GSDM’s architecture contains positional embeddings which inform the neural
network which inputs correspond to which graphical model nodes. The simplest
variation of GSDM learns one embedding per graphical model node independently,
and we call this approach independent embeddings, or IE. An issue with IE is
that it cannot generally be adapted to changing input dimension. For example,
a network trained with IE to operate on inputs of size length 10 couldn’t be
applied to inputs of length 11. As a generic way to tackle problems defined
over variable-size arrays we suggest array embeddings, or AE. Creating these
involves analyzing the problem to group together variables that are in the
same (potentially multi-dimensional) array, treating scalars as arrays of size
1 in each dimension. We then create the embedding for each variable as the sum
of a shared array embedding, learned independently for every array, and a
sinusoidal positional embedding [Vaswani et al., 2017] for its position within
an array.

For models exhibiting the permutation invariances discussed in Section 2.3 we
can optionally use exchangeable embeddings, or EE. To do so for any index that
a model is permutation invariant with respect to, we share embeddings between
all variables which are replicas of each other along that index. For example,
the matrix multiplication in Fig. 1 is invariant to permutations of $i$ and
$k$ so we share embeddings across all $A_{ik}$. In combination with the
structured attention mechanism (which prevents communication between nodes
with different indices) this renders the neural network equivariant with
respect to these permutations. It also allows the number of repetitions of
each plate to be changed arbitrarily, allowing generalisation for models
including our matrix factorization experiment. We derive why the resulting
GSDM is fully permutation equivariant in Appendix I.

Figure 5: Error vs problem dimension for GSDM on binary continuous matrix
factorization. We show the root mean square error between the observed matrix
${\bm{E}}$ and the product of the sampled ${\bm{A}}$ and ${\bm{R}}$. The
colorbar for each value of $k$ is scaled so that “yellow” corresponds to the
error achieved by a baseline which samples ${\bm{A}}$ and ${\bm{R}}$ from the
prior, ignoring ${\bm{E}}$. Despite never seeing a value of $n$, $m$, or $k$
larger than $10$ during training, GSDM scales well to much larger values of
$m$ and $n$. When they grow large enough, GSDM runs out of GPU memory. We mark
entries where this occurred in white. Figure 6: Two factorizations sampled by
GSDM with $m=5$, $n=10$ and $k=7$. Each row in the plot shows the inferred
${\bm{A}}$, ${\bm{R}}$ and the respective reconstruction
$\hat{{\bm{E}}}={\bm{R}}{\bm{A}}$ on the left and the ${\bm{E}}$ provided as
input on the right. Intermediate variables ${\bm{C}}$ are omitted here.

##  4 Experiments

##### Binary continuous matrix factorization (BCMF)

Our first experiment tackles the challenging BCMF problem, where we factorize
a continuous matrix into one binary and one continuous component. Our BCMF
generative model samples a binary matrix ${\bm{R}}\in\mathbb{R}^{k\times n}$
elementwise from $\text{Bernoulli}(0.3)$ and a continuous matrix
${\bm{A}}\in\mathbb{R}^{m\times k}$ from an elementwise $\text{Uniform}(0,1)$
prior. The BCMF task is to infer these conditioned on
${\bm{E}}:={\bm{A}}{\bm{R}}$. To obtain intermediate variables as discussed in
Section 3.3 we break the matrix multiplication into two steps,
$C_{ijk}:=A_{ik}R_{kj}$ and then $E_{ij}:=\sum_{k}C_{ijk}$. Our latent
variables ${\mathbf{x}}_{0}$ are therefore the combination of all elements of
${\bm{R}}$, ${\bm{A}}$, and ${\bm{C}}$ and the observed variables
${\mathbf{y}}$ are the elements of ${\bm{E}}$. Fig. 6 shows that our learned
GSDM can find factorisations that are consistent with the observations.
Furthermore, we show in Fig. 5 that GSDM scales well, even to larger $m$ and
$n$. The model was trained on ranges uniformly sampled in the range $1$ to
$10$ for $m$, $n$ and $k$, but generalizes to $20$ times larger $m$ and $n$.

##### Sudoku

A Sudoku grid is a $9\times 9$ array of numbers such that each number is in
$\\{1,\ldots,9\\}$ and no two numbers in the same row, column, or $3\times 3$
block are the same. Solving a Sudoku, i.e. completing one given a partially-
filled in grid, is a difficult problem for deep learning methods, and has
previously been addressed with hand-designed modules for reasoning [Palm et
al., 2018] or semi-definite programming [Wang et al., 2019]. We use GSDM
without such custom modules for combinatorial reasoning. We model a Sudoku
with a factor graph. There is one factor for each row, column, and block
representing the constraint that it contains all numbers $\\{1,\ldots,9\\}$.
The resulting GSDM attention mask lets each variable attend to all other
variables in the same row, column, and block. Our data generator444We
generated complete Sudokus with a port of
https://turtletoy.net/turtle/5098380d82 creates complete $9\times 9$ Sudokus.
In order to train GSDM as a Sudoku solver for arbitrary Sudoku puzzles, we
create each training example by randomly partitioning the grid into latent and
observed portions by sampling $n_{o}$ uniformly from 0 to 80 and then
uniformly sampling $n_{o}$ variables to observe. We show samples from GSDM in
Fig. 8, which exhibit diversity when multiple solutions exist. In our
evaluations, the samples were valid Sudokus $76\%$ of the time when no cells
were observed; $55\%$ of the time when 16 of the 81 cells were observed;
$99\%$ of the time when 40 cells were observed; and always when 64 of the 81
cells were observed.

(a) BCMF error vs dimensionality.

(b) Sudoku performance throughout training.

(c) Sorting performance throughout training.

Figure 7: Ablations over the use of structured attention, intermediate
variables, and different types of embedding sharing. In (a) we show the test
error on BCMF as each dimension is varied. While varying $n$, we set $m=16$,
$k=8$. While varying $m$, we set $n=16$, $k=8$. While varying $k$, we set
$n=m=16$. The dashed line marks the best error with constant estimates of
${\bm{A}}$ and ${\bm{R}}$. Combining intermediate variables with structured
attention greatly reduces the error, and prevents it from increasing with the
rank $k$. In (b) we show the proportion of unconditionally-generated Sudokus
that are valid over the course of training. For GSDM this begins to decrease
halfway through training, but the accuracy for conditionally-generated Sudokus
continues to rise. In (c) we measure how well sorted lists match the ground-
truth. In all cases, attention and intermediate variables make training much
faster. AE provides a significant improvement over IE, while EE provides a
small further improvement over AE.

##### Sorting

We demonstrate GSDM on sorting as evidence of it’s broad applicability to a
wide variety of problems. Our graphical model is as follows. (1) Sample an
unsorted list ${\mathbf{u}}\in{\bm{R}}^{n}$. with each element $u_{i}$ sampled
from a unit normal. (2) Sample a permutation matrix
${\bm{P}}\in\\{0,1\\}^{n\times n}$. Similarly to the Sudoku case, factors on
each row and column enforce the constraints that there is a single 1 in each.
(3) Multiply ${\bm{P}}$ and ${\mathbf{u}}$. We integrate intermediate
variables $C_{ij}:=P_{ij}u_{j}$ and sum them as $s_{i}:=\sum_{j}C_{ij}$ to
yield ${\mathbf{s}}$. (4) We use factors between each pair of elements in
${\mathbf{s}}$ to enforce that it is sorted. This graphical model is different
to, and simpler than, our true data generation procedure in which we obtain
${\mathbf{s}}$ and ${\bm{P}}$ with a pre-existing sorting algorithm. We
emphasise that this approach fits into the GSDM framework nonetheless since
the graphical model is a valid specification of the independences in the data
distribution. We train GSDM to sort lists with sizes ranging from 2 to 40. We
measure it’s performance as the mismatch between the real and sampled
permutation matrices ${\bm{P}}$, and plot progress throughout training in Fig.
7(c). During evaluation, GSDM made errors on only two of 80 test examples. In
each of these two cases it confused a single pair of elements that were
$2\times 10^{-3}$ apart in a list of length $20$ and $1\times 10^{-5}$ apart
in a list of length $30$.

##### Boolean

We additionally use the Boolean circuit described in Section 3.3 (Fig. 4) to
demonstrate GSDM’s ability to learn structured functions over many variables.

###  4.1 Effect of structured attention and intermediate variables

All of our experiments rely on structured attention for their good
performance, and the positive effect remains even after removing intermediate
variables. We saw this for the Boolean circuit in Section 3.3 and here show
experiments for Sudoku in Fig. 7(b), sorting lists of length $n=20$ in Fig.
7(c), and BCMF of various dimensionalities in Fig. 7(a). These are relatively
simple ablations in that we do not vary the dimensionality during training
but, even so, imposing structure leads to significant improvements in each
case, especially in combination with intermediate variables.

We ablate intermediate variables in the same figures. In combination with
structured attention, including intermediate variables is extremely helpful in
all cases. For BCMF the intermediate variables reduced the error in Fig. 7(a)
by an average factor of roughly $4.3$. For the Boolean circuit, structured
attention removes the exponential blow-up in the number of required training
iterations. For sorting, intermediate variables sped up the time to reach
$99\%$ accuracy by a factor of $3$.

Sparsely structured attention also makes the network faster to execute. Even
despite the substantial number of intermediate variables needed to take
advantage of sparsity in e.g. BCMF, we show in Appendix G that the
computational complexity of GSDM with intermediate variables and structured
attention is better than that of a naive approach with neither in all
experiments with parameterizable size (i.e. all but Sudoku).

Figure 8: Two Sudoku solutions conditioned on the same 16 observed cells (in
bold).

###  4.2 Effect of embedding-sharing

Three of our problems contain permutation invariances exploitable by
embedding-sharing. Our sorting model is invariant to the order of
${\mathbf{u}}$, Sudoku to various row/column permutations, and BCMF to the
permutations of any of the plate indices in Fig. 1. We see in Fig. 7(c) that
incorporating these invariances with EE gives much faster training than using
independent embeddings. Even without specifying the invariances, AE can be
used to obtain most of the benefit. The same story can be seen in Fig. 7(b)
for Sudoku. All of our results for BCMF use EE, and we emphasise that the
results showing generalization with respect to problem dimensions would not be
possible without embedding sharing.

###  4.3 Robustness to choice of graphical model

There can be a degree of subjectivity in the choice of graphical model for a
given problem. For instance, in sorting we represented the constraint that
${\mathbf{s}}$ is sorted with pairwise constraints between neighbouring
elements. Another reasonable graphical model may have imposed a factor over
all nodes of ${\mathbf{s}}$, making ${\mathbf{s}}$ fully-connected in our
attention mask. We show in Fig. 9 that this choice makes negligible difference
to GSDM’s performance. Furthermore, some modeling choices make no difference
at all to GSDM. For example we sampled ${\mathbf{u}}$ and ${\bm{P}}$ first and
then computed ${\mathbf{s}}:={\bm{P}}{\mathbf{u}}$, but someone else may have
sampled ${\mathbf{s}}$ first (with factors to ensure it is sorted) and then
${\bm{P}}$ before computing ${\mathbf{u}}:={\bm{P}}{\mathbf{s}}$. These two
choices lead to identical GSDM networks because the only difference is the
direction of edges in the graphical model (which is irrelevant when they are
symmetrized to create the attention mask). Figure 9 also shows that GSDM can
be robust to a misspecified model, “Unconstrained ${\mathbf{s}}$”, where
constraints are not imposed on ${\mathbf{s}}$. The “Random” baseline, however,
in which each node is allowed to attend to 20 other nodes sampled at random,
performs much worse.

Figure 9: Ablations of GSDM with different graphical model structures for
sorting. The first three lines, which represent constraints on ${\mathbf{s}}$
in different ways described in Section 4.3, are on top of eachother and
quickly reach $100\%$ accuracy. This speaks to the robustness of GSDM to
different ways of specifying a graphical model. Randomising the attention mask
works very poorly in comparison.

##  5 Related work

Sparse attention mechanisms have been introduced in several forms, either to
save memory footprint [Dai et al., 2019, Kitaev et al., 2020, Roy et al.,
2020] or computational cost [Child et al., 2019, Beltagy et al., 2020, Zaheer
et al., 2021]. A recent review is provided in Tay et al. [2022].

The framework of amortized inference [Gershman and Goodman, 2014, Ritchie et
al., 2016] and probabilistic programming [Le et al., 2017, van de Meent et
al., 2018] provides the framework for our approach. But instead of requiring a
full probabilistic model we relax the requirement to only specify the
graphical model structure. Weilbach et al. [2020] use a graphical model to
structure a continuous normalizing flow for inference problems of fixed
dimension. We use the more flexible and scalable DM framework including
discrete variables. We can also work directly with the forward probabilistic
model to avoid computing the potentially denser stochastic inverse of Webb et
al. [2017].

Close in spirit to our work in terms of combinatorial optimization are Selsam
et al. [2019] for general SAT solving and Tönshoff et al. [2022] for general
CSP solving, which also encode the structure between variables and constraints
as message passing neural networks. But these frameworks are only applicable
to deterministic discrete problem classes, while we integrate everything in
the more general probabilistic inference framework.

Our approach to explicitly training conditional diffusion models is based on
that of Tashiro et al. [2021], Harvey et al. [2022]. Various other methods
train unconditional diffusion models before providing approximate conditioning
at test-time [Song et al., 2021b, Ho et al., 2022]. Most DMs are defined over
either purely continuous [Ho et al., 2020] or purely discrete spaces [Austin
et al., 2021, Hoogeboom et al., 2021]. Our approach to mixed-continuous DMs is
similar to that of Hoogeboom et al. [2022] but takes a variational-
dequantization perspective [Ho et al., 2019] so that mapping back to the
discrete space involves taking an $\operatorname*{arg\,max}$ instead of
requiring sampling.

##  6 Discussion

GSDMs automate the reasoning required to create approximate solutions to tasks
as diverse as sorting, Sudoku solving and binary-continuous matrix
factorization. The two main steps needed for our approach are acquiring a data
set and describing the class of problems as a graphical model. If a full
generative model is available our approach additionally benefits in accuracy
and scalability from the access to computed intermediate values. Direct
translation of known permutation invariances of the data distribution further
improve GSDMs. Our work is a step towards the integration of the generality of
statistical conditioning, the expressivity of state-of-the-art diffusion
models with attention mechanisms, and the structural reasoning applied in
programming language theory and algorithm design. Promising directions for
future work include deeper integration of structural knowledge with the
dynamics of diffusion processes, exploitation of syntactic knowledge of
problem descriptions beyond the class of graphical models and integration into
probabilistic programming systems.

#### Acknowledgments

We acknowledge the support of the Natural Sciences and Engineering Research
Council of Canada (NSERC), the Canada CIFAR AI Chairs Program, and the Intel
Parallel Computing Centers program. Additional support was provided by UBC’s
Composites Research Network (CRN), and Data Science Institute (DSI). This
research was enabled in part by technical support and computational resources
provided by WestGrid (www.westgrid.ca), Compute Canada (www.computecanada.ca),
and Advanced Research Computing at the University of British Columbia
(arc.ubc.ca). WH acknowledges support by the University of British Columbia’s
Four Year Doctoral Fellowship (4YF) program.

## References

  * Austin et al. [2021] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg.  Structured denoising diffusion models in discrete state-spaces.  _Advances in Neural Information Processing Systems_ , 34:17981–17993, 2021.
  * Beltagy et al. [2020] Iz Beltagy, Matthew E. Peters, and Arman Cohan.  Longformer: The Long-Document Transformer, December 2020.
  * Bloem-Reddy and Teh [2020] Benjamin Bloem-Reddy and Yee Whye Teh.  Probabilistic Symmetries and Invariant Neural Networks.  _Journal of Machine Learning Research_ , 21(90):1–61, 2020.  ISSN 1533-7928.
  * Child et al. [2019] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever.  Generating Long Sequences with Sparse Transformers, April 2019\.
  * Dai et al. [2019] Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V. Le, and Ruslan Salakhutdinov.  Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context, June 2019.
  * Gershman and Goodman [2014] Samuel Gershman and Noah Goodman.  Amortized inference in probabilistic reasoning.  In _Proceedings of the Cognitive Science Society_ , volume 36, 2014.
  * Harvey et al. [2022] William Harvey, Saeid Naderiparizi, Vaden Masrani, Christian Weilbach, and Frank Wood.  Flexible Diffusion Modeling of Long Videos, May 2022.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016_ , pages 770–778, 2016.  doi: 10.1109/CVPR.2016.90.
  * Ho et al. [2019] Jonathan Ho, Xi Chen, Aravind Srinivas, Yan Duan, and Pieter Abbeel.  Flow++: Improving flow-based generative models with variational dequantization and architecture design.  In _International Conference on Machine Learning_ , pages 2722–2730. PMLR, 2019.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 6840–6851. Curran Associates, Inc., 2020.
  * Ho et al. [2022] Jonathan Ho, Tim Salimans, Alexey Gritsenko, William Chan, Mohammad Norouzi, and David J. Fleet.  Video Diffusion Models.  _arXiv:2204.03458 [cs]_ , April 2022.
  * Hoogeboom et al. [2021] Emiel Hoogeboom, Alexey A Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans.  Autoregressive diffusion models.  _arXiv preprint arXiv:2110.02037_ , 2021.
  * Hoogeboom et al. [2022] Emiel Hoogeboom, Vıctor Garcia Satorras, Clément Vignac, and Max Welling.  Equivariant diffusion for molecule generation in 3d.  In _International Conference on Machine Learning_ , pages 8867–8887. PMLR, 2022.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.
  * Kitaev et al. [2020] Nikita Kitaev, Łukasz Kaiser, and Anselm Levskaya.  Reformer: The Efficient Transformer.  _arXiv:2001.04451 [cs, stat]_ , February 2020.
  * Koller and Friedman [2009] Daphne Koller and Nir Friedman.  _Probabilistic Graphical Models: Principles and Techniques_.  Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2009.  ISBN 978-0-262-01319-2.
  * Le et al. [2017] Tuan Anh Le, Atılım Güneş Baydin, and Frank Wood.  Inference Compilation and Universal Probabilistic Programming.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS)_ , volume 54 of _Proceedings of Machine Learning Research_ , pages 1338–1348, Fort Lauderdale, FL, USA, 2017. PMLR.
  * Palm et al. [2018] Rasmus Palm, Ulrich Paquet, and Ole Winther.  Recurrent Relational Networks.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Ritchie et al. [2016] Daniel Ritchie, Paul Horsfall, and Noah D. Goodman.  Deep Amortized Inference for Probabilistic Programs.  _arXiv:1610.05735 [cs, stat]_ , October 2016.
  * Rombach et al. [2022] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-Resolution Image Synthesis With Latent Diffusion Models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10684–10695, 2022.
  * Roy et al. [2020] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier.  Efficient Content-Based Sparse Attention with Routing Transformers, October 2020.
  * Selsam et al. [2019] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill.  Learning a SAT Solver from Single-Bit Supervision.  _arXiv:1802.03685 [cs]_ , March 2019.
  * Sohl-Dickstein et al. [2015] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep Unsupervised Learning using Nonequilibrium Thermodynamics.  In _Proceedings of the 32nd International Conference on Machine Learning_ , pages 2256–2265. PMLR, June 2015.
  * Song et al. [2021a] Yang Song, Conor Durkan, Iain Murray, and Stefano Ermon.  Maximum Likelihood Training of Score-Based Diffusion Models.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 1415–1428. Curran Associates, Inc., 2021a.
  * Song et al. [2021b] Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-Based Generative Modeling through Stochastic Differential Equations.  _arXiv:2011.13456 [cs, stat]_ , February 2021b.
  * Tashiro et al. [2021] Yusuke Tashiro, Jiaming Song, Yang Song, and Stefano Ermon.  CSDI: Conditional score-based diffusion models for probabilistic time series imputation.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Tay et al. [2022] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler.  Efficient Transformers: A Survey, March 2022.
  * Tönshoff et al. [2022] Jan Tönshoff, Berke Kisin, Jakob Lindner, and Martin Grohe.  One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction.  August 2022.  doi: 10.48550/arXiv.2208.10227.
  * van de Meent et al. [2018] Jan-Willem van de Meent, Brooks Paige, Hongseok Yang, and Frank Wood.  An Introduction to Probabilistic Programming.  _arXiv:1809.10756 [cs, stat]_ , September 2018.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is All you Need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Wang et al. [2019] Po-Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter.  SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver.  _arXiv:1905.12149 [cs, stat]_ , May 2019.
  * Webb et al. [2017] Stefan Webb, Adam Golinski, Robert Zinkov, N. Siddharth, Tom Rainforth, Yee Whye Teh, and Frank Wood.  Faithful Inversion of Generative Models for Effective Amortized Inference.  December 2017.
  * Weilbach et al. [2020] Christian Weilbach, Boyan Beronov, William Harvey, and Frank Wood.  Structured Conditional Continuous Normalizing Flows for Efficient Amortized Inference in Graphical Models.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4441–4451. PMLR, June 2020.
  * Zaheer et al. [2021] Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed.  Big Bird: Transformers for Longer Sequences, January 2021\.

##  Appendix A Experimental details

Table 2: Experimental parameters. For sorting and BCMF we have two sets of hyperparameters: one for the main results and one for the ablations in Figs. 7, 9 and 15. Problem dimension is listed as “varying” where we vary the dimensions between each training batch (sampling $n$ between 2 and 10 for the “Sorting” column and sampling $n$, $m$, and $k$ independently from 1 to 10 for the “BCMF” column) and “multiple” where we show results with different problem dimensionalities. Parameter | Sorting | Sorting abl. | Sudoku | BCMF | BCMF abl. | Boolean
---|---|---|---|---|---|---
Problem dimension | varying | $n=20$ | $9\times 9$ | varying | multiple | multiple
Training time | 1 day | 8 hours | 7-8 hours | 1 day | 1 day |  $40$-$160$ min.
Training iters (1000s) | $140$ |  $300$-$450$ | $500$ | $680$ |  $180$-$680$ | $20$
Batch size | $16$ | $16$ | $32$ | $32$ | $8$ | $16$
Learning rate | $2\text{\times}{10}^{-4}$ | $2\text{\times}{10}^{-4}$ | $2\text{\times}{10}^{-5}$ | $2\text{\times}{10}^{-5}$ | $2\text{\times}{10}^{-5}$ | $2\text{\times}{10}^{-5}$
Embedding dim. | $64$ | $64$ | $128$ | $64$ | $64$ | $64$
# transformer layers | $6$ | $6$ | $6$ | $12$ | $12$ | $12$
# attention heads | $8$ | $1$ | $8$ | $2$ | $2$ | $2$
GPU type | A100 | A5000 | A5000 | A100 | A5000 | A5000

Table 2 presents our experimental parameters. Our ablations on sorting and
BCMF give all networks equal training time, and the number of iterations
therefore varies depending on the time to run the network. We tuned the
learning rates through small grid searches but this yielded only a small
improvement to training. In keeping with common deep learning wisdom, we found
that increasing the embedding dimension and number of transformer layers
improved performance, as does using multiple attention heads. Conversely, the
results degrade gracefully in smaller embedding dimensions, less transformer
layers or varying numbers of attention heads. We set these architectural
hyperparameters with the goal of obtaining networks that were both lightweight
and trained quickly, and tuned them via some experimentation for sorting,
Sudoku, and BCMF. We use NVIDIA A100 GPUs for sorting and BCMF, and smaller
NVIDIA RTX A5000s for all ablations and other problems. We did little tuning
on the batch sizes, other than ensuring that they were large enough to obtain
good GPU utilization and small enough to avoid out-of-memory errors. All data
is sampled synthetically on-the-fly, so data points used in one minibatch are
never repeated in another minibatch. We use $1000$ diffusion timesteps in all
experiments and set the hyperparameters $\beta_{1},\ldots,\beta_{1000}$ using
a linear interpolation schedule [Ho et al., 2020] from $\beta_{1}=10^{-4}$ to
$\beta_{1000}=0.005$. Finally, we use the Adam optimizer with $\beta_{1}=0.9$
and $\beta_{2}=0.999$ [Kingma and Ba, 2015], no weight decay and gradient
clipping at $1.0$. We release code to ensure full reproducibility of our
results.

##  Appendix B Automatic compilation of BCMF

Figure 10: Connectivity mask extracted from BCMF source code. This is the same
structure as in Figure 1 but with permuted indices and before the addition of
the diagonal self-edges.

Building on the probabilistic programming language defined in van de Meent et
al. [2018], we demonstrate a compiler which maps from programs into a
corresponding graphical model structure. We will publish our implementation on
acceptance. We demonstrate it on the program on page 17, which multiplies two
random matrices ${\bm{A}}\in\mathbb{R}^{3\times
2},{\bm{R}}\in\mathbb{R}^{2\times 3}$ similarly to our BCMF experiment.
Samples from Dirac distributions are used to introduce the intermediate nodes
of ${\bm{C}}$ and the terminal nodes of ${\bm{E}}$. Our compiler first
translates it into a graphical model and then into the attention mask as shown
in Figure 10. We envisage a future extension which “compiles” directly from
such source code to a trained GSDM network.

(a) BCMF ($n=4,m=4,k=2$).

(b) Sorting ($n=5$).

(c) Boolean circuit ($n=4$).

(d) BCMF w/o intermediate.

(e) Sorting w/o intermediate.

(f) Boolean circuit w/o intermediate

Figure 11: Attention masks for BCMF, sorting, and the Boolean circuit. All are
shown with (top row) and without (bottom row) intermediate variables. Variable
$i$ can attend to variable $j$ iff the cell in row $i$ and column $j$ is
white. These masks all become more sparse (as measured by proportion of
entries which are non-zero) as the problem dimensionality is increased. Figure
12: Correspondence between a $9\times 9$ Sudoku grid (left) and the resulting
attention mask. We draw a factor for each of the first row, column and block
on the left. On the right the respective entries in the attention structured
mask ${\bm{M}}$ are highlighted with the same color.

##  Appendix C Structured attention

The optimal choice for our structured attention would be sparse matrix
multiplication on the accelerator, unfortunately this was not yet available at
the time of writing of this paper. We therefore provide a packed dense
implementation of structured attention. Our structured attention mechanism
lets us reduce the computational and memory cost of an $n$-dimensional DM from
${\mathcal{O}}(n^{2})$ to $\Theta(nm)$, where $m$ is the maximum number of
ones in any row of our attention mask ${\bm{M}}$. For our BCMF experiment, the
reduction in memory footprint was necessary for us to scale to the dimensions
demonstrated while using a single GPU. Recall that, after computing keys
${\bm{K}}$, values ${\bm{V}}$, and queries ${\bm{Q}}$ (all with shape $n\times
d$, where $d$ is the embedding dimension), and given a attention mask
${\bm{M}}$ with shape $n\times n$, we compute

$\displaystyle{{\bm{e}}}$
$\displaystyle=\mathrm{softmax}\left({\bm{M}}\odot{\bm{Q}}{\bm{K}}^{T}\right){\bm{V}}.$
(6)

If implemented naively with dense matrix multiplications, both computing
${\bm{Q}}{\bm{K}}^{T}$ and the outer multiplication by ${\bm{V}}$ involve
${\mathcal{O}}(n^{2})$ scalar operations. We attempt to avoid this cost while
still taking advantage of the dense matrix multiplications for which GPUs are
designed for. To do so, we project ${\bm{K}}$ and ${\bm{V}}$ into
3-dimensional matrices $\bar{{\bm{K}}}$ and $\bar{{\bm{V}}}$ of shape $n\times
m\times d$. We perform this projection such that $\bar{{\bm{K}}}_{i}$ is a
sequence of the key vectors for every variable that variable $i$ is connected
to. Equivalently, letting $a_{ij}$ be the index of the $j$th variable that
variable $i$ is connected to, $\bar{{\bm{K}}}_{i,j}$ is equal to
${\bm{K}}_{a_{ij}}$. We define $\bar{{\bm{V}}}$ similarly for value vectors.
If variable $i$ connects to less than $m$ entries, then we pad
$\bar{{\bm{K}}}_{i}$ and $\bar{{\bm{V}}}_{i}$ with zeros. We then compute an
$n\times m$ array of unnormalised weights ${\bm{U}}$ (encompassing all
interactions allowed by our attention mask) such that
${\bm{U}}_{i,j}={\bm{Q}}_{i}\cdot\bar{{\bm{K}}}_{i,j}$. Doing so involves only
${\mathcal{O}}(nm)$ operations, rather than the ${\mathcal{O}}(n^{2})$
required to compute dense attention weights. We then mask all entries in
${\bm{U}}$ that were padded by setting them to $-\infty$ before applying the
usual $\text{softmax}({\bm{U}})$ row-wise to get $\bar{{\bm{W}}}$. Finally, we
can compute the output ${h}$ by setting each
${{\bm{e}}}_{i}=\sum_{j}{\bar{{\bm{W}}}_{i,j}\bar{{\bm{V}}}_{j}}$ (again
requiring only ${\mathcal{O}}(nm)$ operations), which is equal to the output
that would be obtained through dense matrix multiplications including the mask
${\bm{M}}$.

##  Appendix D Attention masks

We show attention masks used by GSDM in each of our experiments. Figure 11
compares masks with and without intermediate variables for BCMF, sorting and
the Boolean circuit. Figure 12 explains the derivation of the Sudoku attention
mask from a factor graph.

##  Appendix E Unconditional BCMF

Figure 13: Similar to Figure 5 but with a GSDM model trained to sampled
${\bm{A}}$, ${\bm{R}}$, and ${\bm{E}}$ jointly instead of conditioning on
${\bm{E}}$. We plot a heatmap of the root mean squared error (RMSE) between
the matrix ${\bm{E}}$ and the product ${\bm{A}}{\bm{R}}$. The ranges for each
rank are scaled so that a yellow color represents the expected RMSE if
${\bm{A}}$, ${\bm{R}}$, and ${\bm{E}}$ are all sampled independently from the
prior. Entries colored in white exceed the GPU’s memory limit.

In Figure 13 we plot a heatmap similar to Figure 5 but with a GSDM which
generates unconditional joint samples of ${\bm{A}}$, ${\bm{R}}$, and
${\bm{E}}$ instead of samples conditioned on ${\bm{E}}$. We measure the
mismatch between ${\bm{E}}$ and the product ${\bm{A}}{\bm{R}}$ and,
interestingly, see that it is greater for the unconditional model (for problem
dimensions both inside and outside the training distribution). This suggests
that it may be possible to improve unconditional generation performance by
adjusting the diffusion process hyperparameters so that ${\bm{E}}$ is sampled
early in the diffusion process and then ${\bm{A}}$ and ${\bm{R}}$ are sampled
later, conditioned on ${\bm{E}}$, but we do not attempt to do so here.

|  | Cost of ResNets | Cost of attention | Overall cost | Reduction
---|---|---|---|---|---
Boolean with input size $n$ | Naive | ${\mathcal{O}}(n)$ | ${\mathcal{O}}(n^{2})$ | ${\mathcal{O}}(n^{2})$ | -
GSDM | ${\mathcal{O}}(n)$ | ${\mathcal{O}}(n)$ | ${\mathcal{O}}(n)$ | ${\mathcal{O}}(n)$
Sorting with input size $n$ | Naive | ${\mathcal{O}}(n^{2})$ | ${\mathcal{O}}(n^{4})$ | ${\mathcal{O}}(n^{4})$ | -
GSDM | ${\mathcal{O}}(n^{2})$ | ${\mathcal{O}}(n^{3})$ | ${\mathcal{O}}(n^{3})$ | ${\mathcal{O}}(n)$
BCMF with $k=m=n$ | Naive | ${\mathcal{O}}(n^{2})$ | ${\mathcal{O}}(n^{4})$ | ${\mathcal{O}}(n^{4})$ | -
GSDM | ${\mathcal{O}}(n^{3})$ | ${\mathcal{O}}(n^{4})$ | ${\mathcal{O}}(n^{4})$ | ${\mathcal{O}}(1)$
Table 3: Comparison of computational complexities of a GSDM layer and a naive
DM layer without structured attention or intermediate variables. We do not
include Sudoku since the problem has fixed dimension. GSDM yields reductions
in complexity that scale with $n$ for the Boolean and sorting experiments,
while giving the same complexity as a naive approach for BCMF yet much better
performance.

##  Appendix F Ablation on BMF embedding type

Figure 14 shows the effect of embedding type on BCMF performance. As in Fig.
7(a), we vary each of $m$, $n$, and $k$ in turn and set $m=16$, $k=8$ while
varying $n$; set $n=16$, $k=8$ while varying $n$; and set $m=n=16$ while
varying $k$. The scale for the y-axis is smaller than in Fig. 7(a) since the
embedding type makes a smaller difference to performance than the use of
sparsity and intermediate variables. This makes the noise in the results more
visible, but it is noticeable that exchangeable embeddings (solid line) mostly
provide the best performance. The array embeddings (dashed) are worse than
independent embeddings (dotted) for higher dimensionality. This may be
because, with sufficient training time, the independent embeddings can learn
to approximately match the exchangeable embeddings. When we look at error
earlier in training, array embeddings perform slightly better than independent
embeddings.

Figure 14: Final RMSE on BCMF as a function of the problem dimension. The
solid line uses exchangeable embeddings; the dashed line uses array
embeddings; the dotted line uses independent embeddings.

##  Appendix G Computational complexities

Table 3 compares the computational cost of GSDM with that of naively applying
a neural network without intermediate variables or structured attention.

##  Appendix H Expanded ablation on attention mask specification

Figure 15 is an expanded version of our ablation on the sorting attention
mask. In addition to the lines in Fig. 9 we show the training performance of a
non-symmetrized mask (dashed red). For sorting, edges added during
symmetrization are necessary to allow any information to flow from the
intermediate variables ${\bm{C}}$ to the permutation matrix ${\bm{P}}$. This
blocks the path between the input ${\mathbf{u}}$ and output of interest
${\bm{P}}$, and so the sampled ${\bm{P}}$ does no better than random chance at
any point in training.

Figure 15: Performance throughout training of sorting with different attention
masks corresponding to different graphical models. The solid line uses EE and
the dashed line uses AE.

##  Appendix I Permutation equivariant GSDM

The stochastic process of the DM is composed of a drift term determined by
$\hat{{\mathbf{x}}}_{\theta}$ and a fixed diffusion term (noise). The
diffusion term employs a diagonal covariance structure in the DM and hence can
be varied in dimension and does not induce dependencies between dimensions.
This leaves the neural network of $\hat{{\mathbf{x}}}_{\theta}$ to reflect the
permutation equivariances. First we observe in Figure 2 that all neural
networks $m$ are applied independently to each dimension (they are contained
in the light grey boxes), leaving only the attention mechanism itself to
relate different dimensions. Attention can only distinguish dimensions through
added positional embeddings [Vaswani et al., 2017]. Consequently our
exchangeable embeddings setting shares the same embedding across all
realizations of an index $i$ if the model is expected to be invariant to
permutations of $i$. The attention mechanism can therefore not distinguish
between variables with different values of $i$ and so the messages passed are
not affected by permutations of $i$. This means that the network as a whole is
equivariant to permutations of $i$ and so the modeled distribution is
invariant to permutations of $i$ [Hoogeboom et al., 2022].

##  Appendix J Matrix inversion

Figure 16: Rows of matrix inversion examples. Similar to Fig. 6, but here we
condition both on ${\bm{A}}$ and ${\bm{E}}=\mathbf{1}$ (blue). Each of the 5
pairs of rows show a solution for the same ${\bm{A}}$. Reconstructions are
shown as $\hat{{\bm{E}}}={\bm{A}}{\bm{R}}$ (green).

In this experiment we explore a purely continuous variation of our BCMF
example from Section 4. We train the model on fixed size full rank matrices of
dimension $5$ and condition on both ${\bm{E}}$ and ${\bm{A}}$ during training
and testing. All entries of both ${\bm{A}}\in{\mathbb{R}}^{5\times 5}$ and
${\bm{R}}\in{\mathbb{R}}^{5\times 5}$ are now sampled from a
$\text{Normal}(0,1)$ prior and we set ${\bm{E}}={\bm{A}}{\bm{R}}$ (as in
BCMF). Despite training on randomly sampled ${\bm{A}}$ and ${\bm{R}}$, we
demonstrate that GSDM implicitly learns matrix inversion. At test time we set
${\bm{E}}$ to the identity matrix and solve for
${\bm{R}}\approx{\bm{A}}^{-1}$. Example solutions can be seen in Fig. 16. Each
pair of rows contains two approximate solutions for the same ${\bm{A}}$ to
illustrate sample diversity. Most reconstructions for $\hat{{\bm{E}}}$ are
close to the identity matrix, but GSDM is not perfect. We did not specialize
our prior from BCMF; a more targeted prior could be constructed by directly
providing pairs of matrices and their inverse. This experiment shows that we
are able to calculate approximate inverses, even though we have not
specialized our graphical model or training distribution to do so.

⬇

(defn rand-matrix [size name]

(foreach (first size) [i (range (first size))]

(foreach (second size) [j (range (second size))]

(sample name (normal 0 1)))))

(defn dot-helper [t state a b]

(+ state

(sample "C" (dirac (* (get a t)

(get b t))))))

(defn dot [a b]

(loop (count a) 0 dot-helper a b))

(defn row-mul [t state m v]

(conj state (sample "E" (dirac (dot (get m t) v)))))

(defn transpose [m]

(foreach (count (first m)) [j (range (count (first m)))]

(foreach (count m) [i (range (count m))]

(get (get m i) j))))

(defn matmatmul [m1 m2]

(let [m2_ (transpose m2)]

(foreach (count m1) [i (range (count m1))]

(foreach (count m2_) [j (range (count m2_))]

(sample

"E"

(dirac (dot (get m1 i) (get m2_ j))))))))

(let [A (rand-matrix [3 2] "A")

R (rand-matrix [2 3] "R")

E (matmatmul A R)]

E)

Figure 17: Source code of a full generative model for the BCMF experiment.
Passing this into our compiler yields the attention mask in Fig. 10. Note that
intermediate variables for ${\bm{C}}$ are explicitly created by sampling from
a dirac distribution.


# Time-energy uncertainty does not create particles

B W Roberts1 and J Butterfield2 1 Philosophy, Logic & Scientific Method,
Centre for Philosophy of Natural and Social Sciences, London School of
Economics & Political Science, London, WC2A 2AE, UK  2 Trinity College,
University of Cambridge, Cambridge, CB2 1TQ, UK<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this contribution in honour of Paul Busch, we criticise the claims of many
expositions that the time-energy uncertainty principle allows both a violation
of energy conservation, and particle creation, provided that this happens for
a sufficiently short time. But we agree that there are grains of truth in
these claims: which we make precise and justify using perturbation theory.

. Forthcoming in _Journal of Physics: Conference Proceedings_ , Mathematical
Foundations of Quantum Mechanics in Memoriam Paul Busch

##  1 Introduction

In expositions of quantum theory, it is often said that energy conservation
can be violated, and that particles can ‘pop in to existence’ out of nowhere,
thanks to a time-energy uncertainty principle. Time-energy uncertainty was, of
course, one of Paul Busch’s areas of expertise. His insightful analyses of it
began already in his two 1990 works [4, 5] and the topic remained an abiding
interest of his, shown for example in his 2008 review article about time in
quantum physics [6]. It seems to us very likely that Busch, with his clarity
and precision of thought, would have had misgivings about this “folklore”.
Accordingly, we propose to commemorate his life and work by criticising it—in
a way that we hope is worthy of his memory. But we will also argue that the
folklore contains grains of truth: which we will make precise and justify,
using perturbation theory.

We begin with some illustrative quotations. Thus Jones proposes that,

> “a consequence of the Heisenberg Uncertainty Principle is that we can take
> seriously the possibility of the existence of energy non-conserving
> processes—provided the amount by which energy is not conserved,
> $E_{violation}$, exists for a time less than $t=\hbar/2E_{violation}$” [12,
> p.226]

This folklore is not just a myth of pedagogy or popular exposition. Many
excellent textbooks111As Fermat might say: we have discovered a marvellous
number of comments of this kind, which this footnote is too small to contain.
Here are a couple from books about quantum field theory; though one of our
main points will be that the issues are not specific to quantum field theory,
but arise already in quantum mechanics. The first book is about quantum field
theory’s philosophical interpretation, the second about its mathematics.
Teller [19, p.148] remarks that violation of local energy conservation is
“customarily excused” by the time-energy uncertainty principle; while Folland
[8, p.133] writes that, “the uncertainty principle allows the particle and/or
quantum to be temporarily ‘off mass-shell’ between the times of emission and
absorption or vice versa”. make similar comments; such as the classic quantum
field theory textbook of Peskin and Schroeder:

> “Even when there is not enough energy for pair creation, multiparticle
> states appear, for example, as intermediate states in second-order
> perturbation theory. We can think of such states as existing only for a very
> short time, according to the uncertainty principle $\Delta E\cdot\Delta
> t=\hbar$. As we go to higher orders in perturbation theory, arbitrarily many
> such ‘virtual’ particles can be created.” [18, p.13]

Similarly, in their textbook on general relativity, Hobson et al. [11] say
that time-energy uncertainty is responsible not just for virtual particles,
but for concrete physical predictions like Hawking radiation222There is a
sense in which Hawking radiation [10], when viewed as a comparison between a
quantum field theory constructed at past null infinity and one constructed at
future null infinity, is indeed associated with particle creation. However,
this is a matter of inequivalent vacua, and so spontaneous symmetry breaking,
not of time-energy uncertainty.:

> “Hawking’s original calculation uses the techniques of quantum field theory,
> but we can derive the main results very simply from elementary arguments. …
> Pair creation violates the conservation of energy and so is classically
> forbidden. In quantum mechanics, however, one form of Heisenberg’s
> uncertainty principle is $\Delta t\Delta E=\hbar$, where $\Delta E$ is the
> minimum uncertainty in the energy of a particle that resides in a quantum
> mechanical state for a time $\Delta t$. Thus, provided the pair annihilates
> in a time less than $\Delta t=\hbar/\Delta E$, where $\Delta E$ is the
> amount of energy violation, no physical law has been broken.” [11, §11.11]

Agreed: not everyone endorses this use of time-energy uncertainty to justify
particle creation. In particular, Griffiths is unimpressed:

> “It is often said that the uncertainty principle means that energy is not
> strictly conserved in quantum mechanics-that you’re allowed to ‘borrow’
> energy $\Delta E$, as long as you ‘pay it back’ in a time $\Delta
> t\sim\hbar/2\Delta E$; the greater the violation, the briefer the period
> over which it can occur. There are many legitimate readings of the energy-
> time uncertainty principle, but this is not one of them. Nowhere does
> quantum mechanics license violation of energy conservation”. [9, p.115]

We agree with Griffiths.333Another dissenter is Bunge [3], who gives a short
but scathing criticism of understanding virtual particles in terms of time-
energy uncertainty. Of course, mass-energy is exactly conserved in an isolated
physical system, in quantum physics no less than classical physics. In quantum
theory, the unitary propagator $U_{t}$ (a strongly continuous unitary
representation of the reals under addition) can be written $U_{t}=e^{-itH}$,
where the self-adjoint generator $H$ is the energy. And, for any initial state
$\rho$ that evolves unitarily according to $\rho_{t}=U_{t}\rho U_{t}^{*}$, the
energy expectation value does not change over time, since $H$ and $U_{t}$
commute: $\Tr(\rho_{t}H)=\Tr(\rho U_{t}^{*}HU_{t})=\Tr(\rho H)$ for all
$t\in\mathbb{R}$.

Nevertheless, what the folklore says about time, energy, and energy
conservation contains some grains of truth. We will focus on three ideas:

  1. 1.

(_non-conservation_) There is some sense in which ‘energy’ associated with a
perturbed system is not conserved;

  2. 2.

(_particle creation_) There is some sense in which that non-conservation
allows the non-conservation of particle-number; and

  3. 3.

(_shorter times_) There is some sense in which more particle creation occurs
during shorter times.

So our aim is to do the exercise of making these statements precise, and
verifying them. Our lesson will be that, in each case, it is not a time-energy
uncertainty relation that provides the wiggle-room to create particles: hence
our slogan, “time-energy uncertainty does not create particles.” The particles
are rather best viewed as artefacts of the shifted perspective one adopts when
approximating a physical system using perturbation theory. We will discuss the
statements (i), (ii) and (iii) in Sections 3, 4 and 5, respectively. But we
precede this with an overview, Section 2, about perturbation theory, and the
way it justifies the idea of a virtual state.

##  2 The perturbation view of virtual states

For our purposes, a quantum system is a triple
$(\mathcal{H},\mathcal{A},t\mapsto U_{t})$, where $\mathcal{H}$ is a separable
complex Hilbert space, $\mathcal{A}$ is a von Neumann algebra of linear
operators on $\mathcal{H}$, and $t\mapsto U_{t}$ is a strongly continuous one-
parameter unitary representation in $\mathcal{A}$ of the group $\mathbb{R}$
under addition. The Hilbert space represents a collection of states; the
algebra contains a collection of operators that represent observables; and the
unitary representation provides the dynamics. By Stone’s theorem, there exists
a unique self-adjoint operator $H\in\mathcal{A}$ (the ‘energy’ operator or
‘Hamiltonian’) such that the dynamics can be written in the form,
$U_{t}=e^{-itH}$, for all $t\in\mathbb{R}$.

Perturbation theory uses a quantum system that is in some way tractable to
approximate a quantum system that is not. For example: the energy $H$ of a
Helium atom, which contains two mutually repulsive electrons, can be
approximated by a system whose energy $H_{0}$ ignores the mutual repulsion of
the electrons. In such examples, one begins with a quantum system
$(\mathcal{H},\mathcal{A},t\mapsto U_{t})$ and a set of operators
$\\{A_{\lambda}\\}\subset\mathcal{A}$ parametrised by a real number $\lambda$,
one value of which gives the correct, or physically real, operator of
interest:

$A_{\lambda}=A_{0}+V_{\lambda}.$ (1)

This set is constructed in such a way that as $\lambda\rightarrow 0$, we get
$A_{\lambda}\rightarrow A_{0}$ in the operator norm. $A_{0}$ is called the
‘unperturbed’ operator, and the set $A_{\lambda}$ is called a ‘perturbation’.
The hope is both that a physical system can be correctly described by
$A_{\lambda}$ for some value of $\lambda$, and also that its properties can be
accurately approximated using known facts about the more tractable operator
$A_{0}$.

Perturbation theory allows one to approximate various aspects of the operator
$A_{\lambda}$ when it can be represented in a power series expansion around
$\lambda=0$. That is, one seeks an exact expression of $A_{\lambda}$ of the
form,

$A_{\lambda}=A_{0}+\lambda\left(\frac{d}{d\lambda}V_{\lambda}\right)\Big{|}_{\lambda=0}+\frac{\lambda^{2}}{2!}\left(\frac{d^{2}}{d\lambda^{2}}V_{\lambda}\right)\Big{|}_{\lambda=0}+\cdots$
(2)

The $n$th-order approximation of $A_{\lambda}$ is by definition the sum of the
first $n$ terms in this series. As $n\rightarrow\infty$, the series approaches
$A_{\lambda}$ in the operator norm. A wide class of problems can be solved by
adopting the simple approximation where only the first two terms are
calculated. Defining $V:=\tfrac{d}{d\lambda}V_{\lambda}\Big{|}_{\lambda=0}$
this gives what is called a ‘linear’ perturbation:

$A_{\lambda}\approx A_{0}+\lambda V.$ (3)

The eigenvalue problem for an operator expressed as a linear perturbation can
typically be given an approximate analysis thanks to classic results in
perturbation theory.444For example, if it is the case that for all $\lambda$,
$A_{\lambda}=A_{0}+\lambda V$ has a discrete spectrum and commutes with its
adjoint ($A_{\lambda}A_{\lambda}^{*}=A_{\lambda}^{*}A_{\lambda}$), then by the
Mitzkin-Taussky theorem, the eigenvalues of $a^{i}_{\lambda}$ of $A_{\lambda}$
are linear in $\lambda$ (in that $a^{i}_{\lambda}=a^{i}_{0}+\lambda k^{i}$),
and its eigenvectors are analytic functions of $\lambda$ [13, §2.5]. It is
then possible to expand these eigenvectors around $\lambda=0$ to give an
approximation in terms of (usually already-known) eigenvectors of $A_{0}$.

A typical way for virtual states to arise in perturbation theory is in its
application to the dynamics. Let $(\mathcal{H},\mathcal{A},t\mapsto U_{t})$ be
a quantum system, and consider a second one-parameter unitary representation
$t\mapsto U^{0}_{t}$. We write $H$ and $H_{0}$ for their respective
Hamiltonian generators, and refer to the former as the ‘perturbed’ (or
‘interacting’) Hamiltonian, while the the latter is the ‘unperturbed’
Hamiltonian. We define $V:=H-H_{0}$ and refer to it as the ‘potential’.
Writing $U_{t}=U^{0}_{t}(U^{0}_{-t}U_{t})$, we expand the term in parentheses
as a power series around $t=0$,

$U_{t}=U^{0}_{t}\left(I+t\frac{d}{dt}(U^{0}_{-t}U_{t})\Big{|}_{t=0}+\frac{t^{2}}{2!}\frac{d^{2}}{dt^{2}}(U^{0}_{-t}U_{t})\Big{|}_{t=0}+\cdots\right).$
(4)

To the extent that $t$ is close to zero and $V=H-H_{0}$ is small (in the
operator norm), the operator $U_{t}$ is approximated by summing the first $N$
terms in this series and ignoring the rest [13, §II.3]. Note however that this
partial sum of the first $N$ terms is in general not unitary.

Writing $U^{(n)}_{t}$ to denote the $n$th term in the series, the first few
orders of approximation can be calculated by applying the Leibniz rule to the
derivatives:

$\displaystyle\begin{split}U^{(0)}_{t}&=U^{0}_{t}\\\
U^{(1)}_{t}&=-itU^{0}_{t}V\\\
U^{(2)}_{t}&=\tfrac{t^{2}}{2!}U^{0}_{t}\left([V,H_{0}]-V^{2}\right)\end{split}$
(5)

The virtual states picture arises from imagining that each contribution to the
series is the amplitude of a “scattering event” in its own right. For example,
suppose $\psi_{a}$ and $\psi_{b}$ are orthogonal eigenvectors of the
unperturbed Hamiltonian $H_{0}$, and that we wish to approximate the amplitude
$\langle\psi_{b},U_{t}\psi_{a}\rangle$ associated with a transition during
time $t$ from $\psi_{a}$ to $\psi_{b}$. In a first-order approximation, we
replace $U_{t}$ with the sum of the terms $U^{(0)}_{t}+U^{(1)}_{t}$. In a more
accurate second-order approximation, we replace it with
$U^{(0)}_{t}+U^{(1)}_{t}+U^{(2)}_{t}$, and so on. With a little
calculation555Zeroth order:
$\langle\psi_{b},U^{(0)}_{t}\psi_{a}\rangle=e^{iat}\langle\psi_{b},\psi_{a}\rangle=0$.
First-order:
$\langle\psi_{b},U^{(1)}_{t}\psi_{a}\rangle=-it\langle\psi_{b},U^{0}_{t}V\psi_{a}\rangle=-ite^{ibt}\langle\psi_{b},V\psi_{a}\rangle$.
Second-order:
$\langle\psi_{b},U^{(2)}\psi_{b}\rangle=\langle\psi_{b},U^{0}_{t}[V,H_{0}]\psi_{a}\rangle-\langle\psi_{b},U_{t}^{0}V^{2}\psi_{a}\rangle=e^{ibt}(a-b)\langle\psi_{b},V\psi_{a}\rangle+e^{ibt}\langle\psi_{b},V^{2}\psi_{a}\rangle$.,
the terms in these approximations are found to be,

$\displaystyle\begin{split}\langle\psi_{b},U^{(0)}_{t}\psi_{a}\rangle&=0\\\
\langle\psi_{b},U^{(1)}_{t}\psi_{a}\rangle&=-ite^{ibt}\langle\psi_{b},V\psi_{a}\rangle\\\
\langle\psi_{b},U^{(2)}_{t}\psi_{b}\rangle&=e^{ibt}(a-b)\langle\psi_{b},V\psi_{a}\rangle-e^{ibt}\langle\psi_{b},V^{2}\psi_{a}\rangle\end{split}$
(6)

where $a$ and $b$ are the $H_{0}$ eigenvalues associated with $\psi_{a}$ and
$\psi_{b}$, respectively. The zeroth-order contribution
$\langle\psi_{b},U^{(0)}\psi_{a}\rangle$, viewed as a transition amplitude in
its own right, describes an initial state $\psi_{a}$ that never transitions to
$\psi_{b}$. The first-order contribution might lead us to say that the
presence of the potential $V$ ‘deflects’ the initial state $\psi_{a}$ to
$\psi_{b}$ with some probability. The second-order contribution has two terms,
the first of which will just get collected together with the first-order one
in the series, and the second of which is a ‘deflection’ by the potential
$V^{2}$. Of course, we have not given any reason to view this language as
anything more than short-hand; strictly speaking, each is simply a
contribution to a series that approximates
$\langle\psi_{b},U_{t}\psi_{a}\rangle$.

Virtual states arise as ‘intermediate states’ in this kind of analysis. In the
example just given of approximating the transition amplitude
$\langle\psi_{b},U_{t}\psi_{a}\rangle$, they begin to appear at the level of
the second-order contribution $U^{(2)}_{t}$. Instead of thinking of the
second-order term $e^{ibt}\langle\psi_{b},V^{2}\psi_{a}\rangle$ as a
deflection in the potential $V^{2}$, let us rewrite it in the form,

$e^{ibt}\langle\psi_{b},V^{2}\psi_{a}\rangle=\langle\psi_{b},Ve^{ib(t-t^{\prime})}\psi^{\prime}\rangle\langle\psi^{\prime},Ve^{ibt^{\prime}}\psi_{a}\rangle$
(7)

where we define $\psi^{\prime}:=\tfrac{1}{|V\psi_{a}|}V\psi_{a}$, and choose
any $t^{\prime}$ such that $0<t^{\prime}<t$. Now, instead of viewing the
transition as going from $\psi_{a}$ to $\psi_{b}$ in the potential $V^{2}$
during a time $t$, we can view it as consisting of an intermediate transition
from $\psi_{a}$ to $\psi^{\prime}$ in $V$ during time $t^{\prime}$, followed
by a transition from $\psi^{\prime}$ to $\psi_{b}$ in $V$ during the later
time-interval $t-t^{\prime}$. The intermediate state $\psi^{\prime}$ is an
example of a virtual state. As expected, the third-order transitions have a
$V^{3}$ term that gives rise to a pair of virtual states, and so on up the
series.

One can draw a Feynman diagram for each contribution
$\langle\psi_{b},U^{(n)}_{t}\psi_{a}\rangle$ in this series, illustrated for
$U^{(0)}$, $U^{(1)}$, and $U^{(2)}$ in Figure 1. Virtual states appear,
beginning in the second-order diagrams, as states without open endpoints, such
as $\psi^{\prime}$ in the right-most diagram of the Figure. This encodes the
fact that they are not associated with the measured in-state or out-state in
the scattering experiment associated with this amplitude. However, again: we
have given no reason to view each diagram as anything other than shorthand for
a term $\langle\psi_{b},U^{(n)}\psi_{a}\rangle$ in a series approximation of
the amplitude
$\langle\psi_{a},U_{t}\psi_{b}\rangle\approx\langle\psi_{a},U^{(0)}_{t}\psi_{b}\rangle+\langle\psi_{a},U^{(1)}_{t}\psi_{b}\rangle+\langle\psi_{a},U^{(2)}_{t}\psi_{b}\rangle+\cdots$.

$\psi_{a}$

$V$$\psi_{a}$$\psi_{b}$

$V$$V$$\psi_{b}$$\psi_{a}$$\psi^{\prime}$

Figure 1:

Feynman diagrams for the first three terms in a perturbation series for
$\langle\psi_{b},U_{t}\psi_{a}\rangle$, with $U_{t}=e^{-it(H_{0}+V)}$ and
$\psi_{a},\psi_{b}$ eigenvectors of $H_{0}$. The second-order state
$\psi^{\prime}$ is ‘virtual’.

##  3 The appearance of energy non-conservation

To sum up: the perturbation view is one of shifting perspectives. We describe
a quantum system $(\mathcal{H},\mathcal{A},t\mapsto U_{t})$ from the
perspective of the $n$th-order approximation in a perturbation series,
recognising that on this perspective, the system will sometimes appear to
deviate from its true ‘perturbed’ dynamics, as well as from the idealised
‘unperturbed’ dynamics.

As it happens, one such deviation is that energy conservation can appear to
fail. Thus we have our first claim:

  1. 1.

(_non-conservation_) There is some sense in which ‘energy’ associated with a
perturbed system is not conserved.

In the context of the virtual states described in the previous section, the
‘energy’ that fails to be conserved is associated with the idealised
Hamiltonian $H_{0}$ of the unperturbed dynamics. In the zeroth-order
approximation $U^{(0)}$, it is conserved. However, in the first-order and
second-order approximations, it is not, in that there are eigenstates of
$H_{0}$ that are not stationary. This is due to the fact that for interacting
systems with $[H_{0},V]\neq 0$, the unperturbed Hamiltonian is not stationary,
$U_{t}H_{0}U_{t}^{*}\neq 0$, or equivalently, $[H,H_{0}]\neq 0$. So this is
one thing that could be meant by saying ‘energy’ is not conserved in the
presence of virtual states.

However, in a quantum system $(\mathcal{H},\mathcal{A},t\mapsto U_{t})$, it is
the generator $H$ of the true i.e. perturbed dynamics $U_{t}$ that represents
the ‘true energy’ of the system, not the idealised Hamiltonian $H_{0}$. So, a
more physically interesting question is whether $H$ commutes with the
approximate dynamics given by a partial sum, up to say the $N$th term, of the
perturbation series, eq. 4 and 5.

Of course, it may happen that for some finite $N$, we find that
$\sum^{N}_{n}U^{(n)}=U_{t}$, so that $\sum^{N}_{n}U^{(n)}$ is an exact
description rather than an approximate one, and the energy $H$ is indeed
conserved. But in general, the approximate dynamics $\sum^{N}_{n}U^{(n)}$ is
not equal to $U_{t}$, indeed is not even unitary; and $H$ will not be
conserved under it.

On the other hand, there is a sense in which energy $H$ for the perturbed
dynamics $U_{t}$ comes closer to being conserved by the approximate dynamics,
the higher the order of approximation. For as we add more terms, the resulting
approximate dynamics $\sum_{n}U^{(n)}_{t}$ better approximates the true
dynamics $U_{t}$; that is, $\sum_{n=0}^{N}U^{(n)}_{t}\rightarrow U_{t}$ in the
operator norm as $N$ becomes arbitrarily large. But this implies:666In
general, $\|A_{n}-B\|\rightarrow 0$ implies the commutator
$\|[A_{n},B]\|\rightarrow 0$, since
$\|[A_{n},B]\|=\|(A_{n}-B)B+B(B-A_{n})\|\leq\|A_{n}-B\|\|B\|+\|B\|\|B-A_{n}\|=2\|B\|\|A_{n}-B\|$.

$\left[\textstyle\sum_{n=0}^{N}U^{(n)}_{t},H\right]\rightarrow 0\text{ as
}N\rightarrow+\infty,$ (8)

giving perfect conservation of energy in the limit. This is ironic, in that
Peskin and Schroeder write: “As we go to higher orders in perturbation theory,
arbitrarily many such ‘virtual’ particles can be created”, suggesting that
energy conservation gets worse with higher order terms [18, p.13]. Agreed:
there is ‘more room’ for virtual states in higher-order terms. But this does
not mean that energy conservation gets worse. In general, it gets better as
the ‘true’ perturbed energy becomes more distant (in the operator norm) from
the idealised, unperturbed description of the system.

##  4 Particle creation

We now turn to the statement of (ii), the particle-number claim. For this we
need to add some notion of particle number to our description. This will
consist in a representation of annihilation ($a_{i}$) and creation
($a_{i}^{*}$) operators on $\mathcal{H}$ for $i\in\mathbb{Z}^{+}$, which
satisfy $[a_{i},a_{j}^{*}]=\delta_{ij}$ and
$[a_{i},a_{j}]=[a_{i}^{*},a_{j}^{*}]=0$. Let $N=\sum_{i}a_{i}^{*}a_{i}$ be the
‘particle number’ operator. Taking $U^{0}_{t}$ as the unperturbed dynamics
associated with no interactions, we assume for simplicity that
$[N,U_{t}^{0}]=0$, and hence that the unperturbed system is one in which this
(unperturbed) particle-number is conserved. However, if $[N,U_{t}]\neq 0$,
then particle number will in general _not_ be conserved by the ‘true’
dynamics; and in general, it will not be conserved under the dynamics given by
any of the partial-sum approximations $\sum_{n}U^{(n)}_{t}$. (Agreed, $N$
might be conserved by $U_{t}$ and-or by an approximate dynamics. But this will
not hold true in general.)

That is, we have:

  1. 2.

(_particle-creation_) The dynamics generated by the partial-sum approximation
$\sum_{n}U^{(n)}_{t}$ does not in general conserve the unperturbed particle
number $N$.

##  5 Shorter times

We now turn to our final claim:

  1. 3.

(_shorter times_) There is some sense in which more particle creation occurs
during shorter times.

Here we enter the realm of the time-energy uncertainty principle—or, rather,
principles—that are invoked by the cavalier textbook tradition with which we
began. These principles are surveyed by Busch [4, 5, 6]. For us, there are two
main points to make, corresponding to two broad understandings of time-energy
uncertainty. The first point is not connected to perturbation theory: it is
really a warning against an untenable understanding of time-energy
uncertainty. The second point will be more positive, in that it will vindicate
the shorter-time claim (iii).

The first point concerns what Busch [6] suggests one should call ‘external
time’ (or in [4]: ‘pragmatic time’): namely, time as measured by clocks that
are not coupled to the objects studied in the experiment. So in this role,
time specifies a parameter or parameters of the experiment: e.g. an instant or
duration of preparation or of measurement, or the time-interval between
preparation and measurement. In this role, there seems to be no scope for
uncertainty about time. And indeed, our first point here is a
warning—following Busch [4]. For as Busch discusses, there is a tradition
(deriving from the founding fathers of quantum theory) of an uncertainty
principle between:

  1. (1)

the duration of an energy measurement; and

  2. (2)

either the range of an uncontrollable change of the measured system’s energy,
or the resolution of the energy measurement, or the statistical spread of the
system’s energy.

To give a little more detail: Busch [4, §1-2] describes how various
authorities (including Landau and Peierls [14] and Landau and Lifshitz [15,
§44]) endorse at least one of the following claims:

  1. ($P$)

An energy measurement of duration $\Delta t$ leads to an uncontrollable and
unpredictable change of the (previously sharply defined) energy by an amount
of the order $\Delta E$ such that $\Delta E.\Delta t\geq\hbar$; so that there
is no short-time reproducible (first kind) energy measurement.

  2. ($P^{\prime}$)

An energy measurement of duration $\Delta t$ must carry an inaccuracy $\Delta
E$ such that the uncertainty relation $\Delta E.\Delta t\geq\hbar$ is
satisfied.

Busch argues, and we agree, that Aharonov and Bohm [1] refute this tradition;
(see [4], especially §4, and [6, §3.1]). They give a simple model of an
arbitrarily accurate and arbitrarily rapid energy measurement, where in short:
two particles are confined to a line and are both free, except for an
impulsive measurement of the momentum and so energy of the first by the
second, with the momentum of the second being the pointer-quantity.777Note
that Busch argues that a proper analysis and vindication of Aharonov and
Bohm’s refutation uses positive operator-valued measures (POVMs) to describe
measurement outcomes, a notion of physical quantity that generalises
projection-valued measures (PVMs); this follows the tradition of Ludwig [16,
17], and is developed at book-length by Busch et al. [7]. This leaves little
room for ‘energy uncertainty’ to develop during brief (in external time)
energy measurements, either in terms of uncontrollable changes in energy, or
in terms of measurement inaccuracy.

Our second, more positive, point concerns what Busch [6] suggests one should
call ‘intrinsic time’ (or in his [4]: ‘dynamical time’): namely, a dynamical
variable of the target system itself whose function is to measure the time,
such as the position of a clock’s dial relative to its face. Busch suggests
that in principle, every non-stationary quantity $A\in\mathcal{A}$ and density
operator state $\rho$ defines a characteristic time interval,
$\tau_{\rho}(A)$, in which the expectation value changes ‘significantly’. For
example: in the Schrödinger representation on the space of $L^{2}(\mathbb{R})$
functions, if $A\psi(x):=Q\psi(x)=x\psi(x)$ for all $\psi(x)$ in the domain of
$Q$ and if $\rho=E_{\psi}$ is the projection associated with a wave packet
$\psi(x)$, then $\tau_{\rho}(A)$ could be defined as the time interval
required for the bulk of the wave packet to shift by its width—in some sense
of ‘width’.

Various definitions of such a time interval are available. We will choose what
is sometimes called the ‘characteristic time’ associated with the dispersion
of an operator-state pair. This obeys what is probably the best-known time-
energy uncertainty principle for intrinsic times: the Mandelstam-Tamm
uncertainty principle.

One arrives at it for a quantum system $(\mathcal{H},\mathcal{A},t\mapsto
U_{t})$ by combining three ideas: (a) the Heisenberg equation of motion for an
operator $A\in\mathcal{A}$ with $A(t):=U_{t}AU^{*}_{t}$,

$i\hbar\tfrac{d}{dt}A(t)=[H,A(t)];$ (9)

(b) the Heisenberg-Robertson uncertainty principle888Cf. [2, Theorem 8.1.2],
that for any quantities $A,B\in\mathcal{A}$, and density operator (quantum
state) $\rho$,

$\Delta_{\rho}A\Delta_{\rho}B\geq\frac{1}{2}|\Tr(i[A,B]\rho)|\;\;;$ (10)

and (c) the definition of a characteristic time for an operator $A$ that does
not commute with the unitary dynamics $t\mapsto U_{t}$, and for a time-
independent state $\rho$ that is not an eigenstate of $A$:

$\tau_{\rho}(A):=\frac{\Delta_{\rho}A}{|\tfrac{d}{dt}\Tr(A(t)\rho)|},$ (11)

i.e. the time it takes for the expectation value of $A$ to change by its
standard deviation. From these definitions it immediately follows that,

$\tau_{\rho}(A)\Delta_{\rho}(H)\geq\frac{1}{2}\hbar,$ (12)

whenever $[A,H]\neq 0$ and $\rho$ is not an eigenstate of $H$.

This principle can be applied in a perturbation theory analysis of a quantum
system $(\mathcal{H},\mathcal{A},t\mapsto U_{t})$ with Hamiltonian generator
$H$ and an unperturbed Hamiltonian $H_{0}$, in two ways, so as to give two
construals of the shorter times claims (iii). The first way puts $H_{0}$ for
$A$ in eq. 12, while the second way puts a number operator $N$ for $A$.

So first set $A:=H_{0}$ in eq. 12, to get:
$\tau_{\rho}(H_{0})\Delta_{\rho}(H)\geq\tfrac{1}{2}\hbar$. Suppose that
$\Delta_{\rho}H_{0}$ is very small, corresponding to a state $\rho$ that is
‘peaked’ in unperturbed energy, so that the characteristic time
$\tau_{\rho}(H_{0})$ is comparatively small. The Mandelstam-Tamm uncertainty
principle then implies that $\Delta_{\rho}H$ is comparatively large, and hence
that the spread of the system’s true (unperturbed) energy is large. In this
sense, a short characteristic time and a peaked distribution of the
unperturbed energy is associated with a large uncertainty of the system’s true
energy. Thus we have one general way to construe the shorter-times claim (iii)
above. Agreed, this is a construal that uses the unperturbed Hamiltonian
$H_{0}$, not an (unperturbed) number operator $N$.

And finally: a related construal of claim (iii) can be given, about a particle
number operator $N$ associated with the unperturbed dynamics i.e. that
satisfies $[N,H_{0}]=0$; so that under unperturbed dynamics, this particle
number is conserved. Such an operator will typically not be conserved by the
true dynamics, in that $[H,N]\neq 0$. Thus let us suppose now that $\rho$ is a
state for which the true i.e. perturbed energy $H$ is peaked, in that
$\Delta_{\rho}H$ is small, and hence (eq. 12) that the characteristic time
(under the true i.e. perturbed dynamics) $\tau_{\rho}(N)$ is large. Then, the
larger $|\tfrac{d}{dt}\Tr(N(t)\rho)|$ is, corresponding to a fast rate of
change of the expectation value of $N$ in the true dynamics, the larger the
spread $\Delta_{p}N$ must be, in order to guarantee that
$\tau_{\rho}(N):=\Delta_{\rho}N/|\tfrac{d}{dt}\Tr(N(t)\rho)|$ (cf. eq. 11) is
sufficiently large. So this construal of claim (iii) amounts to: ‘If the
perturbed energy $H$ is peaked, and the expectation value of $N$ changes fast
(“short times”), then $N$ has large spread (“non-negligible amplitudes for
values far from the expectation value”)’.

To conclude: we hope to have shown that with a little Buschian wisdom, one can
recover some grains of truth from some cavalier statements in the textbook
tradition. May Paul’s legacy continue to inspire our community to emulate his
craftsmanship and creativity.

We thank Klaas Landsman, Jos Uffink and Reinhard Werner for advice and
encouragement at an early stage; two anonymous referees for helpful comments
and corrections; and the editors, not least for their patience. Bryan W.
Roberts was supported by the Leverhulme Trust’s Philip Leverhulme Prize and as
a Visiting Fellow Commoner at Trinity College, Cambridge.

## References

  * Aharonov and Bohm [1961] Y. Aharonov and D. Bohm.  Time in the quantum theory and the uncertainty relation for time and energy.  _Physical Review_ , 122(5):1649, 1961.
  * Blank et al. [2008] Jiří Blank, Pavel Exner, and Miloslav Havlíček.  _Hilbert Space Operators in Quantum Physics_.  Springer Science and Business Media B.V., 2nd edition, 2008.
  * Bunge [1970] Mario Bunge.  Virtual processes and virtual particles: real or fictitious?  _International Journal of Theoretical Physics_ , 3(6):507–508, 1970.  https://link.springer.com/article/10.1007/BF00672455.
  * Busch [1990a] Paul Busch.  On the energy-time uncertainty relation. Part I: Dynamical time and time indeterminacy.  _Foundations of physics_ , 20(1):1–32, 1990a.
  * Busch [1990b] Paul Busch.  On the energy-time uncertainty relation. Part II: Pragmatic time versus energy indeterminacy.  _Foundations of Physics_ , 20(1):33–43, 1990b.
  * Busch [2008] Paul Busch.  The time–energy uncertainty relation.  In Juan Gonzalo Muga, Rafael Sala Mayato, and Íñigno Egusquiza, editors, _Time In Quantum Mechanics - Vol. 1_ , volume 734 of _Lecture Notes in Physics_ , pages 73–105. Springer, Berlin Heidelberg, second edition, 2008.  Preprint: https://arxiv.org/abs/quant-ph/0105049v3,.
  * Busch et al. [1995] Paul Busch, Marian Grabowski, and Pekka J. Lahti.  _Operational Quantum Physics_.  Berlin and Heidelberg: Springer-Verlag, 1995.
  * Folland [2008] Gerald B Folland.  _Quantum Field Theory: A tourist guide for mathematicians_ , volume 149 of _Mathematical Surveys and Monographs_.  Providence, Rhode Island: The American Mathematical Society, 2008.
  * Griffiths [1995] David J. Griffiths.  _Introduction to Quantum Mechanics_.  Upper Saddle River, NJ: Prentice Hall, 1995.
  * Hawking [1975] Stephen W Hawking.  Particle creation by black holes.  _Communications in mathematical physics_ , 43(3):199–220, 1975.
  * Hobson et al. [2006] Michael Paul Hobson, George P Efstathiou, and Anthony N Lasenby.  _General relativity: An introduction for physicists_.  Cambridge: Cambridge University Press, 2006.
  * Jones [2002] Goronwy Tudor Jones.  The uncertainty principle, virtual particles and real forces.  _Physics Education_ , 37(3):223–233, 2002.
  * Kato [1995] Tosio Kato.  _Perturbation Theory for Linear Operators_.  Springer-Verlag Berlin Heidelberg, 2nd edition, 1995.
  * Landau and Peierls [1931] Lev Landau and Rudolf Peierls.  Erweiterung des Unbestimmtheitsprinzips für die relativistische Quantentheorie.  _Zeitschrift für Physik_ , 69(1-2):56–69, 1931.
  * Landau and Lifshitz [1977] Lev Davidovich Landau and Evgenii Mikhailovich Lifshitz.  _Quantum mechanics: non-relativistic theory_ , volume 3 of _Course of Theoretical Physics_.  Oxford: Pergamon Press Ltd, third edition, 1977.  Translated by J. B. Sykes and J. S. Bell.
  * Ludwig [1983] G. Ludwig.  _Foundations of Quantum Mechanics_ , volume I.  Springer-Verlag New York, Inc., 1983.  Translated by Carl A. Hein from the 1954 German edition.
  * Ludwig [1985] G. Ludwig.  _Foundations of Quantum Mechanics_ , volume II.  Springer-Verlag New York, Inc., 1985.  Translated by Carl A. Hein from the 1954 German edition.
  * Peskin and Schroeder [1995] Michael E. Peskin and Daniel V. Schroeder.  _An Introduction to Quantum Field Theory_.  Reading, MA: Perseus Books Publishing, L.L.C., 1995.
  * Teller [1995] Paul Teller.  _An Interpretive Introduction to Quantum Field Theory_.  Princeton: Princeton University Press, 1995.