# Unsupervised Neural Quantization for Compressed-Domain Similarity Search

Stanislav Morozov
Yandex,
Lomonosov Moscow State University
<EMAIL_ADDRESS>Artem Babenko
Yandex,
National Research University
Higher School of Economics
<EMAIL_ADDRESS>
###### Abstract

We tackle the problem of unsupervised visual descriptors compression, which is
a key ingredient of large-scale image retrieval systems. While the deep
learning machinery has benefited literally all computer vision pipelines, the
existing state-of-the-art compression methods employ shallow architectures,
and we aim to close this gap by our paper. In more detail, we introduce a DNN
architecture for the unsupervised compressed-domain retrieval, based on multi-
codebook quantization. The proposed architecture is designed to incorporate
both fast data encoding and efficient distances computation via lookup tables.
We demonstrate the exceptional advantage of our scheme over existing
quantization approaches on several datasets of visual descriptors via
outperforming the previous state-of-the-art by a large margin.

##  1 Introduction

Unsupervised compression of high-dimensional visual descriptors has a long
history in the computer vision community[33, 14]. Nowadays, the development of
effective compact representations becomes even more crucial for the
scalability of modern search engines, given the enormous amount of visual data
in the Web.

Currently the dominant unsupervised compression methods[14, 6, 24, 2, 37, 22,
23] belong to the multi-codebook quantization (MCQ) paradigm. In this
paradigm, descriptors are effectively approximated by a sum or a concatenation
of a few $codeword$ vectors, coming from several disjoint codebooks. Such a
simple form of approximation enables the efficient computation of distances
from uncompressed queries to compressed database vectors via the usage of
lookup tables. While originally appeared for the image retrieval problem, the
quantization methods are extensively used to increase the efficiency in a wide
range of tasks, e.g. CNN compression[8, 36] or localization[19]. Indeed, the
development of more advanced quantization methods remains an important
research direction as they would benefit a whole range of large-scale computer
vision applications.

Despite the ubiquitous use of deep architectures in different areas of
computer vision, the unsupervised quantization for the compressed-domain
retrieval, which we tackle in this paper, did not benefit from their power
yet. While several recent works investigate the usage of deep architectures
for the supervised MCQ scenario[35, 11, 18], the state-of-the-art unsupervised
methods[22, 25, 23] remain shallow. Moreover, the recent work[27] has shown
that even for the supervised compression problem, the usage of unsupervised
MCQ outperforms several strong supervised baselines. To the best of our
knowledge, at the moment it is not clear if the deep learning machinery can
benefit the unsupervised quantization approaches. This is the central question
we aim to answer in our paper.

As the main novelty, we introduce a new Unsupervised Neural Quantization (UNQ)
method, which learns a nonlinear multi-codebook quantization model, trainable
via SGD. Our model is partially inspired by the ideas from the recent works on
generative modeling with discrete hidden variables[12, 21, 32], which, as we
show, appear to be a natural fit for the compressed-domain retrieval problem.
In its essence, UNQ works via embedding both codewords and data vectors into a
common learnable vector space, where efficient nearest neighbor retrieval is
possible. As we show in the experimental section, the non-linear nature of our
model allows increasing the retrieval accuracy, compared to the existing
shallow competitors.

Overall, the main contributions of our paper can be summarized as follows:

  1. 1.

We propose a new method for the unsupervised quantization of visual
descriptors. To the best of our knowledge, our method is the first successful
case of the usage of deep architectures for the unsupervised MCQ for
compressed-domain retrieval.

  2. 2.

With the extensive experimental evaluation, we show that the proposed method
outperforms the existing techniques in terms of retrieval performance. For
most operating points our method provides a new state-of-the-art on two common
benchmarks.

  3. 3.

The Pytorch implementation of the proposed method is available
online111https://github.com/stanis-morozov/unq.

The rest of the paper is organized as follows. In Section 2 we review the
existing unsupervised quantization approaches. The proposed Unsupervised
Neural Quantization model is described in Section 3 and experimentally
evaluated in Section 4. Section 5 concludes the paper.

##  2 Related work

In this section we briefly review the main ideas from the previous works that
are relevant for our method.

High-dimensional data compression. The existing methods for the high-
dimensional data compression mostly fall into two separate lines of research.
The first family[33, 7, 9] includes binary hashing methods, which map the
original vectors into the Hamming space such that nearby vectors are mapped
into hashes with small Hamming distances. The practical advantage of binary
hashing is that it heavily benefits from the efficient binary computations in
modern CPU architectures. The second family of methods generalizes the idea of
vector quantization, and we refer to these methods as multi-codebook
quantization (MCQ). MCQ methods typically do not involve the information loss
on the query side, hence they typically outperform the binary hashing methods
by a large margin. The state-of-the-art compression accuracy is currently
achieved by the recent MCQ methods[25, 23] and in this paper we aim to improve
their quality even further via the power of deep architectures.

Product quantization (PQ)[14] is a pioneering method from the MCQ family,
which inspired further research on this subject. PQ encodes each vector
$x\in\mathbf{R}^{D}$ as a concatenation of $M$ codewords from $M$
$\frac{D}{M}$-dimensional codebooks $C_{1},\ldots,C_{M}$, each containing $K$
codewords. In other words, PQ decomposes a vector into $M$ separate subvectors
and applies vector quantization (VQ) to each subvector, while using a separate
codebook. As a result each vector $x$ is encoded by a tuple of codewords
indices $[i_{1},\ldots,i_{M}]$ and approximated by
$x\approx[c_{1i_{1}},\ldots,c_{Mi_{M}}]$. Fast Euclidean distance computation
becomes possible via efficient ADC procedure[14] using lookup tables:

$\displaystyle\|q-x\|^{2}\approx\|q-[c_{1i_{1}},\ldots,c_{Mi_{M}}]\|^{2}=$ (1)
$\displaystyle\sum\limits_{m=1}^{M}{\|q_{m}-c_{mi_{m}}\|}^{2}$

where $q_{m}$ — $m$th subvector of a query $q$. This sum can be calculated in
$M$ additions and lookups given that distances from query subvectors to
codewords are precomputed.

From the geometry viewpoint, PQ effectively partitions the original vector
space into $K^{M}$ cells, each being a Cartesian product of $M$ lower-
dimensional cells. Such product-based approximation works better if the
$\frac{D}{M}$-dimensional components of vectors have independent
distributions. The degree of dependence is affected by the choice of the
splitting, and can be further improved by orthogonal transformation applied to
vectors as preprocessing. Two subsequent works have therefore looked into
finding an optimal transformation [6, 24]. The modification of PQ
corresponding to such pre-processing transformation is referred below as
Optimized Product Quantization (OPQ).

Figure 1: The proposed Unsupervised Neural Quantization model architecture.
The encoder(left) maps data vector into a product of learned spaces (middle),
selects codewords and decodes them back into the original vector space
(right). The grey ellipses represent the codebook spaces and the orange
hexagons denote the codewords in those codebooks.

Non-orthogonal quantizations. Several works [5, 2, 37, 22, 25, 23] generalize
the idea of Product Quantization by approximating each vector by a sum of $M$
codewords instead of concatenation. In this case, the ADC procedure is still
efficient while the approximation accuracy is increased.

The first approach, Residual Vector Quantization [5], quantizes original
vectors, and then iteratively quantizes the approximation residuals from the
previous iteration. Another approach, Additive Quantization (AQ) [2], is the
most general as it does not impose any constraints on the codewords from the
different codebooks. Usually, AQ provides the smallest compression errors,
however, it is much slower than other methods, especially for large $M$.
Composite Quantization (CQ) [37] learns codebooks with a fixed value of scalar
product between the codewords from different codebooks. Several recent
works[22, 23, 25] elaborate the idea of Additive Quantization, proposing the
more effective procedure for codebooks learning. Currently, state-of-the-art
compression accuracy is achieved by the LSQ method[23]. We present the
qualitative comparison of the existing MCQ methods with the open-source
implementations as well as the proposed UNQ method in Table $1$.

Method | (O)PQ | AQ/LSQ | UNQ
---|---|---|---
Compression Quality | Medium | High | High
Encoding complexity | Low | High | Low
Learning complexity | Low | High | High
Table 1: The qualitative comparison of Unsupervised Neural Quantization (UNQ)
with the existing quantization methods.

Compression with DNN. Several recent works[35, 11, 18] investigate the usage
of deep architectures for multi-codebook quantization in the supervised
compression scenario. In contrast, we tackle the more challenging unsupervised
setup, where only shallow quantization methods are currently in use. To the
best of our knowledge, there is only one recent paper[26] that employs a deep
architecture for the unsupervised compression problem, but it does not work in
the MCQ paradigm. Instead, [26] performs neighborhood-preserving mapping to a
sphere with an additional ”spreading” regularizer that enforces the uniform
distribution of mapped data points. Then [26] uses the fixed predefined
lattices to quantize the data vectors. In our experiments, we demonstrate the
advantage of UNQ over [26] in most operating points.

At the same time, several recent studies on generative modeling developed
efficient ways to learn discrete representations with deep neural networks.
One branch of such methods relies on continuous noisy relaxations of the
discrete variables that can be trained by backpropagation [12, 21, 31].
Another popular approach to learning discrete variables is featured in Vector-
Quantized Variational Autoencoder model[32, 17]. Instead of continuous
relaxation, this approach uses straight-through gradient estimation to
propagate gradient through discrete variables. To the best of our knowledge,
our work is the first that experimentally demonstrates that with the
appropriate training protocol, the discrete hidden variables can be
successfully used for compressed-domain retrieval in the unsupervised
scenario. While we acknowledge the existence of the recent concurrent
preprint[34], which studies the close ideas, its experimental evaluation shows
the performance of their approach to be on par with binary hashing methods,
which are improper baselines. In contrast, our UNQ approach substantially
outperforms the current state-of-the-art, as will be shown in experiments.
While in this paper our approach is used only for compression of precomputed
descriptors, the proposed architecture can be combined with existing self-
supervised methods[4] for end-to-end unsupervised image compression.

##  3 Unsupervised Neural Quantization

We now introduce notation and discuss the proposed UNQ method in detail.
Below, we always assume that image descriptors are vectors from the Euclidean
space $\mathbf{R}^{D}$.

###  3.1 Motivation

All the existing quantization methods contain two essential modules: the
encoder and the distance function.

The encoder $f(x):\mathbf{R}^{D}\rightarrow\\{1,\dots,K\\}^{M}$ maps a data
vector $x$ into a tuple of $M$ indices
$\boldsymbol{i}=\left[i_{1},\dots,i_{M}\right]$. In turn, the distance
function
$d(q,\boldsymbol{i}):\mathbf{R}^{D}\times\\{1,\dots,K\\}^{M}\rightarrow\mathbf{R}$
estimates how far a query $q$ is from an encoded database vector $f(x)$. Both
$f(\cdot)$ and $d(\cdot,\cdot)$ typically depend on learnable parameters (e.g.
the quantization codebooks in PQ or the rotation matrix in OPQ).

Currently, the state-of-the-art unsupervised quantization methods use shallow
encoders and distance functions. In this study, we instead propose to use deep
parametric models for both $f(\cdot)$ and $d(\cdot,\cdot)$ that are jointly
trained to perform nearest neighbor retrieval.

###  3.2 Model

The architecture of our model is schematically presented on Figure 1. There
are two main parts: the encoder maps the data vector $x$ into a tuple of
discrete codes, and the decoder reconstructs the original vector from its
compressed representation.

In the encoder part, we use a simple feedforward neural network $net(x)$ with
$M$ output ”heads”, which are trained jointly. As will be shown below, one can
think of $net(x)=\left[net(x)_{1},\dots,net(x)_{M}\right]$ as a mapping of
data vectors into a product of $M$ learned spaces. Each of the spaces in this
product posesses a codebook of $K$ codewords and we denote by $c_{mk}$ the
codeword $k$ from the codebook $m$, $m\in\\{1,\dots,M\\},k\in\\{1,\dots,K\\}$.

We use this model to define the stochastic encoding function that assigns data
vectors to discrete codes based on the dot product in the learned space. In
particular, the probability of being encoded by the $k$-th code from $m$-th
codebook is defined as:

$p(c_{mk}|x)=\frac{\exp\left({\langle
net(x)_{m},c_{mk}\rangle/\tau_{m}}\right)}{\underset{j}{\sum}\exp\left({\langle
net(x)_{m},c_{mj}\rangle/\tau_{m}}\right)}$ (2)

Here $\tau_{m}\in(0,\infty)$ defines the temperature (inverse ”peakyness”) of
the probability distribution. We treat both $c_{mk}$ and $\tau_{m}$ as regular
model parameters and optimize them with backpropagation.

Assuming conditional independence between the probabilities of codewords in
different codebooks for a given $x$, we get:

$p(c_{1},...,c_{M}|x)=\prod_{i=m}^{M}p(c_{m}|x)$ (3)

We can now define our encoding function by maximizing over those
probabilities:

$\begin{gathered}f(x)=\underset{c_{1},...,c_{M}}{\text{argmax
}}{p(c_{1},...,c_{M}|x)}=\\\ =[\underset{c_{1k}}{\text{argmax
}}{p(c_{0k}|x)},...,\underset{c_{Mk}}{\text{argmax }}{p(c_{Mk}|x)}]=\\\
=[\underset{c_{1k}}{\text{argmax }}{\langle
net(x)_{1},c_{1k}\rangle},...,\underset{c_{Mk}}{\text{argmax }}{\langle
net(x)_{M},c_{Mk}\rangle}]\end{gathered}$ (4)

However, in order to train our model we require encoder to be differentiable.
Inspired by[29], we use a differentiable approximation of $f(x)$ using Gumbel-
Softmax[12, 21] trick. The differentiable approximation $\tilde{f}_{m}(x)$ for
$m$-th codebook is a stochastic function that maps $x$ to a vector:

$\tilde{f}(x)_{m}=softmax\\{\log p(c_{mj}|x)+z_{j},j{=}1..K\\}$ (5)

In the formula above, $z_{j}$ is a sample from the standard Gumbel
distribution that can be obtained as $z_{j}=-\log(-\log Uniform(0,1))$. Note
that the original Gumbel-Softmax distribution[12] divides all exponent rates
by a small temperature factor, which we set to $1$ in all our experiments.

While the relaxation $\tilde{f}(x)_{m}$ is differentiable, it does not produce
one-hot vectors, which are needed for quantization methods. Hence during
training we discretize $\tilde{f}(x)_{m}$ via using $argmax$ instead of
$softmax$ in (5), which results in one-hot vector, corresponding to the index
of the chosen codeword. While this discretization is not differentiable, we
backpropagate through it using straight-through gradient estimation: the
gradients w.r.t. function outputs are passed to its inputs with no
transformation applied.

Then we feed $M$ one-hot vectors, produced by the encoder, into decoder
$g(\cdot)$: another feedforward network that adds the corresponding codewords
and reconstructs the vector $\tilde{x}$ in the original data space.

In all our experiments, both $net(\cdot)$ and $g(\cdot)$ are simple fully-
connected neural networks with ReLU activation functions and Batch
Normalization[10] layers before each activation (see Figure 1). We describe
the particular choice of $net(\cdot)$ and $g(\cdot)$ in the experimental
section.

###  3.3 Nearest Neighbor Search

The retrieval of nearest neighbors in a quantized database is performed via
the exhaustive search with distance function $d(q,\boldsymbol{i})$:

$\underset{\boldsymbol{i}}{\text{argmin }}d(q,\boldsymbol{i})$ (6)

In our model, we use two different definitions for $d(q,\boldsymbol{i})$ to
provide both high compression accuracy and efficient retrieval.

The first ”naive” distance function reconstructs the database vector with the
decoder $g$ and measures distance in the original data space:

$d_{1}(q,\boldsymbol{i})=\left\lVert q-g(\boldsymbol{i})\right\lVert_{2}^{2}$
(7)

However, the usage of $d_{1}$ for exhaustive search would require applying the
decoder network to the whole database, inducing a prohibitively large
computational cost for large databases.

Alternatively, one can define the distance function in the learned space of
codebooks. This definition relies on the fact that both query mapping $net(q)$
and codewords belong to a shared space. This space is conveniently equipped
with a dot-product-based probability (2) of picking a particular codeword.

Our intuition is that the nearest neighbor of data point $q$ should have
codewords that are likely to be assigned to $q$ itself. In other words, in
order to search for the nearest neighbors of $q$ we want to consider
candidates with the highest $p(c_{1},...,c_{M}|q)$. This naturally leads us to
the following distance function:

$\displaystyle
d_{2}(q,\boldsymbol{i})=d_{2}(q,\\{i_{1},\dots,i_{M}\\})=-logp(c_{1i_{1}},...,c_{Mi_{M}}|q)=$
$\displaystyle=-\sum_{m=1}^{M}\left(\langle
net(q)_{m},c_{m{i_{m}}}\rangle-\log\sum_{k=1}^{K}\exp\langle
net(q)_{m},c_{mk}\rangle\right)=$ $\displaystyle=-\sum_{m=1}^{M}\langle
net(q)_{m},c_{m{i_{m}}}\rangle+const(q)$ (8)

Compared to (7), the second formulation allows for an efficient search
algorithm via lookup tables. First, the algorithm computes the dot products of
$net(q)$ with the codewords in all codebooks using one pass of the encoder
network and $O(M\cdot K)$ dot product computations. The algorithm can then
find the nearest neighbor by iterating over the encoded data points and
summing the cached distances, doing only $M$ additions per database vector.

The search based on distance function (8) can be seen as a generalization of
existing quantization methods. However, unlike [6, 22], the distance is
computed not in the original data space but in a new learned space that is
obtained via SGD training.

In practice, we combine both distance functions in a two-stage search: at
first, we efficiently select $L$ nearest candidates based on $d_{2}$, and then
re-rank those candidates using the more expensive $d_{1}$. The additional
reranking stage does not influence the total scheme efficiency by much, as
only a small fraction of the database is reranked.

Of course, the existing shallow methods can also benefit from the additional
reranking with DNN and we compare our scheme with this baseline in the
experiments. Our experiments below demonstrate that the post-search reranking
slightly increases the accuracy of shallow MCQ methods, but the overall
performance of UNQ is substantially higher.

###  3.4 Training

We train our model by explicitly fitting the two distance functions to
maximize recall. The first distance function is defined in the original data
space and can be trained with autoencoder-like objective:

$L_{1}=\frac{1}{n}\sum_{x_{i}}d_{1}(x_{i},\tilde{x_{i}})=\frac{1}{n}\sum_{x_{i}}\left\lVert
x_{i}-g(\tilde{f}(x_{i}))\right\lVert_{2}^{2}$ (9)

However, there is no guarantee that minimizing this objective would result in
good candidates being selected for the reranking stage. Therefore, we also
need to train $d_{2}(\cdot,\cdot)$ with another objective term.

We employ a metric learning approach by minimizing the triplet loss in the
learned space. Intuitively, we want $x$ to be closer to it’s true nearest
neighbor $x_{+}$ than to the negative example $x_{-}$.

$L_{2}=\frac{1}{n}\sum_{x}max(0,\delta+d_{2}(x,f(x_{+}))-d_{2}(x,f(x_{-})))$
(10)

Similarly to [26], we sample $x_{+}$ from top-$3$ true nearest neighbors of
data point $x$. In turn, $x_{-}$ is sampled uniformly from between $100$-th to
$200$-th nearest neighbors, excluding $x$ itself and three candidates for
$x_{+}$. Following a popular practice from the metric learning field, we
sample those vectors at the offset of each training epoch.

The final term for our objective is a regularizer for Gumbel-Softmax that
encourages equal frequency of codewords. A common problem of nearly all
methods for learning discrete variables is that they converge to poor local
optima where some codes are (almost) never used. In order to alleviate this
issue, we repurpose the squared Coefficient of Variation regularizer that was
originally proposed in [28] to combat a similar imbalance in the Mixture of
Experts layers.

The coefficient of variation is computed from codeword probabilities averaged
over the training batch $X$:

$p_{avg}(i_{m}|X)={\frac{1}{n}}\sum_{x_{i}\in X}p(i_{m}|x_{i})$

$CV^{2}(i_{m})=\frac{Var[p_{avg}(i_{m}|X)]}{\left[E[p_{avg}(i_{m}|X)]\right]^{2}}$
(11)

Our final objective is just a sum of those three terms with coefficients. In
our experiments we pick $\alpha$ from $\\{0.1,0.01,0.001\\}$ via grid search.
As for $\beta$, we decrease it linearly from $1.0$ to $0.05$ during training.

$L=L_{1}+\alpha\cdot L_{2}+\beta\cdot\frac{1}{M}\sum_{m=1}^{M}CV^{2}(i_{m})$
(12)

The model is trained to minimize the training objective $L$ using minibatch
gradient descent with the recent Quasi-Hyperbolic Adam algorithm [20]. We also
use One Cycle learning rate schedule[30] for faster model convergence.

##  4 Experiments

In this section we provide the experimental results that compare the proposed
Unsupervised Neural Quantization (UNQ) method with the existing unsupervised
compression methods. Following the recent work[26], we perform the most of
experiments on two sets of data:

  1. 1.

Deep1M/Deep10M/Deep1B datasets contain $96$-dimensional visual descriptors,
which are computed from the activations of a deep neural network[3]. Base sets
include $10^{6}$, $10^{7}$ and $10^{9}$ vectors correspondingly. We use the
additional separate sets of 500.000 vectors for training and 10.000 hold-out
queries for evaluation.

  2. 2.

BigANN1M/BigANN10M/BigANN1B datasets contain $128$-dimensional histogram-based
SIFT descriptors[15]. Base sets include $10^{6}$, $10^{7}$ and $10^{9}$
vectors correspondingly. Here we also use the separate sets of 500.000 vectors
for training and 10.000 hold-out queries for evaluation.

Unless stated otherwise, we always learn the method parameters on the train
set, then compress the base set and evaluate the retrieval performance on the
query set. As a common measure of compressed-domain retrieval performance we
report Recall@k (for $k=1,10,100$), which is the probability that the true
nearest neighbor is among $k$ closest neighbors in the compressed dataset. Two
compression levels ($8$, $16$ bytes per vector) were evaluated. In all the
experiments we used the quantization codebooks of $K=256$ codewords for all
the methods.

Method | BigANN1M | Deep1M
---|---|---
R@1 | R@10 | R@100 | R@1 | R@10 | R@100
| 8 bytes per vector
OPQ | 20.8 | 64.3 | 95.3 | 15.9 | 51.3 | 88.6
Catalyst + OPQ | 26.2 | 73.0 | 97.3 | 20.9 | 61.5 | 93.5
Catalyst + Lattice | 28.9 | 75.8 | 97.9 | 24.6 | 68.3 | 96.1
LSQ | 29.2 | 77.7 | 98.7 | 21.7 | 64.0 | 94.5
LSQ + rerank | 30.3 | 78.9 | 98.8 | 22.8 | 65.7 | 95.6
UNQ | 34.6 | 82.8 | 99.0 | 26.7 | 72.6 | 97.3
| 16 bytes per vector
OPQ | 40.9 | 89.8 | 99.9 | 35.0 | 82.5 | 99.1
Catalyst + OPQ | 46.1 | 92.0 | 99.8 | 39.0 | 86.5 | 99.3
Catalyst + Lattice | 49.1 | 94.1 | 100.0 | 44.8 | 90.8 | 99.8
LSQ | 57.1 | 97.5 | 100.0 | 41.1 | 88.6 | 99.5
LSQ + rerank | 57.7 | 97.6 | 100.0 | 42.4 | 89.5 | 99.6
UNQ | 59.3 | 98.0 | 100.0 | 47.9 | 93.0 | 99.8
Table 2: The compressed-domain retrieval performance achieved by unsupervised
compression approaches. The proposed UNQ method outperforms all the
competitors on both datasets and under both memory budgets.

###  4.1 Comparison to the state-of-the-art

As a preliminary experiment, we compare the proposed UNQ method with the
current state-of-the-art approaches for the unsupervised compression problem
on the million-scale Deep1M and Bigann1M datasets. In particular, we compare
the following methods:

  * •

OPQ[6, 24], with the implementation from the Faiss library[16].

  * •

Catalyst+OPQ[26] that uses OPQ on top of the ”spreaded” vectors, as described
in [26]. We use the implementation provided by the authors and tune $d_{out}$
and $\lambda$ hyperparameters for optimal performance.

  * •

Catalyst+Lattice[26] that uses the fixed predefined lattice on a sphere for
vector quantization. Here we also use the implementation provided by the
authors and tuned $d_{out}$ and $\lambda$ hyperparameters. The dimension of
hidden layers was set to $2048$ neurons. The lattice quantizers with
$r^{2}=79$ for $8$ bytes and $r^{2}=253$ for $16$ bytes were used.

  * •

LSQ[22], the state-of-the-art shallow quantization method that approximates
each vector by a sum of codewords. We use the implementation provided by the
authors.

  * •

LSQ+rerank, that additionally reranks some top of LSQ results by the learned
decoder with two hidden layers of $1024$ neurons. The decoder obtains
$D$-dimensional LSQ approximations as an input and is trained to minimize the
reconstruction objective (9). The number of elements to rerank is the same as
for UNQ.

  * •

UNQ, our method, introduced in this paper. We use the architecture similar to
[26]: the encoder and decoder consist of two 1024-unit linear layers, each
equipped with Batch Normalization and ReLU activation function. The
dimensionality of codewords was set to $256$, and we rerank top-500
candidates.

The recall values achieved by the different methods are presented in Table 2.
Below we highlight several key observations:

Method | BigANN10M | Deep10M
---|---|---
R@1 | R@10 | R@100 | R@1 | R@10 | R@100
| 8 bytes per vector
Catalyst + Lattice | 20.9 | 63.9 | 94.3 | 18.2 | 53.5 | 88.7
LSQ | 21.7 | 64.3 | 95.0 | 14.8 | 48.1 | 84.8
LSQ + rerank | 21.8 | 64.8 | 95.0 | 15.1 | 48.8 | 85.9
UNQ | 25.8 | 70.5 | 96.3 | 18.8 | 57.0 | 90.9
| 16 bytes per vector
Catalyst + Lattice | 42.0 | 90.0 | 99.7 | 37.9 | 84.6 | 99.2
LSQ | 50.5 | 95.0 | 99.9 | 34.3 | 79.8 | 98.2
LSQ + rerank | 50.7 | 95.3 | 99.9 | 34.5 | 81.1 | 98.4
UNQ | 52.1 | 95.4 | 99.9 | 40.1 | 86.8 | 99.3
Table 3: The performance on the ten million datasets. On this scale, the advantage of the proposed Unsupervised Neural Quantization method over existing approaches persists. Method | BigANN1B | Deep1B
---|---|---
R@1 | R@10 | R@100 | R@1 | R@10 | R@100
| 8 bytes per vector
Catalyst + Lattice | 10.4 | 37.6 | 76.6 | 16.8 | 38.7 | 68.2
LSQ | 9.6 | 35.9 | 73.3 | 13.2 | 32.3 | 59.9
LSQ + rerank | 9.9 | 36.1 | 73.8 | 12.3 | 31.6 | 59.7
UNQ | 13.0 | 44.5 | 82.4 | 14.5 | 37.8 | 68.5
| 16 bytes per vector
Catalyst + Lattice | 31.1 | 77.8 | 98.3 | 35.3 | 72.8 | 95.6
LSQ | 38.0 | 85.6 | 99.3 | 30.5 | 65.0 | 91.1
LSQ + rerank | 37.6 | 86.0 | 99.3 | 30.1 | 65.8 | 91.4
UNQ | 38.3 | 86.8 | 99.4 | 35.5 | 74.2 | 96.1
Table 4: The performance on the one billion datasets. The proposed UNQ method
outperforms the competitors in most operating points.

  * •

On both datasets and for both compression levels the introduced Unsupervised
Neural Quantization outperforms the competitors and provides a new state-of-
the-art for the unsupervised compression problem.

  * •

The current state-of-the-art methods Catalyst+Lattice and LSQ are competitive
on different types of visual data. While LSQ outperforms Catalyst+Lattice on
shallow SIFT descriptors, its accuracy is much lower on deep descriptors.
Meanwhile, the proposed UNQ provides the highest accuracy on both datasets,
which makes it a universal method for all types of data.

  * •

An additional reranking stage with a learnable decoder provides only a slight
improvement for the shallow LSQ method. This indicates that the end-to-end
learning in UNQ is crucial for high compression accuracy.

###  4.2 Additional memory consumption

Here we analyze the additional memory consumption required by the proposed UNQ
method. Compared to the shallow baselines UNQ additionally stores the
parameters of the feed-forward encoder and decoder networks. In our
experiments, the model requires about 19.8 Mb for 8-byte budget and 30.1 Mb
for 16-byte budget, which is on par with the Catalyst+Lattice[26] which
requires 17.2 Mb. Note, that this amount does not depend on the number of
database vectors. For instance, for databases of one billion vectors, this
results only in negligible 0.02 additional bytes per vector. As the most
important experiment, we verify that the advantage of UNQ persists for more
massive datasets. Namely, we perform the comparison of Catalyst+Lattice, LSQ,
and UNQ on larger datasets Deep10M and BigANN10M, and billion-scale datasets
Deep1B and BigANN1B. The results are shown in Table 3 and Table 4 and
demonstrate that UNQ always outperforms a shallow LSQ counterpart by a
considerable margin. UNQ also outperforms Catalyst+Lattice in most operating
points, except for R@1,R@10 on 8-bytes encoding on Deep1B. For Deep1B and
BigANN1B we rerank top-1000 candidates since it requires a negligible time in
comparison with the billion-scale search.

###  4.3 Ablation

In this section we empirically validate our choice of training architecture
and model by evaluating the contribution of each component. All experiments in
this section fit the budget of $M{=}8$ bytes per vector on the BigANN1M
dataset. More specifically, we compare

  * •

UNQ — our primary model that is built and trained in accordance with the
description provided in Section 3 with all parameters described in the first
experiment.

  * •

Exhaustive reranking — like UNQ, but the nearest neighbor search is performed
with $d_{1}(\cdot,\cdot)$ only. This approach requires reconstructing every
data vector by running the decoder module once for every vector in the
database. This setup was evaluated on the same model parameters as UNQ.

  * •

No reranking — the training procedure is the same as for UNQ, but the search
is implemented without reranking by the decoder.

  * •

No triplet loss — UNQ model that performs two-stage search but does not
optimize for $d_{2}(\cdot,\cdot)$ explicitly, i.e. $\alpha=0$. This is
equivalent to training a regularized discrete variational autoencoder without
explicit requirements to its hidden representation.

  * •

Triplet only — like UNQ, but the nearest neighbor search is performed with
$d_{2}(\cdot,\cdot)$ only. This model is also trained using $\alpha=1.0$ and
without the term (9).

  * •

UNQ w/o hard — like UNQ, but Gumbel-Softmax without hard assignment
discretization, as in [13].

  * •

UNQ w/o Gumbel — like UNQ, but the quantization is implemented as in [1] with
$\beta{=}0.1$.

  * •

No regularizer — same as UNQ, but the balance regularizer term is set to
$\beta=0$. All other parameters are unchanged.

Method | BigANN1M, 8 bytes
---|---
R@1 | R@10 | R@100
UNQ | 34.6 | 82.8 | 99.0
Exhaustive reranking | 34.6 | 82.8 | 99.3
No reranking | 25.0 | 68.5 | 95.0
No triplet loss | 35.5 | 83.4 | 95.7
Triplet only | 27.9 | 72.6 | 99.2
UNQ w/o hard | 33.8 | 80.4 | 98.0
UNQ w/o Gumbel | 30.2 | 75.7 | 78.1
No regularizer | 31.0 | 80.4 | 95.2
Table 5: Ablation study for different training objectives.

The results in Table 5 suggest that each of the three core components of our
approach (reranking, triplet loss, CV regularizer) influences the model
performance. The reranking stage with $L=500$ candidates is predictably less
important on $R@100$, compared to $R@1$, as one can see from the comparison
between UNQ and No reranking. The triplet loss term benefits $R@100$, while
the CV regularizer provides significant gains across all three recall areas.
Note, that the usage of the Gumbel-Softmax trick outperforms the
differentiable quantization, proposed in [1]. Finally, the usage of ”hard”
version of Gumbel-Softmax trick results in higher performance compared to UNQ
w/o hard option.

###  4.4 Timings

Finally, we discuss the timings needed to encode the database and search over
compressed data.

Encoding the database points with UNQ has almost the same complexity as in
Catalyst as it requires the only feed-forward pass through two fully-connected
layers. In particular, the encoding time of Deep1M for $8$ bytes per point on
the single Nvidia 1080Ti GPU for the UNQ requires about 1.5 seconds, while for
the Catalyst+Lattice it is about 4.1 seconds on the same GPU card. The LSQ
encoding is slower as it requires several optimization iterations, in our
experiments it took 27 seconds to encode Deep1M with the authors’
implementation.

Search. Unlike the existing competitors, the proposed UNQ method includes an
additional reranking stage, that reconstructs a few candidates with the feed-
forward decoder and computes the distances in the original $D$-dimensional
space. Because the number of candidates is typically small, the reranking
stage almost does not influence the total search runtime. E.g. on the Deep1B
dataset with $M{=}8$ the exhaustive scan with $d_{2}(\cdot,\cdot)$ (via lookup
tables) requires 3 seconds. Meanwhile, the reranking of 1000 candidates,
implemented via BLAS instructions with the Intel MKL library, requires only
25.9 ms. Both timings are obtained in a single-CPU mode on the same machine.
This indicates that the additional runtime cost from reranking is
insignificant, especially for large databases or longer codes. Note, that the
search in the Catalyst+Lattice method is slower compared to the LUT-based
methods, namely, [26] reports about $1.5\times$ increase in search runtime for
$8$-byte codes.

##  5 Conclusion

We have presented Unsupervised Neural Quantization (UNQ) — a new unsupervised
compression scheme for the problem of compressed-domain retrieval. Our scheme
employs the ideas from the recent works on discrete auto-encoders and shows
that with the proper training objective the hidden variables can successfully
serve as quantized representations for efficient retrieval. From another point
of view, our method can be seen as a natural ”deep” generalization of the
existing shallow quantization methods, such as AQ or LSQ.

By a large number of experiments, we demonstrate the advantage of UNQ over the
state-of-the-art approaches, such as LSQ and the recent lattice-based
quantizer. Furthermore, while the existing methods perform differently on
different types of data, UNQ provides the highest retrieval accuracy on both
histogram-based and deep descriptors.

For the reproducibility purposes, we publish the Pytorch implementation of
Unsupervised Neural Quantization online222https://github.com/stanis-
morozov/unq.

## References

  * [1] Eirikur Agustsson, Fabian Mentzer, Michael Tschannen, Lukas Cavigelli, Radu Timofte, Luca Benini, and Luc V Gool.  Soft-to-hard vector quantization for end-to-end learning compressible representations.  In Advances in Neural Information Processing Systems, pages 1141–1151, 2017.
  * [2] Artem Babenko and Victor S. Lempitsky.  Additive quantization for extreme vector compression.  2014\.
  * [3] Artem Babenko and Victor S. Lempitsky.  Efficient indexing of billion-scale datasets of deep descriptors.  2016\.
  * [4] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze.  Deep clustering for unsupervised learning of visual features.  In Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XIV, pages 139–156, 2018.
  * [5] Yongjian Chen, Tao Guan, and Cheng Wang.  Approximate nearest neighbor search by residual vector quantization.  In Sensors, 2010.
  * [6] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun.  Optimized product quantization for approximate nearest neighbor search.  2013\.
  * [7] Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin.  Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval.  IEEE Trans. Pattern Anal. Mach. Intell., 35(12):2916–2929, 2013\.
  * [8] Yunchao Gong, Liu Liu, Ming Yang, and Lubomir D. Bourdev.  Compressing deep convolutional networks using vector quantization.  CoRR, abs/1412.6115, 2014.
  * [9] Jae-Pil Heo, Youngwoon Lee, Junfeng He, Shih-Fu Chang, and Sung-Eui Yoon.  Spherical hashing.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, June 16-21, 2012, pages 2957–2964, 2012.
  * [10] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, pages 448–456, 2015.
  * [11] Himalaya Jain, Joaquin Zepeda, Patrick Pérez, and Rémi Gribonval.  Subic: A supervised, structured binary code for image search.  In IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 833–842, 2017.
  * [12] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  2016\.
  * [13] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  arXiv preprint arXiv:1611.01144, 2016.
  * [14] Hervé Jégou, Matthijs Douze, and Cordelia Schmid.  Product quantization for nearest neighbor search.  IEEE Trans. Pattern Anal. Mach. Intell., 33(1):117–128, 2011\.
  * [15] Herve Jegou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg.  Searching in one billion vectors: Re-rank with source coding.  In Proc.ICASSP, 2011.
  * [16] Jeff Johnson, Matthijs Douze, and Hervé Jégou.  Billion-scale similarity search with gpus.  arXiv preprint arXiv:1702.08734, 2017.
  * [17] Lukasz Kaiser, Samy Bengio, Aurko Roy, Ashish Vaswani, Niki Parmar, Jakob Uszkoreit, and Noam Shazeer.  Fast decoding in sequence models using discrete latent variables.  In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 2395–2404, 2018.
  * [18] Benjamin Klein and Lior Wolf.  In defense of product quantization.  CoRR, abs/1711.08589, 2017.
  * [19] Simon Lynen, Torsten Sattler, Michael Bosse, Joel A. Hesch, Marc Pollefeys, and Roland Siegwart.  Get out of my lab: Large-scale, real-time visual-inertial localization.  In Robotics: Science and Systems XI, Sapienza University of Rome, Rome, Italy, July 13-17, 2015, 2015.
  * [20] Jerry Ma and Denis Yarats.  Quasi-hyperbolic momentum and adam for deep learning.  CoRR, abs/1810.06801, 2018.
  * [21] Chris J. Maddison, Andriy Mnih, and Yee Whye Teh.  The concrete distribution: A continuous relaxation of discrete random variables.  CoRR, abs/1611.00712, 2016.
  * [22] Julieta Martinez, Joris Clement, Holger H. Hoos, and James J. Little.  Revisiting additive quantization.  In Computer Vision - ECCV 2016 - 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part II, pages 137–153, 2016.
  * [23] Julieta Martinez, Shobhit Zakhmi, Holger H. Hoos, and James J. Little.  LSQ++: lower running time and higher recall in multi-codebook quantization.  In Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XVI, pages 508–523, 2018.
  * [24] Mohammad Norouzi and David J. Fleet.  Cartesian k-means.  2013\.
  * [25] Ezgi Can Ozan, Serkan Kiranyaz, and Moncef Gabbouj.  Competitive quantization for approximate nearest neighbor search.  IEEE Trans. Knowl. Data Eng., 28(11):2884–2894, 2016.
  * [26] Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Hervé Jégou.  Spreading vectors for similarity search.  2018\.
  * [27] Alexandre Sablayrolles, Matthijs Douze, Nicolas Usunier, and Herve Jegou.  How should we evaluate supervised hashing?  In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2017, New Orleans, LA, USA, March 5-9, 2017, pages 1732–1736, 2017.
  * [28] Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc V. Le, Geoffrey E. Hinton, and Jeff Dean.  Outrageously large neural networks: The sparsely-gated mixture-of-experts layer.  CoRR, abs/1701.06538, 2017.
  * [29] Raphael Shu and Hideki Nakayama.  Compressing word embeddings via deep compositional code learning.  CoRR, abs/1711.01068, 2017.
  * [30] Leslie N Smith and Nicholay Topin.  Super-convergence: Very fast training of neural networks using large learning rates.  arXiv preprint arXiv:1708.07120, 2017.
  * [31] George Tucker, Andriy Mnih, Chris J. Maddison, John Lawson, and Jascha Sohl-Dickstein.  REBAR: low-variance, unbiased gradient estimates for discrete latent variable models.  In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 2624–2633, 2017.
  * [32] Aäron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu.  Neural discrete representation learning.  In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 6309–6318, 2017.
  * [33] Yair Weiss, Antonio Torralba, and Robert Fergus.  Spectral hashing.  In Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pages 1753–1760, 2008.
  * [34] Hanwei Wu and Markus Flierl.  Learning product codebooks using vector quantized autoencoders for image retrieval.  CoRR, abs/1807.04629, 2018.
  * [35] Tan Yu, Junsong Yuan, Chen Fang, and Hailin Jin.  Product quantization network for fast image retrieval.  In Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part I, pages 191–206, 2018.
  * [36] Jialiang Zhang and Jing Li.  PQ-CNN: accelerating product quantized convolutional neural network on FPGA.  In 26th IEEE Annual International Symposium on Field-Programmable Custom Computing Machines, FCCM 2018, Boulder, CO, USA, April 29 - May 1, 2018, page 207, 2018.
  * [37] Ting Zhang, Chao Du, and Jingdong Wang.  Composite quantization for approximate nearest neighbor search.  2014\.


# Multi-scale architecture for fast optical addressing and control of large
scale qubit arrays

T. M. Graham  E. Oh  and M. Saffman  Department of Physics, 1150 University
Ave., University of Wisconsin-Madison, Madison, WI, 53706, USA
<EMAIL_ADDRESS>
###### Abstract

We present a technique for rapid site-selective control of the quantum state
of particles in a large array using a combination of a fast deflector (e.g. an
acousto-optic deflector) and a relatively slow spatial light modulator. The
use of spatial light modulators for site-selective quantum state manipulation
has been limited due to slow transition times preventing rapid, consecutive
quantum gates. By partitioning the spatial light modulator into multiple
segments, and using a fast deflector to transition between them, it is
possible to substantially reduce the average time increment between scanner
transitions by increasing the number of gates that can be performed for a
single spatial light modulator full frame setting. We analyze the performance
of this device in two different configurations: in configuration 1, each
segment of the spatial light modulator addresses the full qubit array; in
configuration 2, each segment of the spatial light modulator addresses a sub-
array and an additional fast deflector positions that sub-array with respect
to the full qubit array. With these hybrid scanners we calculate qubit
addressing rates that are tens to hundreds of times faster than using an SLM
alone.

††journal: ao††articletype: Research Article

##  1 Introduction

The last decade has seen the demonstration of the first small and medium scale
quantum computing devices. The demanding requirements for quantum computing
have led to several different competing platforms using different physical
qubit technologies. One promising approach encodes qubits in internal states
of neutral atoms, which are trapped in an optical lattice contained in a
vacuum cell [1]. Such atomic lattices promise long qubit coherence times,
controllable interactions, and identical qubits; however, perhaps the most
attractive feature of an atom-based quantum computer is the ability to scale
to large numbers of qubits. This trait arises from flexibility and ease of
construction of large optical lattices using the mature technologies of high-
power lasers and various light patterning devices such as holograms and
spatial light modulators (SLMs). Optical lattices composed of $>1000$ traps
have already been demonstrated[2, 3] and arrays with more than 300
deterministically positioned atoms have been achieved[4]. The size of such
arrays is only limited by the available optical power and the array trapping
optics. Lattices with $>10,000$ trapping sites, based on existing technology,
can realistically be anticipated in the next few years.

However, rapidly performing quantum gates on such a large number of qubits
remains a challenge. Standard techniques for performing multi-qubit gates (or
multiple parallel single-qubit gates) on neutral atom qubits require the
ability to optically address targeted qubits with focused lasers without
illuminating non-targeted qubits. Techniques to perform multi-qubit addressing
on small-scale optical lattice quantum computers[5] are not efficiently
scalable to larger arrays and/or multi-qubit gates that require simultaneous
illumination of multiple qubits. Available technologies for rapidly scanning
optical beams across multiple spatial locations have been reviewed in [6, 7].
As pointed out in these references, there are technologies such as
piezoelectric devices, galvanometer mirrors, and liquid crystal or digital
micro mirror device (DMD) spatial light modulators that can flexibly address
many spatial locations but are relatively slow. Technologies that are very
fast, such as acousto-optic and electro-optic beam scanners, cannot
arbitrarily address many spatial locations. We reveal here a new architecture
that combines fast and slow devices to achieve rapid addressing of a large
number of spatial locations.

Scalable control of large qubit arrays is challenging due to the competing
requirements of addressing multiple trap sites simultaneously and being
quickly reconfigurable while allowing many gates to be performed in the qubit
coherence time. The former requirement can be achieved using SLMs. These
devices allow a spatially varying amplitude and/or phase mask to be applied to
an incident light field. When used as a hologram, an arbitrary illumination
pattern can be generated on the qubit array, allowing the addressing of
multiple qubit sites with high diffraction efficiency. These devices have the
additional benefit of also being able to shape optical beams to allow more
uniform illumination [8] and correct some optical aberrations in the beam path
[9, 10, 11, 8]. Unfortunately, the switching speed of such spatial light
modulators is slow, typically 1 kHz or less for liquid crystal-based SLMs.
DMDs may be modulated at up to 20 kHz but only provide binary amplitude
modulation, which limits the diffraction efficiency to $\leq 10\%$[12].

In contrast to SLM qubit addressing, fast deflectors such as electro-optic
deflectors (EOD) and acousto-optic deflectors (AODs) provide efficient,
quickly reconfigurable qubit addressing, but are limited in their ability to
address multiple sites simultaneously[13, 5]. EODs deflect an incoming light
beam using either Kerr or Pockels interactions. While very efficient, EODs are
currently bulkier, less commercially available, and have a smaller scan range
than AODs. For this reason, we will analyze the performance of this scanner in
the context of using AODs rather than EODs; however much of this analysis can
be extended to any beam deflector technology. In an AOD, a transducer creates
a traveling acoustic wave in a crystal; the spatially varying index of
refraction caused by this wave acts as a traveling bulk diffraction grating on
an incoming light beam. This traveling wave both diffracts the light and gives
the first-order diffracted beam a frequency shift equal to the acoustic wave
frequency. By adjusting the acoustic wave driving frequency, the angle of the
output diffracted beam can be controlled in one dimension. Using two
perpendicularly oriented AODs, an input beam can be steered in two dimensions.
To address multiple sites, an AOD is driven with multiple frequencies;
however, this addressing scheme cannot be used to simultaneously address
arbitrary sites in a qubit array. When steering a single optical beam with a
2D AOD scanner, two frequencies are needed, a horizontal frequency $f_{1,x}$
and a vertical frequency $f_{1,y}$. However, driving horizontal and vertical
AODs each with two different frequencies, $f_{1,x}$, $f_{2,x}$, $f_{1,y}$,
$f_{2,y}$, will NOT result in two diffracted beams (one corresponding to the
first $x,y$ frequency pair and one corresponding to the second frequency pair)
because nothing prevents diffraction at cross-indexed frequency combinations.
Driving with two horizontal and two vertical frequencies will instead result
in four diffracted beams corresponding to frequency combinations:
$(f_{1,x},f_{1,y})$, $(f_{1,x},f_{2,y})$, $(f_{2,x},f_{1,y})$, and
$(f_{2,x},f_{2,y})$. More generally, if there are $N_{l}$ frequencies driving
the horizontal AOD and $M_{l}$ frequencies driving the vertical AOD, then an
$N_{l}\times M_{l}$ grid of diffracted beam spots will be output. This
limitation significantly limits the utility of crossed AODs for performing
arbitrary addressing of sites in a qubit array.

In addition to limitations in the addressing pattern, frequency shifts can
cause complications in addressing multiple qubit sites. As mentioned above,
when a beam is diffracted by an AOD, the diffracted light is shifted in
frequency by the AOD driving frequency. Since addressing multiple array sites
requires driving at least one axis of a 2D AOD with multiple frequencies, the
output beams will not all have the same frequency. This is problematic when
the optical beams are being used to drive resonant transitions, since the
detuning from the transition will change over the beam spot pattern. In
addition, a small amount of crosstalk between diffracted beams from optical
aberrations or scattering can have a large time-varying effect on the
intensity of the light addressing the qubits (see [5]).

While both SLMs and AODs individually are limited in their ability to address
qubits in a two-dimensional array, we introduce here an architecture that uses
both devices in conjunction, thereby enabling large-scale, rapidly
reconfigurable, and abitrary addressing of large qubit arrays. The techniques
described here are applicable to a variety of qubit technologies that are
controlled with light beams. These include qubits implemented in neutral
atoms, molecules, trapped ions, and semiconductor quantum dots.

Figure 1: Two configurations which combine acousto-optic deflectors (AOD) and
spatial light modulators. a) Configuration 1. A 2D AOD (AOD A) is used to
select different segments of a spatial light modulator (SLM). Each segment of
the spatial light modulator contains a different hologram corresponding to an
illumination pattern in the qubit array. A second AOD (AOD B) is used to
correct momentum shifts imparted by the first AOD. An upstream double-pass
acousto-optic modulator (AOM) is used for fast light beam modulation and
frequency control and compensation for other acousto-optic devices. This
double pass setup uses a polarizing beam splitter (PBS) and quarter waveplate
(QWP) to direct the light beam towards the AODs after passing through the AOM
twice. Fast transitions between the SLM partitions using the AODs allow an
effective increase in the average SLM reconfiguration rate. b) Configuration
2. The addition of a third AOD (AOD C) allows fast positioning of the image
created by the SLM relative to the qubit array. By including all required
addressing configurations in the SLM partition, this configuration can address
a large array with fast scanner transition times. Note that SLMs in
transmission mode are used in the diagrams; however, modifications for a
reflection mode SLM are straight forward, and only require an adjustment of
beam path.

##  2 Hybrid Scanner Description and Modeling

We propose to combine the fast deflection capabilities of AODs with the
arbitrary addressing and beam shaping capabilities of an SLM in a single
optical layout (see Fig. 1). This hybrid scanner uses an AOD to direct a beam
at different regions of the SLM; each of these different regions contains a
phase hologram which produces a distinct addressing pattern in the plane where
the qubit array is located. Since the AOD allows rapid switching between
different regions of the SLM, rapid transitions between addressing patterns
are possible. This rapid switching allows faster transitions between quantum
gate sets than using only a non-segmented SLM which has several benefits for
the operation of a quantum computer. More rapid transitions reduce the total
time needed for a quantum computation allowing a faster overall computation
improving the overall computer performance, since the quantum state degrades
over time due to finite $T_{1}$ and $T_{2}$ coherence times. Fast switching
times also enable certain quantum gate procedures that are not possible with
slow scanner transition times. For example, some previously demonstrated
2-qubit controlled phase gates on neutral atom qubits relied on very fast
scanner pointing transition times since some population was left in fragile,
highly excited Rydberg states between scanner transitions [14]. For these
gates $<1~{}\mu\rm s$ scanner transition times were needed to prevent
significant Rydberg decay and dephasing, more than 3 orders of magnitude
faster than an SLM. Details of the optical layout and SLM segmentation
strategy greatly affect the scanner performance. Below we detail two possible
strategies and provide estimations of the scanner performance in these
configurations. The first of these configurations allows global, arbitrary
addressing of the entire array with a moderate speed improvement. The second
configuration provides arbitrary addressing on a movable sub-array and allows
a much more dramatic speed increase at the cost of losing arbitrary addressing
over the entire qubit array.

Table 1:  If AOD B is not used to correct the k-vector shift imparted by AOD
A, then the beam position will be displaced on the high NA lens (see Fig. 1).
The maximum displacement, $D_{\rm max}$, will depend on the number of SLM
partitions, the ratio of the SLM partition size to the beam waist, $q_{\rm
SLM}$, and the waist of the beam at the high NA lens, $w_{\rm lens}$ (see eq.
(1)). The waist $w_{\rm lens}$ is constrained by the target waist size at the
atoms, $w_{\rm a}$, the focal length of the high NA lens, and the wavelength
of the light. Below, we calculate $D_{\rm max}$ for a number of configurations
where the wavelength is 459 nm, the focal length of the high NA lens is 23 mm,
and $q_{\rm SLM}=5$. For this configuration, we observe that AOD B is needed
to avoid beam clipping and coma even for a small number of SLM partitions and
moderate $w_{\rm a}$. Note that a lens with NA$=0.7$ and the given focal
length has a diameter of 45 mm. Beam displacement at high NA lens
---
SLM partitions | $w_{\rm a}~{}(\mu\rm m)$ | $w_{\rm lens}~{}\rm(mm)$ | $D_{\rm max}~{}\rm(mm)$
$2\times 2$ | $1.5$ | $2.25$ | $16$
$2\times 2$ | $3$ | $1.12$ | $8$
$15\times 15$ | $1.5$ | $2.25$ | $119$
$15\times 15$ | $3$ | $1.12$ | $59$

###  2.1 Configuration 1

The first hybrid AOD and SLM scanner configuration detailed in this paper is
composed of an SLM sandwiched by two 2D AODs (see Fig. 1). The first 2D AOD
(AOD A) directs the beam to one of several previously defined regions of the
SLM. The SLM regions each impart a spatially-varying phase on the optical
beam, shaping the beam to address the targeted array sites. The second 2D AOD
(AOD B) then compensates the deflection introduced by AOD A. The correction
provided by AOD B prevents clipping on the beam stop of the high numerical
aperture lens, which focuses the optical beam on the target array sites. If we
assume Gaussian optics, without AOD B, the maximum displacement, $D_{\rm
max}$, at the high numerical aperture lens will be equal to

$D_{\rm max}=q_{\rm SLM}w_{\rm lens}\frac{\sqrt{N_{x}^{2}+N_{y}^{2}}}{2},$ (1)

where $q_{\rm SLM}$ is the ratio of the SLM region size to the beam waist on
the SLM and $N_{x}$ ($N_{y}$) is the number of horizontal (vertical) SLM
partitions. The size of the waist at the atoms is determined by $w_{\rm
lens}$, the wavelength of the light, and the focal length of the high NA lens.
Table 1 lists maximum displacement values for various SLM partition and
focusing conditions. The $k$-vector correction also improves beam focus in the
qubit plane by reducing coma and polarization problems due to the light’s
$k$-vector being misaligned with respect to the optical axis. The other lenses
in the system transform the beam between image and Fourier conjugate planes of
the qubit array. When using a reflective SLM (or a transmission hologram with
a reflector), it is possible to simplify this setup to use only a single 2D
AOD with the addition of a Faraday rotator, half-wave plates, and polarizing
beam splitter (see Fig. 2). For clarity, we will describe the operation of
this scanner using the layout in Fig. 1, but similar analysis will also
describe the scanners in Fig. 2.

Figure 2: Simplified versions of a) Configuration 1 and b) Configuration 2
using a reflective spatial light modulator. The addition of a Faraday rotator,
half-wave plates, and a polarizing beam splitter allows the roles of acousto-
optic deflectors (AODs) A and B to be combined into a single 2D AOD (AOD A,B).

To calculate the performance of this hybrid AOD $+$ SLM scanner, the number of
addressable array sites and the number of SLM sub-regions must be considered.
These two quantities are jointly constrained by the AOD time-bandwidth
product, the SLM pixel resolution, and desired beam spot size in the qubit
array image plane. The parameters used in the analysis are summarized in Fig.
3. Assuming a Gaussian beam input into AOD A, the maximum number of hologram
segments which the SLM can be divided into is limited by the number of
resolvable spots ($N_{r}$) of AOD A

$N_{r}=\frac{\pi}{q_{\rm AOD,A}q_{\rm SLM}}TBW.$ (2)

Here $q_{\rm AOD,A}=L_{\rm AOD}/w_{\rm AOD,A}$ is the ratio of the length of
the active aperture of AOD A ($L_{\rm AOD}$) to the Gaussian beam waist in the
AOD ($w_{\rm AOD,A}$), $q_{\rm SLM}=L_{\rm SLM}/w_{\rm SLM}$ is the ratio of
the SLM segment size $L_{\rm SLM}$ to the beam waist size on the SLM ($w_{\rm
SLM}$), and $TBW=T_{\rm{AOD}}\Delta f$ is the time-bandwidth product
specification of the AOD, which is the time it takes for an acoustic wave to
propagate across the AOD’s active aperture ($T_{\rm{AOD}}$) multiplied by the
frequency bandwidth of the AOD ($\Delta f$).

Figure 3: A summary of experimental parameters used in the text. Gaussian beam
waist parameters, $w_{\rm AOD,A}$, $w_{\rm SLM}$, and $w_{\rm a}$ correspond
to the $1/e^{2}$ radius of the Gaussian beam intensity profile in the acousto-
optic deflectors (AODs), the spatial light modulator (SLM), and the qubit
array, respectively. Note that beam waists in AOD A and AOD B will be
identical, but the waist of the beam in AOD C in configuration 2 will be
different ($w_{AOD,C}$) and will depend on the lenses used. The length
parameters correspond to the AOD active aperture size ($L_{\rm AOD}$), the
size of each SLM patch ($L_{\rm SLM}$), and the distance between adjacent
qubits in the array plane ($L_{\rm a}$). Finally, $q_{\rm AOD,A}$, $q_{\rm
SLM}$, and $q_{\rm a}$ are ratios of the respective length ($L$) to the
corresponding beam waist ($w$).

Each segment of the SLM will have $n_{x}\times n_{y}$ pixels. For this
analysis, we use only $+1$ diffraction orders of the SLM to reduce crosstalk
onto unwanted target sites due to imperfect diffraction. To calculate the
qubit array dimension that each SLM section can address, we need to determine
how much displacement the SLM patch can generate in an image plane of the
qubit array relative to the beam waist in that same plane. For this analysis,
we can ignore the AODs and consider a simplified setup which just involves
illuminating the SLM patch with a collimated Gaussian beam, then focusing the
diffracted light on the qubit array plane with a lens (see Fig. 4). We
consider a beam with waist $w_{\rm SLM}$ incident on an SLM patch with length
$L_{\rm SLM}$. The SLM then applies a 1D phase tilt in the $x$-plane changing
the beams momentum. Focusing the beam with a lens gives a Gaussian spot at a
focal length $f$ away from the lens. This spot will be shifted from the
optical axis by an amount which depends on the focal length of the lens and
the wavefront tilt applied with the SLM. The angle (see Fig. 4)

$\theta\approx\frac{d}{L_{\rm SLM}}$ (3)

is the angular change that the SLM must induce to the wavefront in order to
shift the focus between two adjacent qubit sites in the image plane of the
lens. Since the beam propagates a focal distance from the lens to reach the
qubit array, after this propagation, the beam will be displaced by a distance
of

$L_{\rm a}\approx\theta f=\frac{fd}{L_{\rm SLM}},$ (4)

where $L_{\rm a}$ is the distance between neighboring qubit sites. If the SLM
applies $v$ full wave fringes across the SLM patch (i.e. the phase linearly
increases from $0$ to $v\times 2\pi$), then we can identify the total phase
shift over the aperture as

$\phi_{\rm tot}=\frac{2\pi d}{\lambda}=2\pi v,$ (5)

where $\lambda$ is the wavelength of the light. We can now relate $L_{\rm a}$
to the parameters of the Gaussian beam incident on the SLM, the SLM phase
mask, and the focal length of the following lens by solving for $d$ in eq. (5)
and substituting into eq. (4) yielding

$L_{\rm a}\approx\frac{v\lambda f}{L_{\rm SLM}}.$ (6)

Figure 4: A simplified spatial light modulator (SLM) scanner imaging system.
An SLM patch applies a phase tilt to an incoming collimated Gaussian beam with
waist $w_{\rm SLM}$. The beam diffracts at an angle $\theta$ relative to the
incoming beam based on the effective path length difference $d$ that is
applied over the SLM patch length, $L_{\rm SLM}$. A lens with focal length $f$
focuses the light onto the qubit array resulting in a Gaussian beam spot with
a waist $w_{\rm a}$ that is displaced by $L_{\rm a}$ from the optical axis.

For single-site addressing in the qubit array, we define an inter-site spacing
($L_{\rm a}$) to addressing beam waist ($w_{\rm a}$) ratio as $q_{\rm
a}=\frac{L_{\rm a}}{w_{\rm a}}$. We can relate $w_{\rm a}$ to the beam
parameters just after the SLM and lens system using well-known formulae for
the radius of a Gaussian beam assuming the beam waist is in the plane of the
qubit array

$w_{\rm SLM}=w(-f)=w_{\rm a}\sqrt{1+\left(\frac{-f}{z_{R}}\right)^{2}},$ (7)

where $z_{R}=\frac{\pi w_{\rm a}^{2}}{\lambda}$ is the Rayleigh range of the
beam at the qubit array. Assuming $\frac{f}{z_{R}}\gg 1$, we can solve for
$w_{a}$

$w_{\rm a}\approx\frac{f\lambda}{\pi w_{\rm SLM}}=\frac{f\lambda q_{\rm
SLM}}{\pi L_{\rm SLM}}.$ (8)

Now we can relate $q_{\rm a}$ to $v$ using eqs. (6,8) to get

$q_{\rm a}\approx\frac{v\lambda f}{L_{\rm SLM}}\frac{\pi L_{\rm SLM}}{\lambda
fq_{\rm SLM}}=\frac{\pi v}{q_{\rm SLM}}.$ (9)

The number of full $2\pi$ fringes the SLM needs to apply to the incident beam
to move one site in the image plane is then

$v\approx\frac{q_{a}q_{\rm SLM}}{\pi}.$ (10)

With $n_{x}$ pixels, we can apply a maximum number of fringes of $v_{\rm
max}=\frac{n_{x}}{2}$ by alternating between $0$ and $\pi$ phase shifts.
Dividing this by the number of fringes needed per site, we find that the
maximum number of sites that can be addressed along one dimension is

$N_{q,\rm max}=\frac{\pi n_{x}}{2q_{\rm a}q_{\rm SLM}}.$ (11)

We can apply the same analysis to the other spatial dimension, yielding, a
maximum addressable array size of $\frac{\pi n_{x}}{2q_{\rm a}q_{\rm
SLM}}\times\frac{\pi n_{y}}{2q_{\rm a}q_{\rm SLM}}$ sites that can be
addressed in the array plane.

Figure 5: Light beam parameters and dimensional constraints in acousto-optic
deflector AOD B which is used to correct the momentum shift that AOD A gives
to the optical beam. Diffraction due to the SLM will cause the light field in
AOD B to be different from AOD A, e.g the light image in AOD B might contain
multiple beam spots. We assume that the SLM is addressing an array of
$N_{q}\times N_{q}$ qubits with addressing beam waists of $w_{\rm a}$ and
qubit separations of $L_{\rm a}$. If the waist of each Gaussian beam in AOD B
is $w_{\rm AOD,A}$ (for simplicity, the waists in AOD A and B are taken to be
equal), then the magnification from AOD B to the qubit plane is $M_{\rm
a}=\frac{w_{\rm a}}{w_{\rm AOD,A}}$. If a distance of $2w_{a}$ is allowed
between the AOD aperture edge and the nearest beam center to minimize
clipping, then in order to fit the beam image inside the active aperture of
AOD B, eq. (12) must be satisfied.

For $q_{\rm SLM}=5$ and $q_{\rm a}=3$, we see that about $10\times 10$ pixels
are needed per site. However, the diffraction efficiency is reduced for SLM
patterns with a higher number of fringes over the SLM segment as shown in Sec.
3. This decreased efficiency is due to the effective blazing of the SLM
becoming less and less perfect as the fringe number approaches half the pixel
number. Additionally, for higher diffraction angles, multi-site addressing
without cross-talk, aberration correction, and beam shaping[15] are error-
prone and result in artifacts in the qubit array image plane. To reduce these
artifacts and improve the diffraction efficiency over the addressable array,
for $q_{a}=3$ and $q_{\rm SLM}=5$, we conservatively allow $20\times 20$
pixels per array site. Note, that it is not necessary for all SLM segments to
address the same set of array sites. By applying an additional static or
dynamic linear phase mask over each SLM segment, the portion of the qubit
array that each segment addresses may be shifted. While this allows a larger
array to be imaged, it reduces the number of times a particular site can be
addressed before the SLM must be reset.

For simplicity, we analyze the case where the entire array is addressed by
each hologram patch. The size of the array that can be addressed in this way
is ultimately limited by the active aperture of AOD B. This is because AOD B
is in an image plane of the qubit array, so a magnified image of the
addressing beams propagates through AOD B’s aperture. To be able to address
all sites in the $N_{q}\times N_{q}$ array without clipping on the AOD
aperture (here we set the Gaussian beam waists in AOD B and A the same
$(w_{\rm AOD,B}=w_{\rm AOD,A}$)

$L_{\rm{AOD}}\geq 4w_{\rm AOD,A}+(N_{q}-1)L_{\rm a}/M_{\rm a}=4w_{\rm
AOD,A}+q_{\rm a}w_{\rm AOD,A}(N_{q}-1),$ (12)

where $M_{\rm a}$ is the magnification of the image from AOD B to the qubit
array (see Fig. 5). Equivalently, this can be written as

$1\geq\frac{4+q_{\rm a}(N_{q}-1)}{q_{\rm AOD,A}}.$ (13)

Here we have assumed a square AOD aperture and allowed a $2w_{\rm AOD,A}$
buffer between the edge of the AOD active aperture and the center of the
nearest beam spot.

Table 2:  Some possible examples of SLM, AOD, and beam size settings for
configuration 1. For each example, the following quantities are listed in
columns left to right: the total qubit array size $N_{q}\times N_{q}$, number
of partitions into which the SLM is divided, the ratio of the beam waist in
AOD A (see Fig. 3) to the AOD crystal length ($q_{\rm AOD,A}$), the average
transition rate between different addressing patterns, and the burst rate
between SLM resets. Each of these settings is consistent with a $1000\times
1000$ pixel SLM, 2D AODs with $11.5~{}\mu$s transition time and time-bandwidth
product of TBW$=575$, SLM patch size to beam waist on the SLM ratio of $q_{\rm
SLM}=5$, and array spacing to beam waist ratio of $q_{a}=3$. Configuration 1
addressing examples
---
qubit array | SLM partitions | $q_{\rm AOD,A}$ | average transition rate | burst transition rate
$N_{q}\times N_{q}$ |  |  | $\left(10^{3}~{}\rm s^{-1}\right)$ | $\left(10^{3}~{}\rm s^{-1}\right)$
$7\times 7$ | $7\times 7$ | 52 | 39 | 181
$10\times 10$ | $5\times 5$ | 70 | 22 | 190
$25\times 25$ | $2\times 2$ | 180 | 4 | 198

With these constraints, we observe that there is a trade-off between array
size and number of partitions on the SLM. This translates to a trade-off
between array size and the effective addressing speedup because the speedup of
this configuration compared to using an SLM alone is related to the number of
partitions the SLM is divided into. Assuming each SLM patch is used once
before the SLM frame is reset, then the average time required to transition
between SLM configurations is

$T_{\rm ave}=\frac{1}{N_{x}N_{y}r_{\rm SLM}}+T_{\rm burst},$ (14)

where the SLM is divided into $N_{x}\times N_{y}$ patches, $r_{\rm SLM}$ is
the full frame transition rate of the SLM, and $T_{\rm burst}$ is the time
required for AODs A and B to transition between different patches on the SLM.
Note that while the average scanner transition rate $1/T_{\rm ave}$ is limited
primarily by the number of SLM partitions and the SLM refresh rate, AODs allow
much faster transitioning between segments on the SLM. The fast AOD
transitions enable a burst rate which can be sustained until the SLM needs to
be updated to address a new pattern of sites. Since multiple spots may be
present in AOD B’s aperture due to diffraction from the SLM, the time required
for the acoustic wave to traverse the entire image region in AOD B is greater
than or equal to the transition time of AOD A assuming the beam waist in AOD A
is the same as the beam waist of the spots in AOD B. Allowing the acoustic
wave time to travel at least $2w_{\rm AOD,A}$ from the center of each beam
spot, then an upper bound on the transition time ($T_{\rm{burst}}$) between
these SLM partitions is

$T_{\rm{burst}}\leq\frac{4w_{\rm AOD}+L_{\rm a}N_{q}}{v_{\rm
a}}=\frac{T_{\rm{AOD}}(4+q_{\rm a}N_{q})}{q_{\rm AOD,A}},$ (15)

where $v_{\rm a}$ is the acoustic wave velocity in the AOD crystal. The burst
rate is then $1/T_{\rm{burst}}$. Table 2 lists some possible configurations
assuming SLM and AOD parameters that are currently commercially available.
This first configuration allows a significant speed-up over an SLM alone.
Furthermore, because arbitrary addressing of the target regions can be
achieved using each region of the SLM, gates can be operated in parallel over
the qubit array.

###  2.2 Configuration 2

The addition of a third 2D AOD (AOD C) to the scanner allows for greatly
increased size of the addressable array and the average transition frequency,
but comes at the expense of completely arbitrary addressing over the full
array. This is made possible by setting the various SLM segments to address
different combinations of sites within a small sub-array of sites using the
same optical layout as described in configuration 1 of Fig. 1. The addition of
the final 2D AOD in configuration 2 of Fig. 1 allows this sub-array to be
moved around a larger optical array. Note, as mentioned in the last section,
it is possible to combine the roles of AODs A and B into a single 2D AOD (see
Fig. 2); however, as in the last section, we analyze the configuration shown
in Fig. 1 for simplicity.

Figure 6:  An example of segmenting a SLM into multiple partitions for
addressing a $3\times 3$ sub-array for use in configuration 2. In
configuration 2, a third 2D acousto-optic deflector is used to position the
SLM hologram images with respect to the qubit array. To address any single
qubit in a $3\times 3$ sub-array, only 1 hologram patch is needed. Any two
qubits in the sub-array can be addressed with the next 12 SLM configurations.
Equation (16) gives the number of SLM combinations required to simultaneously
address $k$ qubits in an $m_{s}\times n_{s}$ sub-array.

Configuration 2 has many benefits. If holograms for all addressing
combinations required for a quantum computation can be represented by a single
SLM frame (see Fig. 6), then the SLM will not need to be reset during the
computation. The number of SLM patches needed to arbitrarily address $k$
qubits in a $m_{s}\times n_{s}$ sub array can be calculated from the
combinatorial formula for putting $k$ identical particles in $m_{s}\times
n_{s}$ boxes, $\frac{(m_{s}n_{s})!}{k!(m_{s}n_{s}-k)!}$. However, since AOD C
may be used to position the sub array, this formula over-counts the number of
required configurations. Any two patterns which differ only by a translation
can be represented by a single SLM patch and two AOD C settings. Without loss
of generality, we quantify these patterns by counting only combinations which
contain at least one spot in the left-most column and one spot in the top-most
row, since any addressing pattern may be translated to satisfy this
requirement. We can then subtract off combinations which do not meet the row
criterion ($\frac{[(m_{s}-1)n_{s}]!}{k![(m_{s}-1)n_{s}-k]!}$ combinations) and
also the combinations where the column criterion is not met
($\frac{[m_{s}(n_{s}-1)]!}{k![m_{s}(n_{s}-1)-k]!}$ combinations). This
subtraction double counts the combinations where both row and column criteria
are not satisfied, so these
($\frac{[(m_{s}-1)(n_{s}-1)]!}{k![(m_{s}-1)(n_{s}-1)-k]!}$ combinations) must
be added back. This results in the total number of SLM patches ($P$) needed to
simultaneously address any combination of $k$ sites in a $m_{s}\times n_{s}$
sub array as

$\displaystyle P(m_{s},n_{s},k)$ $\displaystyle=$
$\displaystyle\frac{(m_{s}n_{s})!}{k!(m_{s}n_{s}-k)!}-\frac{[(m_{s}-1)n_{s}]!}{k![(m_{s}-1)n_{s}-k]!}$
(16) $\displaystyle-$
$\displaystyle\frac{[m_{s}(n_{s}-1)]!}{k![m_{s}(n_{s}-1)-k]!}+\frac{[(m_{s}-1)(n_{s}-1)]!}{k![(m_{s}-1)(n_{s}-1)-k]!}.$

Table 3:  SLM patterns for different qubit addressing patterns in
configuration 2. In configuration 2, the diffracted pattern from the SLM can
be translated with respect to the array using AOD C. With this degree of
freedom, the SLM only needs to address a sub-region to address the full qubit
array. The number of SLM patches needed for arbitrary addressing of this sub-
region depends on the dimensions of the sub-region ($m_{s}\times n_{s}$) and
the maximum number of qubit sites to be simultaneously addressed, $k_{\rm
max}$. The total number of SLM patches needed to arbitrarily address any
combination of sites up to $k_{\rm max}$ sites simultaneously in the sub-
region is then equal to $P_{\rm tot}(m_{s},n_{s},k_{\rm max})$.  Configuration
2 SLM partitions
---
addressed qubit sub-region | simultaneously addressed sites | unique configurations
$m_{s}\times n_{s}$ | $k_{\rm max}$ | $P_{\rm tot}(m_{s},n_{s},k_{\rm max})$
$3\times 3$ | 2 | 13
$3\times 3$ | 3 | 61
$3\times 3$ | 4 | 158
$4\times 4$ | 2 | 25
$4\times 4$ | 3 | 229
$5\times 5$ | 2 | 41
$5\times 5$ | 3 | 621

The number of partitions needed to address every sub-array combination for up
to $k_{\rm max}$ simultaneous beams is then:

$P_{\rm tot}(m_{s},n_{s},k_{\rm max})=\sum_{k=1}^{k_{\rm
max}}P(m_{s},n_{s},k).$ (17)

Alternatively, one could include SLM patch optimization in the compilation
step of the quantum computation. This way, SLM patches which optimize gate
parallelism in the quantum computation could be chosen.

In the case where SLM patches do not need to be reset during the calculation,
the transition time between quantum gates will only be limited by the rise
time of the three AODs, and the average transition rate will be equal to the
burst transition rate. Dimensions of the qubit array $N_{q}\times N_{q}$ that
can be addressed can be much larger than the dimensions of the sub-array that
is addressed by the SLM patches ($m_{s}\times n_{s}$ sites). The dimension
$N_{q}$ is limited by the properties of AOD C, the light field entering the
AOD, and the dimensions of the qubit array being addressed. Assuming Gaussian
inputs, then the size of the addressable array is

$N_{q}=\frac{\pi}{q_{\rm AOD,C}q_{\rm a}}TBW,$ (18)

where $q_{\rm AOD,C}$ is the ratio of the AOD C’s active aperture length to
the beam waist in AOD C and both $q_{\rm a}$ and $TBW$ are defined in the same
way as in the previous subsection (this analysis assumes that all three 2D
AODs are the same model, though this need not be the case). Note that $q_{\rm
AOD,C}$ can be very different from $q_{\rm AOD,A}$ since the corresponding
beam waists are in conjugate Fourier planes. This difference results in the
effective switching speed of the AODs being different. The transition time
needed for AOD B is larger than or equal to that of AOD A, so the transition
time of the scanner is equal to the greater of the transition times of AOD B
and AOD C

$T_{\rm{transition}}=\max\left(\frac{T_{\rm AOD,B}(4+q_{\rm a}N_{q})}{q_{\rm
AOD,A}},\frac{4T_{\rm AOD,C}}{q_{\rm AOD,C}}\right).$ (19)

Depending on the size of the qubit array being addressed in each of the two
configurations and the number of SLM partitions, the scanner transition time
for configuration 2 might be slower than the burst transition time for
configuration 1. However, the average transition time will typically be faster
for configuration 2 since the SLM does not need to be reset. Table 4 details
the configuration 2 scanner performance given various scanner parameters. The
values in this table were calculated for a $1000\times 1000$ pixel SLM,
however, higher resolution 4k ($4160\times 2464$) SLMs are available
commercially, and 8k ($8192\times 4320$) pixel prototypes have been
demonstrated [16]. These higher resolution SLMs would allow for
correspondingly larger sub-array addressing and/or more complete addressing
combinations.

Table 4: Some possible examples of SLM and beam size settings for
configuration 2. For each example, the following quantities are listed in
columns left to right: the total qubit array size, number of partitions into
which the SLM is divided, the dimensions of the sub-array that each SLM patch
addresses, the maximum simultaneous addressing number $k_{\rm max}$ for which
$P_{\rm tot}$ (see eq. (17)) is less than or equal to the number of SLM
partitions, the ratio of the beam waist in AOD A (see Fig. 1) to the AOD
active aperture length ($q_{\rm AOD,A}$), the ratio of beam waist in AOD C to
the active aperture length ($q_{\rm AOD,C}$), and the average transition rate
between different addressing patterns. Note that in the last two rows, $k_{\rm
max}$ is 2, but more than half of the 3 beam combinations could be included in
the SLM partitions. Each of these settings is consistent with a $1000\times
1000$ pixel SLM, 2D AODs with $11.5~{}\mu$s transition time, $TBW=575$, SLM
patch size to beam waist on the SLM ratio $q_{\rm SLM}=5$, and a array spacing
to beam waist ratio of $q_{\rm a}=3$. Configuration 2 addressing examples
---
array size | SLM | sub-array | $k_{\rm max}$ | $q_{\rm AOD,A}$ | $q_{\rm AOD,C}$ | transition rate
$N_{q}\times N_{q}$ | partitions | size |  |  |  | $\left(10^{3}~{}\rm s^{-1}\right)$
$20\times 20=400$ | $4\times 4$ | $3\times 3$ | 2 | 90 | 30 | 650
$40\times 40=1600$ | $8\times 8$ | $3\times 3$ | 3 | 45 | 15 | 325
$67\times 67=4489$ | $13\times 13$ | $3\times 3$ | 4 | 27 | 9 | 195
$30\times 30=900$ | $5\times 5$ | $4\times 4$ | 2 | 72 | 20 | 416
$75\times 75=5625$ | $12\times 12$ | $4\times 4$ | $2+$ | 30 | 8 | 173
$167\times 167=27889$ | $12\times 12$ | $4\times 4$ | $2+$ | 30 | 3.6 | 78
Figure 7:  By driving the final acousto-optic deflector (AOD) of configuration
2 (see Fig. 1) with multiple frequencies, it is possible to duplicate an image
in the qubit array region. Each column (row) corresponds to a particular AOD
frequency for the $x$ ($y$) axes of a 2D AOD.

Since a single SLM only addresses a small section of the qubit array in
configuration 2, it is not possible to perform completely arbitrary array
addressing with configuration 2. However, it is possible to duplicate the
image pattern created by the SLM in multiple regions of the qubit array by
driving AOD C with multiple frequency tones (see Fig. 7). While this multi-
frequency driving does allow some addressing flexibility, it is limited
because each axis of a 2D AOD can only provide momentum changes of an incident
beam along the corresponding axis. By driving that axis with multiple
frequencies, an incident beam can be split since each acoustic wave frequency
diffracts the beam by a different amount; however, the momentum shifts are all
in the same direction. The resulting image will be duplicated by
$N_{f_{x}}\times N_{f_{y}}$ times, where $N_{f_{x}}$ ($N_{f_{y}}$) corresponds
to the number of $x$ ($y$) frequencies that the AOD axes are driven by.

Furthermore, as mentioned above, the frequency of a beam diffracted by an
acoustic wave is shifted by the acoustic wave frequency times the diffraction
order. So the multiple images made by diffracting a beam with multiple
acoustic wave frequencies will each receive a different frequency shift. When
the resulting images are used, e.g., to drive atomic transitions, the various
diffraction orders corresponding to the different acoustic wave frequencies
will be detuned from the transition by different amounts. In some types of
quantum gates, this relatively small frequency shift does not matter (e.g.
${\sf R}_{z}$ gates executed using differential Stark shifts on the qubit
states [14], Raman gates with several GHz detuning [17], or gates using sub-
picosecond laser pulses [18]). Other quantum gates using resonant transitions
might be affected by this detuning and will require additional addressing
constraints or compensation strategies. For example, when driving two-photon
transitions (each wavelength with its own scanner), then frequency shifts can
be effectively compensated by having the frequency of the first and second
photons of the transition being shifted by equal magnitudes but opposite signs
[5]. Despite such limitations, the multi-tone operation is particularly useful
for situations when identical operations need to be performed in several sub-
regions over the array. Such situations arise during initialization and
syndrome measurement in logical qubits. Using multi-tone operation of AOD C,
such operations can be performed in parallel, greatly saving operation time.

##  3 Hologram Simulations

In the previous sections, we described the hybrid scanner in two different
configurations. Here, we will show that these proposed configurations provide
satisfactory performance even with the simplest hologram generation method
which does not require iterative algorithms. The implementation of iterative
algorithms might improve fidelity of the light field at the qubits at the cost
of reduced efficiency and slower computation times. In general, when it comes
to arbitrary beam shaping, it is necessary to have a large number of SLM
pixels to precisely modulate the beam profile. Often, it also requires an
advanced algorithm to gain high fidelity of the desired pattern, but it comes
with the cost of losing power that should go to the target region. This is not
desirable because it will limit not only the diffraction efficiency but also
sacrifice the number of different hologram patterns that can be simultaneously
displayed in one frame.

In the application to qubit addressing it is not always necessary to impose
the requirement of beam reshaping on the holograms. In particular, when the
shape of the input beam and the desired output beam are the same, or very
similar, the hologram only has to deflect the input beam into single or
multiple target sites within the target array. Using this mechanism, the
hologram can be easily generated by calculating the phase difference between
the desired output field back-propagated to the SLM plane,
$\mathcal{F}^{-1}\left(E_{\rm out}\right)$, and the input field in the SLM
plane, $\mathcal{F}\left(E_{\rm in}\right)$. The required phase is

$\phi=\text{mod [arg}[\mathcal{F}^{-1}\left(E_{\rm
out}\right)-\mathcal{F}\left(E_{\rm in}\right),2\pi]$ (20)

where $E_{\rm in}$ is the input field, $E_{\rm out}$, is the field of the
desired output pattern, $\mathcal{F}=$ Fourier Transform, and
$\mathcal{F}^{-1}$ = inverse Fourier Transform.

Using this method we simulated the SLM performance for two different beam
shapes: Gaussian and square flattop beams as shown in Fig. 8. The flattop beam
has benefits over a Gaussian beam in qubit addressing because it not only
reduces the crosstalk to neighboring sites but also the sensitivity of gate
fidelity to optical misalignment[19]. It can be incorporated in the hybrid
scanner architecture by using an additional flattop generator to shape the
beam prior to passing through AOD A.

The simulations were done in Matlab based on Fourier analysis within the
paraxial approximation, using a simulation array with $2^{13}\times 2^{13}$
pixels. Each SLM pixel is represented by 5 simulation pixels which allow other
diffraction orders to show up in the output plane and therefore give an
accurate value for the diffraction efficiency at the desired target region.
The SLM is assumed to have 10 bits of phase resolution and the input beam
illuminates the SLM normal to its surface, neglecting any angle shift. The
finite fill factor of a real SLM was neglected when calculating diffraction
efficiencies. In this simulation, We also assume aberration-free optics and a
single polarization optical field, so the experimental results might slightly
vary from the theoretical results presented in the paper. More detailed
analysis and improvements to the results can be made by incorporating the full
Helmholtz propagation.

Figure 8: Simulation results using Gaussian or square flattop beams as the
target outputs $q_{SLM}=5$ and $q_{\rm a}=3$ to address up to 4 target
locations in a $4\times 4$ array. a) Diffraction efficiency vs. number of SLM
pixels per axis for Gaussian beams. c) Diffraction efficiency for flattop
beams. b) Accuracy for Gaussian beams. d) Accuracy for flattop beams. The
accuracy is the average for the number of targets used. The insets show the
generated patterns as well as the one-dimensional intensity profiles of the
target and simulated output for the beam in the lower right corner of the
array using 64 SLM pixels per axis with the target intensity outside the
target region set to zero.

In order to analyze the performance of the hybrid scanner, it is crucial to
know how many pixels per SLM partition are needed to accurately address an
$N_{q}\times N_{q}$ target array, while maintaining both the diffraction
efficiency and the accuracy at a sufficient level. Using the simple method of
eq. (20) we analyze the number of SLM pixels needed for simultaneous
addressing of up to 4 target sites in a $4\times 4$ array. To quantify the
performance two metrics, diffraction efficiency $\eta$, and accuracy
$\epsilon$, are used for the analysis and are defined as

$\displaystyle\eta$ $\displaystyle=$ $\displaystyle\frac{\text{total power in
the target sites}}{\text{total input power on the SLM}}$ (21)
$\displaystyle\epsilon$ $\displaystyle=$
$\displaystyle\sqrt{\frac{1}{N_{\chi}}\sum_{(x,y)\in\chi}\left(\frac{I_{\rm
out}(x,y)-I_{\rm t}(x,y)}{I_{\rm t}(x,y)}\right)^{2}}$ (22)

where $\chi$ is the region covering the $4\times 4$ array of target sites in
the output plane and $N_{\chi}$ is the number of points at which the output is
sampled [20]. Here, the output intensity $I_{\rm out}$ and target intensity
$I_{\rm t}$ are normalized to have the same power in each target site. The
points where $I_{\rm t}$ is smaller than $1/100$ of its maximum were omitted
to avoid sensitivity to the edges of the beams when calculating $\epsilon$.

The simulations in Fig. 8 are relevant for a $1000\times 1000$ pixel SLM that
is used in configuration 2 (see Sec. 2.2). As shown in Table 3 all possible
configurations of simultaneously addressing up to 3 sites in a $4\times 4$
sub-array requires 229 SLM partitions. Using an SLM with $1000\times 1000$
pixels each SLM partition can have $66\times 66$ pixels. Using this number of
pixels we achieve $\eta\approx 60\%$ of total diffraction efficiency and
accuracy $\epsilon\approx 0.05$. Less than $0.5\%$ of the total input power
went to the untargeted sites within the target array and the rest of the
missing power was distributed outside the target array. The results shown in
the insets of Fig. 8 used 64 SLM pixels per axis to address a $4\times 4$
array which corresponds to $16\times 16$ pixels per array site in good
agreement with the conservative estimate of $2N_{q,\rm max}\times 2N_{q,\rm
max}=20\times 20$ pixels per array site as discussed below eq. (11).
Increasing the number of pixels to $80\times 80$ ($20\times 20$ per array
site) we reach a diffraction efficiency of $\eta\approx 70\%$ when targeting a
single site, and a few percent lower when targeting up to 4 sites. It is also
possible to use more sophisticated hologram design methods such as Gerchberg-
Saxton[21] or the MRAF algorithm of [20]. These algorithms can achieve higher
accuracy at the expense of lower diffraction efficiency. The results presented
here verify the pixel requirements estimated in eq. (11), while ultimate
performance limits will depend on the specific hologram design methodology
employed.

##  4 Conclusions

In this paper, we described and analyzed the performance of two optical beam
scanner architectures designed to provide fast quantum gate operations for
future generations of optically addressed qubit arrays. These scanners combine
the arbitrary addressing of an SLM with the fast deflection capabilities of an
AOD to provide site-selective quantum gates. The first of these configurations
allows completely arbitrary site addressing of medium sized qubit arrays with
a moderate transition rate between qubit gates. Completely arbitrary
addressing allows parallel gates over the entire qubit array, but in this
configuration there is a competition between average scanner transition rate
(limited by the number of SLM partitions and the SLM transition rate) and the
number of addressable sites in the array (limited by the number of pixels per
SLM partition). Despite these trade-offs, we calculate a 100-site qubit array
could be arbitrarily addressed with an average repetition rate of $22\times
10^{3}~{}\rm s^{-1}$, a factor of 22 times speed-up over using an SLM alone.

In the second configuration, the scanner is configured such that the SLM only
provides arbitrary addressing on a sub-array of the qubit array and an
additional AOD is added to allow scanning over the entire qubit array. In this
second configuration, arbitrary addressing on the full qubit array is
sacrificed for faster transition speeds and larger array sizes. With strategic
SLM partitioning, this scanner enables fast addressing of large qubit arrays
with arbitrary addressing on a movable sub-array within the qubit array. We
show how to address a large array with more than 25,000 sites with limited
multi-site simultaneous addressing at a transition rate of $78\times
10^{3}~{}\rm s^{-1}$, a factor of 78 times the rate using an SLM alone.
Limited parallel addressing of the entire array could be achieved by driving
the final AOD with multiple frequencies. Both of the scanner configurations
can leverage the SLM for aberration correction and beam focus shaping to
provide more optimal illumination patterns on targeted qubits, as is verified
by numerical simulation of SLM phase holograms. These features combined will
enable high fidelity, fast, and parallel gate operations in optically
addressed qubit arrays.

During revision of the paper we became aware of a patent [22] related to the
architecture presented here. The patent uses a fast switch to select different
regions of a segmented SLM. This patent did not include $\bf k$-vector
compensation in the atom plane nor the idea of scanning a sub-array relative
to the full qubit array as is used in configuration 2.

##  5 Acknowledgement

This material is based on work supported by NSF Award 2016136 for the QLCI
center Hybrid Quantum Architectures and Networks, the U.S. Department of
Energy Office of Science National Quantum Information Science Research
Centers, and NSF Award 2210437.

Disclosure: M. Saffman is a part time employee and equity holder in
Infleqtion, Inc. .

## References

  * [1] M. Saffman, “Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges,” J. Phys. B 49, 202001 (2016).
  * [2] D. Kim, A. Keesling, A. Omran, H. Levine, H. Bernien, M. Greiner, M. D. Lukin, and D. R. Englund, “Large-scale uniform optical focus array generation with a phase spatial light modulator,” Opt. Lett. 44, 3178–3181 (2019).
  * [3] P. Huft, Y. Song, T. M. Graham, K. Jooya, S. Deshpande, C. Fang, M. Kats, and M. Saffman, “Simple, passive design for large optical trap arrays for single atoms,” Phys. Rev. A 105, 063111 (2022).
  * [4] K.-N. Schymik, B. Ximenez, E. Bloch, D. Dreon, A. Signoles, F. Nogrette, D. Barredo, A. Browaeys, and T. Lahaye, “In situ equalization of single-atom loading in large-scale optical tweezer arrays,” Phys. Rev. A 106, 022611 (2022).
  * [5] T. M. Graham, Y. Song, J. Scott, C. Poole, L. Phuttitarn, K. Jooya, P. Eichler, X. Jiang, A. Marra, B. Grinkemeyer, M. Kwon, M. Ebert, J. Cherek, M. T. Lichtman, M. Gillette, J. Gilbert, D. Bowman, T. Ballance, C. Campbell, E. D. Dahl, O. Crawford, N. S. Blunt, B. Rogers, T. Noel, and M. Saffman, “Multi-qubit entanglement and algorithms on a neutral-atom quantum computer,” Nature 604, 457–462 (2022).
  * [6] P. Bechtold, R. Hohenstein, and M. Schmidt, “Evaluation of disparate laser beam deflection technologies by means of number and rate of resolvable spots,” Opt. Lett. 38, 2934 (2013).
  * [7] G. R. B. E. Römer and P. Bechtold, “Electro-optic and acousto-optic laser beam scanners,” Phys. Procedia 56, 29 (2014).
  * [8] S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Semeghini, A. Omran, D. Bluvstein, R. Samajdar, H. Pichler, W. W. Ho, S. Choi, S. Sachdev, M. Greiner, V. Vuletić, and M. D. Lukin, “Quantum phases of matter on a 256-atom programmable quantum simulator,” Nature 595, 227–232 (2021).
  * [9] R. W. Bowman, A. J. Wright, and M. J. Padgett, “An SLM-based Shack-Hartmann wavefront sensor for aberration correction in optical tweezers,” J. Opt. 12, 124004 (2010).
  * [10] F. Nogrette, H. Labuhn, S. Ravets, D. Barredo, L. Béguin, A. Vernier, T. Lahaye, and A. Browaeys, “Single-atom trapping in holographic 2D arrays of microtraps with arbitrary geometries,” Phys. Rev. X 4, 021034 (2014).
  * [11] C.-Y. Shih, S. Motlakunta, N. Kotibhaskar, M. Sajjan, R. Hablützel, and R. Islam, “Reprogrammable and high-precision holographic optical addressing of trapped ions for scalable quantum control,” npj Qu. Inf. 7, 57 (2021).
  * [12] S. Turataev, I. T. Leite, K. J. MIitchell, M. J. Padgett, D. B. Phillips, and T. Čižmár, “Comparison of nematic liquid-crystal and DMD based spatial light modulation in complex photonics,” Opt. Expr. 25, 29874 (2017).
  * [13] F. Schmidt-Kaler, H. Häffner, S. Gulde, M. Riebe, G. P. T. Lancaster, T. Deuschle, C. Becher, W. Hänsel, J. Eschner, C. F. Roos, and R. Blatt, “How to realize a universal quantum gate with trapped ions,” Appl. Phys. B 77, 789 (2003).
  * [14] T. Graham, M. Kwon, B. Grinkemeyer, A. Marra, X. Jiang, M. Lichtman, Y. Sun, M. Ebert, and M. Saffman, “Rydberg mediated entanglement in a two-dimensional neutral atom qubit array,” Phys. Rev. Lett. 123, 230501 (2019).
  * [15] K. Gillen-Christandl, G. Gillen, M. J. Piotrowicz, and M. Saffman, “Comparison of Gaussian and super Gaussian laser beams for addressing atomic qubits,” Appl. Phys. B 122, 131 (2016).
  * [16] G. Lazarev, A. Hermerschmidt, S. Krüger, and S. Osten, “LCOS spatial light modulators : Trends and applications,” Optical Imaging and Metrology: Advanced Technologies (2012).
  * [17] D. D. Yavuz, P. B. Kulatunga, E. Urban, T. A. Johnson, N. Proite, T. Henage, T. G. Walker, and M. Saffman, “Fast ground state manipulation of neutral atoms in microscopic optical traps,” Phys. Rev. Lett. 96, 063001 (2006).
  * [18] Y. Song, H.-g. Lee, H. Kim, H. Jo, and J. Ahn, “Subpicosecond ${X}$ rotations of atomic clock states,” Phys. Rev. A 97, 052322 (2018).
  * [19] K. Gillen-Christandl and G. D. Gillen, “Projection of diffraction patterns for use in cold-neutral-atom trapping,” Phys. Rev. A 82, 063420 (2010).
  * [20] M. Pasienski and B. DeMarco, “A high-accuracy algorithm for designing arbitrary holographic atom traps,” Opt. Express 16 (2008).
  * [21] R. W. Gerchberg and W. O. Saxton, “A practical algorithm for the determination of phase from image and diffraction plane pictures,” Optik 35 (1972).
  * [22] D. Kim and D. R. Englund, “Optical holographic addressing of atomic quantum bits,” U. S. Patent 11,120,360 B2 (2021).