./images/

# Quantum JPEG

Simone Roncallo  0000-0003-3506-9027<EMAIL_ADDRESS>Dipartimento di Fisica, Università degli Studi di Pavia, Via Agostino Bassi 6,
I-27100, Pavia, Italy  INFN Sezione di Pavia, Via Agostino Bassi 6, I-27100,
Pavia, Italy  Lorenzo Maccone  0000-0002-6729-5312<EMAIL_ADDRESS>Dipartimento di Fisica, Università degli Studi di Pavia, Via Agostino Bassi 6,
I-27100, Pavia, Italy  INFN Sezione di Pavia, Via Agostino Bassi 6, I-27100,
Pavia, Italy  Chiara Macchiavello  0000-0002-2955-8759
<EMAIL_ADDRESS>Dipartimento di Fisica, Università degli Studi di
Pavia, Via Agostino Bassi 6, I-27100, Pavia, Italy  INFN Sezione di Pavia, Via
Agostino Bassi 6, I-27100, Pavia, Italy

###### Abstract

The JPEG algorithm compresses a digital image by filtering its high spatial-
frequency components. Similarly, we introduce a quantum protocol that uses the
quantum Fourier transform to discard the high-frequency qubits of an image,
downsampling it to a lower resolution. This allows to capture, compress and
send images even with limited quantum resources for storage and communication.
We show under which conditions this protocol is advantageous with respect to
its classical counterpart.

Quantum image processing; Quantum image downsampling; Quantum image
compression; Quantum image communication;

##  I Introduction

Digital images represent information in terms of arrays of pixels. Compression
and downsampling can reduce the cost for data storage and transmission, while
preserving the original visual pattern [1]. An example is the joint
photographic expert group (JPEG) algorithm [2], which operates in the spatial-
frequency domain. The JPEG algorithm divides the input image into smaller
subimages, then taking the discrete cosine transform of each element. The high
spatial frequencies are removed, reducing the amount of information stored at
the cost of the quality of the output image.

Quantum image processing seeks to encode, manipulate, and retrieve visual
information in a quantum-mechanical way [3, 4, 5, 6, 7, 8, 9]. In this paper,
we discuss the downsampling and compression of images encoded as multiqubit
quantum states. Using the quantum Fourier transform ($\operatorname{QFT}$)
[10, 11], we provide an algorithm to discard the most significant qubits in
the encoding register, thus filtering the high spatial-frequency components of
the input image. This algorithm preserves the original visual pattern,
downscaling its resolution to reduce the number of encoding resources in the
register (see Fig. 1). Our implementation differs from [12, 13, 14] in both
the encoding strategy and the algorithm used. It also differs from [15] (which
appeared at the same time as the current paper) in both the algorithm and its
purpose, although it uses the same encoding. By taking into account the
statistical reconstruction at the output, we show that our algorithm is
advantageous over its classical counterpart, as long as the output resolution
is sufficiently compressed. As a possible hardware implementation of the
encoding register, we consider a multiatom lattice sensor that captures the
image by electromagnetically interacting with a multimode coherent state. In a
generic scenario, combining the algorithm and the encoder allows two users to
capture and transmit images by reducing the communication cost, as well as the
dimension of the channel with respect to the initial image size.

Figure 1: Compression by downsampling a $4\times 4$ image into a $2\times 2$
image. The input is encoded in the probabilities of a $n_{0}=4$ qubits state
$\ket{\Psi}_{0}$, i.e. $p_{abcd}=|\bra{abcd}\ket{\Psi}_{0}|^{2}$ with
$a,b,c,d=0,1$. Alg. 1 compresses $\ket{\Psi}_{0}$ into the $n_{2}=2$ qubits
state $\rho_{2}$, yielding the output image from the Born rule
$q_{ab}=\Tr(\ket{ab}\\!\bra{ab}\rho_{2})$.

##  II Quantum image downsampling and compression

In this section we discuss the quantum downsampling and compression algorithm.
We vectorize and encode the image in the probabilities of a state loaded in
the $n_{0}$-register, i.e. a register of $n_{0}$ qubits. After a
$\operatorname{QFT}$, we trace out the qubits that correspond to the high
spatial-frequency components of the image. Then, we return to the
computational basis with the inverse $\operatorname{QFT}$
($\operatorname{QFT^{\dagger}}$), discarding the redundant qubits and
compressing the image in the $n_{2}$-register, i.e. a register of
$n_{2}<n_{0}$ qubits. We discuss the relation between the downsampling factor,
i.e. the number of discarded qubits $n_{2}-n_{0}$, and the loss in the output
resolution.

A digital grayscale image is a grid of elements called _pixels_. Each pixel is
associated to a finite and discrete quantity called _grey value_ , which
represents the brightness reproduced at each point of the grid (for coloured
images, there are three brightness values, one for each of the red, green and
blue channels). Classically, each pixel value is encoded in a string of $c$
bits which determines the total number of $L=2^{c}$ _grey levels_ of the
image, namely the depth. Mathematically, an image is described by a matrix
$\mathscr{I}$, with the size $N\times M$ representing its _resolution_ and
$NM$ the total number of pixels. For simplicity we consider only square
images, i.e. with $N=M$.

We represent $\mathscr{I}$ as a $n_{0}$-qubit quantum state,

$\displaystyle\ket{\Psi}_{0}=\sum_{j=0}^{{2}^{{n}_{0}}-1}\sqrt{\theta(\mathscr{I}^{\prime})_{j}}\ket{j}_{0}\
,$ (1)

where $\ket{j}_{0}$ labels the elements of the computational basis on the
$n_{0}$-qubit Hilbert space $\mathcal{H}_{0}$ and $\theta$ is a row-wise111The
choice of the vectorization path is conventional, as long as it is respected
throughout the algorithm. vectorization map that associates a $N\times N$
matrix to the $N^{2}$ column vector

$\theta(\mathscr{I})=\left[\mathscr{I}_{00},\ldots,\mathscr{I}_{0(N-1)},\mathscr{I}_{10},\ldots,\mathscr{I}_{(N-1)(N-1)}\right]^{T}\
.$ (2)

We call $\ket{\Psi}_{0}$ quantum image. In our notation, states or operations
with subscript $0$ are referred to the $n_{0}$-register. This representation
encodes the grey value of $N^{2}$ pixels in the probabilities of
$n_{0}=2\log_{2}(N)$ qubits, whose normalization follows by rescaling each
pixel value to the total brightness of the image, so that
$\mathscr{I}^{\prime}=\mathscr{I}/\sum_{m,n=0}^{N-1}\mathscr{I}_{mn}$. This
strategy yields a first lossless exponential compression of the image: from
$N^{2}$ pixels to $n_{0}$ qubits. Below, we process the quantum image to
further reduce the size of the encoding register.

The $\operatorname{QFT}$ operates on the $n_{0}$-register as

$U_{\operatorname{QFT}_{0}}\ket{j}_{0}=\frac{1}{N}\sum_{k=0}^{N^{2}-1}e^{2\pi
ijk/N^{2}}\ket{k}_{0}\ .$ (3)

We use the subscript notation to specify the register on which the
$\operatorname{QFT}$ operates. Consider the $n_{1}$-subregister made only of
the first $n_{1}=n_{0}-\tilde{n}$ qubits of $\mathcal{H}_{0}$ and let
$\ket{j}_{1}$ label the elements of its computational basis. Then
$\ket{j}_{0}=\ket{l}_{\tilde{n}}\otimes\ket{m}_{1}$, with
$\ket{l}_{\tilde{n}}$ defined on the $\tilde{n}$-register. The inverse
$\operatorname{QFT}$ operates naturally on the $n_{1}$-subregister as
$(\mathds{1}\otimes
U^{\dagger}_{\operatorname{QFT}_{1}})\ket{j}_{0}=\ket{l}_{\tilde{n}}\otimes
U^{\dagger}_{\operatorname{QFT}_{1}}\ket{m}_{1}$.

Our algorithm downsamples a quantum image $\ket{\Psi}_{0}$ from the
$n_{0}$-register to the $n_{2}$-register, with settable $\tilde{n}$, reducing
the number of encoding qubits from $n_{0}$ to $n_{2}=n_{0}-2\tilde{n}$. The
output image resolution is $N/2^{\tilde{n}}\times N/2^{\tilde{n}}$.

We adopt the little-endian ordering, with the least significant qubit placed
on the top of the register and labelled by $q=0$, with $0\leq q\leq m-1$ and
$m\in\\{n_{0},n_{1},n_{2}\\}$.222Consider the 3-qubit state
$\ket{abc}=\ket{a}\otimes\ket{b}\otimes\ket{c}$, with $a,b,c=0,1$. The little-
endian convention interprets $a$ as the most significant qubit in the
register. In our notation, it is labelled by $q=3$. We denote $H$ the single-
qubit Hadamard gate.

Algorithm 1 Quantum image downsampling

Input Quantum image $\ket{\Psi}_{0}$
Parameter Integer $\tilde{n}<n_{0}/2$

1:apply $H^{\otimes n_{0}}$ $\triangleright$ $n_{0}$-register

2:apply $U_{\operatorname{QFT}_{0}}$

3:for $q$ in $n_{0}$-register do

4: if $n_{0}-\tilde{n}\leq q\leq n_{0}-1$ then

5: discard the $q$th qubit $\triangleright$ Rule 1 ($n_{0}\to n_{1})$

6:apply $U^{\dagger}_{\operatorname{QFT}_{1}}$ $\triangleright$
$n_{1}$-register

7:for $q$ in $n_{1}$-register do

8: if $n_{0}/2-\tilde{n}\leq q\leq n_{0}/2-1$ then

9: discard the $q$th qubit $\triangleright$ Rule 2 ($n_{1}\to n_{2})$

10:apply $H^{\otimes n_{2}}$ $\triangleright$ $n_{2}$-register

Result Compressed image $\rho_{2}$

The algorithm operates as follows. After applying $H^{\otimes n_{0}}$, a first
$\operatorname{QFT}$ is taken on the register in which $\ket{\Psi}_{0}$ is
initially loaded. Discard the first $\tilde{n}$ most significant qubits from
the bottom of the register, which means averaging out the low-probability
frequency components of the original image (Rule 1). Take the
$\operatorname{QFT^{\dagger}}$. This reduces the image resolution of a factor
$2^{\tilde{n}}$ along only one of its axes. Then, discard the last $\tilde{n}$
positions of the first half of the initial register, which contain redundant
information after the $\operatorname{QFT^{\dagger}}$, then take $H^{\otimes
n_{2}}$. As we discuss below, this yields a $N/2^{\tilde{n}}\times
N/2^{\tilde{n}}$ image, conformally downscaled along both its axes, and
described by the state $\rho_{2}$. There may be different implementations of
this protocol, which eventually uses the superposition principle to achieve a
Fourier compression that operates on both the image axes, simultaneously.
However, we expect such generalizations to produce similar results, eventually
optimizing the complexity of the whole algorithm or maximizing the signal-to-
noise ratio of the final reconstruction.

The algorithm works independently of the presence of $H^{\otimes n_{0}}$ (Step
1) and $H^{\otimes n_{2}}$ (Step 10). As we show in Appendix A, the Hadamard
gates improve the quality at the output, reducing the statistical fluctuations
at each pixel while preserving the original image contrast. We report the
circuit implementation of Alg. 1 in Fig. 2.

Figure 2: Compression by downsampling a quantum image into a register of fewer
qubits. The image is initially encoded in the probabilities of
$\ket{\Psi}_{0}$. The most significant qubit is represented at the bottom of
the $n_{0}$-register. The $\operatorname{QFT}$ is taken. (Rule 1) Chosen an
integer $\tilde{n}<n_{0}/2$, take an $\operatorname{QFT^{\dagger}}$ on the
first $n_{0}-\tilde{n}$ qubits and discard the remaining part of the register.
(Rule 2) Discard the same number of qubits from those register positions that
correspond to the last $\tilde{n}$ qubits of the first half of the
$n_{0}$-register. The algorithm compresses the image $\ket{\Psi}_{0}$ in the
state $\rho_{2}$, reducing the number of pixels from $N^{2}$ to
$N^{2}/4^{\tilde{n}}$. The Hadamard gates reduce the statistical fluctuations
at the output, while preserving the original image contrast (see Appendix A
for a discussion). The trade-off between the output resolution and the amount
of resources saved (the number of discarded qubits) is controlled by the
choice of $\tilde{n}$.

As an example of Rule 1 and 2, consider a $512\times 512$ image encoded in the
$18$-register, with qubits labelled by the list $[0,1,\ldots,17]$. Suppose
that $\tilde{n}=4$. The discarding sequence reads

$[0,1,\ldots,17]\xrightarrow[\text{Discard }{[}14,15,16,17{]}]{\text{Rule
1}}[0,1,\ldots,13]\\\ \xrightarrow[\text{Discard }{[}5,6,7,8{]}]{\text{Rule
2}}[0,1,2,3,4,9,10,11,12,13]\ .$ (4)

These rules, combined with the $\operatorname{QFT}$ and
$\operatorname{QFT^{\dagger}}$, yield a downsampled $32\times 32$ image
encoded in the $10$-register with qubits $[0,1,2,3,4,9,10,11,12,13]$.

The reconstruction of the output image requires the complete knowledge of the
probabilities

$p_{j}=\Tr(\ket{j}_{2}\\!\bra{j}\rho_{2})\ ,$ (5)

with $j\in\\{0,1,\ldots,2^{n_{2}}-1\\}$. The image is obtained by means of a
devectorization operation $\theta^{-1}$, which rearranges $p_{j}$ as the
entries of a $d\times d$ matrix, with $d^{2}=2^{{n}_{2}}$. Characterizing the
sample size for a good-quality output requires further statistical
considerations.

(a)  (b)

(c)

(d)

(e)

Figure 3: Simulated results for a $8$-bit digital image with original
resolution of $512\times 512$ pixels. (a) The image is initially vectorized
and prepared as a $18$-qubit quantum state, then Alg. 1 is taken. Figures
(b-d) show the reconstructed output with respect to the number of $n_{2}$
qubits in the output register. The Hadamard gates improve the reconstruction,
reducing the statistical fluctuations while correcting the image contrast (see
Appendix A for a discussion). Simulation performed with Qiskit Aer and
$2^{n_{2}}\times 256^{\nicefrac{{3}}{{2}}}$ shots. For comparison, all the
images are rescaled to the same size. (b) $n_{2}=16$, $256\times 256$ pixels.
(c) $n_{2}=14$, $128\times 128$ pixels. (d) $n_{2}=10$, $32\times 32$ pixels.
(e) Statistical fluctuations at the output. The reconstruction of (c) is
repeated for $20$ times. The histogram plots the number of pixels with respect
to their standard deviation. The inset shows the standard deviation at each
pixel location.

Since the grey values are probabilistically encoded in the output state, a
single computational basis measurement on $\rho_{2}$ would produce one white
pixel in the image plane, with position specified by the output bitstring. The
complete reconstruction of the image requires the full knowledge of the
probability distribution of Eq. 5. Let $S$ be the number of shots, obtained by
repeating the algorithm and the measurement for $S$ times, and $L$ the number
of grey levels desired at the output, e.g. $L=256$ for an $8$-bit image. Let
$f_{j}$ be the frequency of each outcome. We identify the color _white_ with
the pixel with the highest probability $f_{w}=\max_{j}f_{j}$, with
$f_{w}\in[0,1]$ and $f_{j}\in[0,f_{w}]\ \forall j\in\\{0,1,\ldots,d^{2}-1\\}$.
Each grey value is reconstructed as

$g_{j}=\frac{f_{j}L}{f_{w}}\ ,$ (6)

with $g_{j}=0,1,\ldots L-1$ and $g_{w}=L$. For each pixel, a measurement on
$\rho_{2}$ corresponds to two possible outcomes: a shot is assigned to the
$j$th bin, i.e. to the $j$th pixel, with probability $p_{j}$, or it is not
with probability $1-p_{j}$. Under the normal approximation and with the $95\%$
confidence level [16], the probabilities can be estimated as $p_{j}=f_{j}\pm
2\sqrt{f_{j}(1-f_{j})/S}$. In terms of grey values, this reads

$g_{j}=\frac{f_{j}L}{f_{w}}\pm 2\sqrt{\frac{f_{j}(1-f_{j})L^{2}}{f_{w}^{2}S}}\
.$ (7)

By requiring that $g_{j}$ fluctuates of at most one grey level, we get $S\geq
4f_{j}(1-f_{j})L^{2}/f_{w}^{2}$. For $f_{w}\geq 0.5$, $S\geq L^{2}/f_{w}^{2}$,
while for $f_{w}<0.5$, $S\geq 4L^{2}/f_{w}^{2}$. A conservative choice would
yield $S\simeq 4L^{2}/f_{w}^{2}$. For an all-purpose estimation, consider a
$d\times d$ completely white image as the worst-case scenario. Since
$f_{w}=1/d^{2}$, a full reconstruction requires

$S\simeq 4L^{2}d^{2}\ ,$ (8)

where each pixel uniformly collects an average of $4L^{2}$ shots.

Eq. 8 provides a conservative estimation for every image. The optimal sample
size depends on the proportion between dark and bright pixels, which
determines the value of $f_{w}$.333An example is given by highly contrasted
and mostly-black images, in which small samples of data will quickly localize
in the significant sectors of the image. For a specific image, the
reconstruction can be actively optimized by measuring the fluctuations each
time a new shot is collected, then stopping the experimental repetitions as
soon as the desired standard deviation is reached by the chosen amount of
pixels.

In terms of number of gates, the sole algorithm of Fig. 2 brings an
exponential speedup over its classical counterpart. However, the
reconstruction requires multiple runs of Alg. 1, thus increasing the overall
cost of the protocol. Using the above characterization, we show that an
advantage remains for sufficiently downsampled images.

######  Theorem.

Let a $N\times N$ image be encoded in the $n_{0}$-register. Consider the
output of Alg. 1 in the $n_{2}$-register, with resolution
$N/2^{\tilde{n}}\times N/2^{\tilde{n}}$, $L=2^{c}$ grey levels, and
downsampling factor $\tilde{n}=(n_{0}-n_{2})/2$. A quantum advantage holds if

$3+2c+\log_{2}\left(\log_{2}n_{0}\right)<2\tilde{n}<n_{0}\ .$ (9)

###### Proof.

For $n_{1}\ll n_{0}$, the complexity of $\operatorname{QFT}_{0}$ dominates
that of $\operatorname{QFT^{\dagger}}_{1}$, while for $n_{1}\simeq n_{0}$,
both contribute to the same order. For this reason, the whole cost for
operating with $(\mathds{1}\otimes U^{\dagger}_{\operatorname{QFT}_{1}})\
U_{\operatorname{QFT}_{0}}$ can be upper bounded at
$\mathcal{O}(2n_{0}\log_{2}(n_{0}))$ gates [11]. For a conservative
reconstruction, the algorithm must be repeated for
$4L^{2}N^{2}/2^{2\tilde{n}}$ times, yielding a total cost of
$Q(n_{0},\tilde{n})=\mathcal{O}(8L^{2}\log_{2}(n_{0})n_{0}2^{n_{2}})$ gates.
The same protocol performed with the classical fast Fourier transform
($\operatorname{FFT}$) requires $\mathcal{O}\left(2N^{2}\log_{2}(N)\right)$
operations, i.e. $C(n_{0})=\mathcal{O}\left(n_{0}2^{n_{0}}\right)$ gates [17].
A quantum advantage holds whenever $Q(n_{0},\tilde{n})/C({n_{0}})<1$. This
condition gives the left-hand side of Eq. 9. The other side of Eq. 9
represents the maximum compression achievable for a $n_{0}$-register, upper
bounded by the input resolution, i.e. $\tilde{n}<n_{0}/2$. ∎

In Fig. 3 we simulate the full compression and reconstruction of a $8$-bit
$512\times 512$ image, prepared in the $18$-register. We plot the output for
different values of $n_{2}$. In Fig. 3e we plot the statistical fluctuations
for a reconstruction performed with $L^{3/2}d^{2}$ shots. We show that this
order of magnitude provides the adequate statistics for an average
reconstruction. The simulation code can be found at [18].

The vectorized representation of Eq. 1 allows the processing of high-
resolution images even for small NISQ registers [19]. For example, let $b$ be
the maximum number of qubits supported by an hypothetical hardware device, and
consider a $N\times N$ image exceeding the encoding capability of the hardware
with $N^{2}>2^{b}$. The compression can still be achieved by first splitting
the image in $2^{b/2}\times 2^{b/2}$ subimages, then processing it as a
sequence of vectorized quantum states
$\left\\{\ket{\Psi^{(m)}}_{0}\right\\}_{m}$, each given in input to Alg. 1,
with $m=0,1,\ldots,N^{2}/2^{b}$. A similar pre-encoding is also performed by
the classical JPEG algorithm, which splits the original image in $8\times 8$
blocks, before mapping them to the spatial frequencies domain [2].

Finally, we outline an alternative algorithm that compresses the image without
downscaling its resolution. Consider
$U_{\operatorname{QFT}_{0}}\ket{\Psi}_{0}$. Instead of discarding the last
$\tilde{n}$ qubits of the $n_{0}$-register, we apply Rule 1 to reinitialize
them to $\ket{0\ldots 0}_{\tilde{n}}$.444This operation can be unitarily
implemented by adding as many ancillas and SWAP operations as the number of
qubits to be reinitialized. After taking $\operatorname{QFT^{\dagger}}_{0}$
and skipping Rule 2, we obtain $\rho_{0}$, without modifying the size of the
original register. This implementation closely relates to the classical JPEG
compression, in particular when combined with the previous subimages encoding.
As opposed to Alg. 1, this algorithm preserves the resolution of the input
image. For this same reason, however, the full output reconstruction shows no
computational advantage with respect to its classical counterpart.

##  III Hardware encoder: The quantum camera

In this section, we show how to encode an image into the $n_{0}$-register
using a multiatom lattice sensor analogous to a classical charge-coupled
device (CCD) [20]. This implementation precedes the application of Alg. 1,
whose working principle remains independent of the specific hardware encoder
model. The output of the sensor is related to the $n_{0}$-register of Alg. 1,
in which the fingerprint of the image is loaded as the multiqubit quantum
state $\ket{\Psi}_{0}$.

Consider a classical image encoded in a multimode coherent state
$\ket{\alpha_{\psi}}=D(\alpha_{\psi})\ket{\varnothing}$, where
$\ket{\varnothing}$ denotes the vacuum state and

$D(\alpha_{\psi})=\exp(\alpha A^{\dagger}_{\psi}-\alpha^{*}A_{\psi})$ (10)

the multimode displacement operator. We work in the far-field approximation,
with $k$ and $x$ respectively labelling the momentum and the position on the
plane transversal to the direction of propagation of the wave. The creation
operator

$A_{\psi}^{\dagger}=\int dk\widetilde{\psi}(k)a^{\dagger}(k)$ (11)

encodes the Fourier transform $\widetilde{\psi}(k)=\int dx\psi(x)e^{-ik\cdot
x}$ of the spectral amplitudes of $\ket{\alpha_{\psi}}$. In our notation,
$\psi$ describes the classical analog image encoded in the coherent state,
while $\ket{\Psi}_{0}$ denotes the same image but discretized, vectorized and
probabilistically encoded in the $n_{0}$-register of the previous section. In
this section, we show how to connect these two representations.

We consider a lattice made of $N^{2}$ identical atoms, with equally spaced
energy levels. Let $(m,n)$ label their position on the $N\times N$ lattice.
Each atom can be modelled as a two-level system, namely a qubit with
computational basis $\left\\{\ket{0}_{mn},\ket{1}_{mn}\right\\}$. We
initialize the lattice in the vacuum state
$\ket{b}=\bigotimes_{m^{\prime},n^{\prime}}\ket{0}_{m^{\prime}n^{\prime}}$,
which represents a completely black image with all the qubits in the ground
state.

We model the interaction between the lattice and the electromagnetic field
using a multimode and multiatom Jaynes-Cummings Hamiltonian, in the resonant
rotating wave approximation [21, 22, 23]

$H_{I}=\int dk\sum_{m,n=0}^{N-1}\gamma^{*}_{mn}(k)a(k)\sigma_{mn}^{+}+\text{
H.c.}\ ,$ (12)

where

$\sigma_{mn}^{+}=\ket{1}_{mn}\\!\bra{0}\
,\quad\sigma_{mn}^{-}=\ket{0}_{mn}\\!\bra{1}\ ,$ (13)

and $\gamma_{mn}(k)$ is the Fourier transform of the spatial coupling function
$g_{mn}(x)$ between the coherent photons and a qubit located at $(m,n)$, i.e.
$\gamma_{mn}(k)=\int dxg_{mn}(x)e^{-ik\cdot x}$. We assume that $g_{mn}$ is
compactly supported $\forall m,n$ and that
$\operatorname{supp}(g_{mn})\cap\operatorname{supp}(g_{m^{\prime}n^{\prime}})$
is negligible.

The interaction Hamiltonian $H_{I}$ encodes the input coherent state as a
quantum image in the user’s sensor. See Appendix B for a complete derivation
and a discussion about time evolution. Consider a shutter that initially
prevents the photons from interacting with the qubits, so that the initial
state reads $\ket{I}\rangle=\ket{\alpha_{\psi}}\otimes\ket{b}$. When the
shutter opens, a photon may release energy in the sensor, exciting one of the
qubits as $\ket{0}_{mn}\to\ket{1}_{mn}$. Globally, a single interaction may
give no excitation, a single excitation or multiple qubits excitations, with
contributions to the final state of the form

$c^{0}_{0}\ket{b}+c^{1}_{0}\ket{0\ldots 001}+c^{1}_{1}\ket{0\ldots
010}+\ldots\\\ +c^{1}_{N^{2}-1}\ket{10\ldots 00}+c^{2}_{0}\ket{0\ldots
011}+\ldots$ (14)

The vacuum term can be neglected in post-selection, by discarding any
completely black image at the output. Then, the single-qubit contributions
become dominant and the final state reads
$\ket{F}\rangle\simeq\ket{\alpha_{\psi}}\otimes\ket{\Omega}$, where

$\displaystyle\ket{\Omega}=C\sum_{m,n=0}^{N-1}v_{mn}\sigma^{+}_{mn}\ket{b}\ ,$
(15) $\displaystyle v_{mn}=\int_{P_{mn}}dx\psi(x)g^{*}_{mn}(x)\ ,$ (16)

with $P_{mn}=\operatorname{supp}{(g_{mn})}$, and $C$ an overall normalization
constant. In these equations, the interaction term $g_{mn}(x)$ acts as a
spatial transfer function that discretizes the image in the region $P_{mn}$,
encoding the light intensity in the probability of the corresponding qubit to
occupy the higher energy level state. In Fig. 4 we plot the probabilities
encoded from a superposition of two Gaussian packets. We compare the numerical
results with the probability density of the input state, showing that they
correctly reproduce the spectral amplitudes of $\ket{\alpha_{\psi}}$.

(a)  (b)

Figure 4: Comparison between the spectral amplitudes $\psi$ and the multiqubit
quantum state $\ket{\Omega}$, encoded using the multiatom lattice sensor
described by Eq. 16. (a) Contour plot of $|\psi(x,y)|^{2}$, obtained from the
multimode coherent spatial spectrum
$\psi(x,y)=\sum_{i=0}^{1}K\exp(-a_{i}(x-x_{i})^{2}-b_{i}(y-y_{i})^{2})$, with
parameters $x_{0}=-y_{1}=-1.5$, $x_{1}=-y_{0}=2$, $a_{0}=b_{1}=0.35$,
$a_{1}=b_{0}=1$ and normalization constant $K$. (b) Probabilities
$|v_{mn}|^{2}$ of the encoded state $\ket{\Omega}$, plotted as a $256\times
256$ grayscale image. The sensor is a $256\times 256$ lattice of evenly spaced
identical atoms, with spatial coupling functions
$g_{mn}(x,y)=\exp(-5(x-a_{n})^{2}-5(y-b_{m})^{2})$ and positions labelled by
$(a_{n},b_{m})$, with $n,m=0,1,\ldots,255$.

The state $\ket{\Omega}$ represents the image using a sub-optimal one-hot
encoding, i.e. with only $N^{2}$-qubit contributions of the form
$(\bigotimes_{m^{\prime}\neq m,n^{\prime}\neq
n}\ket{0}_{m^{\prime}n^{\prime}})\otimes\ket{1}_{mn}\forall
m,n\in\\{0,1,\ldots,N-1\\}$. We optimize the output of the hardware encoder by
appending a one-hot to binary converter [24, 25], which uses a combination of
CNOTs to re-encode the image in $n_{0}=2\log_{2}(N)$ qubits,555This pre-
compression prepares the input for Alg. 1: It is a _lossless_ reorganization
of the encoding coefficient $v_{mn}$, inside a smaller but fully exploited
quantum register. yielding

$\ket{\Omega}\to\sum_{j=0}^{N^{2}-1}w_{j}\ket{j}_{0}=\ket{\Psi}_{0}\ ,$ (17)

which is the state $\ket{\Psi}_{0}$ of Section II, with $w=\theta(v)$. This
conversion requires $\mathcal{O}(N^{2})$ operations, which is the same readout
cost of the CCD bidirectional shift registers.

After this step, the user applies Alg. 1 to discard $2\tilde{n}$ qubits from
the encoding register. This compresses $\ket{\Psi}_{0}$ in $\rho_{2}$,
reducing the requirements for its storage, e.g. the number of qubits of a
quantum random access memory [26], as well as the dimension of the channel
needed for communicating the image to another user [27].

##  IV Conclusions

In this paper, we discussed an algorithm for quantum image downsampling and
compression. Chosen the downsampling factor, our protocol uses the
$\operatorname{QFT}$ to downscale the original visual pattern, which is
preserved while reducing the number of encoding qubits.

This work opens interesting insights and perspectives for quantum imaging and
quantum image processing. Regarding the compression only, our algorithm
provides an exponential speedup over its classical $\operatorname{FFT}$
counterpart. However, its cost increases when reconstructing the full image at
the output, due to the necessary statistics. We investigated the
reconstruction process, showing that the algorithm is still advantageous when
working on high-resolution images. Whenever a full reconstruction is not
needed, e.g. when forwarding the output of the algorithm to a quantum
classifier, the exponential advantage would be completely recovered.

As a possible hardware implementation, we designed a multiatom lattice sensor
for coherent light. Described by the Jaynes-Cummings Hamiltonian, this
hardware encoder maps the light intensity at each lattice location to the
probability of the corresponding qubit of being excited by a single-photon
interaction. In this framework, two users can capture and share images even
with limited communication resources, using the algorithm to forward the image
state through lower-dimensional channels.

## Acknowledgments

This work received support from EU H2020 QuantERA ERA-NET Cofund in Quantum
Technologies, Quantum Information and Communication with High-dimensional
Encoding (QuICHE) under Grant Agreement 731473 and 101017733, from the U.S.
Department of Energy, Office of Science, National Quantum Information Science
Research Centers, Superconducting Quantum Materials and Systems Center (SQMS)
under Contract No. DE-AC02-07CH11359. L.M. acknowledges support from the PNRR
MUR Project PE0000023-NQSTI. C.M. acknowledges support from the National
Research Centre for HPC, Big Data and Quantum Computing, PNRR MUR Project
CN0000013-ICSC. No animals were harmed in the making of this work. S.R. would
like to thank his feline friend for graciously and patiently posing for the
picture used in this research.

##  APPENDIX A FURTHER CONSIDERATIONS ON THE ALGORITHM

In this section, we provide an explicit example of our downsampling and
compression algorithm for a simple $4\times 4$ pattern. We first describe the
algorithm without using the Hadamard gates. Then, we show that they reduce the
contrast shift and the statistical fluctuations at the output.

(a)  (b)

Figure 5: Compression by downsampling two arrays prepared as $8$-qubit quantum
states, with $\tilde{n}=1$. The simulation is performed with Qiskit Aer and
$10^{6}$ shots. The output of Alg. 1 is plotted with and without the Hadamard
gates, and by post-correcting the contrast in the latter case. The plot shows
the probabilities $p_{i}$ of each multiqubit output state $\ket{i}_{2}$. (a)
The input array is $[0,1,2,\ldots,255]$. The continuous line shows the
original pattern directly represented in the $6$-qubit register, i.e. the
array $[0,1,2,\ldots,63]$. (b) The input is
$[0,1,2,\ldots,127,127,126,125,\ldots,0]$. The continuous line shows the same
pattern in the $6$-qubit register, i.e. $[0,1,2,\ldots,63,63,62,61,\ldots,0]$.
The output best reproduces the original input when using the Hadamard, which
preserves the contrast and shows no artefact. The discontinuities at each $8$
multiqubit configuration can be removed by turning off (Rule 2), which
remains, however, essential to preserve the aspect ratio when compressing two-
dimensional images instead of one-dimensional arrays.

Consider a lower triangular $4\times 4$ image

$\mathscr{I}=\begin{bmatrix}1&0&0&0\\\ 1&1&0&0\\\ 1&1&1&0\\\
1&1&1&1\end{bmatrix}\ .$ (18)

This pattern can be downscaled into a $2\times 2$ matrix as

$\mathscr{I}=\begin{bmatrix}1&0\\\ 1&1\\\ \end{bmatrix}\ .$ (19)

We vectorize and represent Eq. 18 as $4$-qubit state

$\ket{\Psi}_{0}\leftarrow\frac{1}{\sqrt{8}}\left[1\ 0\ 0\ 0\ 1\ 1\ 0\ 0\ 1\ 1\
1\ 0\ 1\ 1\ 1\ 1\right]^{T}\ .$ (20)

With $n_{2}=2$, $\tilde{n}=1$ and before discarding any qubit, Alg. 1 reads

$\ket{\Phi}_{0}=(\mathds{1}\otimes U^{\dagger}_{\operatorname{QFT}_{1}})\
U_{\operatorname{QFT}_{0}}\ket{\Psi}_{0}\ .$ (21)

We denote the amplitude components of the output state as $\ket{abcd}$, with
$a$ ($d$) labelling the bottom (top) qubit on the register of Fig. 2 and
$a,b,c,d=0,1$. Let $p_{abcd}$ be the probabilities of $\ket{abcd}$. We apply
Rule 1 by tracing out the high spatial-frequency qubit $a$ from
$\ket{\Phi}_{0}$, i.e. by summing $p_{0bcd}$ with $p_{1bcd}$ $\forall b,c,d$.
Then, we apply Rule 2 by doing the same for the redundant qubit $c$, i.e. by
summing $p_{b0d}$ with $p_{b1d}$ $\forall b,d$. The probabilities in the
$n_{2}$-register read

$p_{bd}=\sum_{a,c=0}^{1}p_{abcd}\ ,$ (22)

which correspond to the $2\times 2$ image

$\mathscr{I}_{c}=\begin{bmatrix}p_{00}&p_{01}\\\ p_{10}&p_{11}\end{bmatrix}\
.$ (23)

The above procedure is implicitly summarized in Eq. 5, in which the compressed
state $\rho_{2}$ is obtained by applying (Rule 1) and (Rule 2) to
$\ket{\Phi}_{0}$. For Eq. 18, we find

$\mathscr{I}_{c}\simeq\begin{bmatrix}0.35&0.06\\\ 0.32&0.27\end{bmatrix}\ ,$
(24)

which reproduces the same input pattern, but downsampled and represented with
fewer qubits than $\ket{\Psi}_{0}$.

The results improve when $\ket{\Psi}_{0}$ is encoded in the $X$ basis. Let $H$
be the single-qubit Hadamard operator. As shown in Fig. 2, we introduce
$H^{\otimes n_{0}}$ and $H^{\otimes n_{2}}$ respectively before
$\operatorname{QFT}_{0}$ and after (Rule 2). Hence, Alg. 1 reads

$\ket{\Psi}_{0}\to H^{\otimes n_{0}}\to
U_{\operatorname{QFT}_{0}}\to\text{Rule 1}\\\ \to
U^{\dagger}_{\operatorname{QFT}_{1}}\to\text{Rule 2}\to H^{\otimes
n_{2}}\to\rho_{2}\ ,$ (25)

yielding

$\mathscr{I}_{c}\simeq\begin{bmatrix}0.30&0.00\\\ 0.41&0.29\end{bmatrix}\ ,$
(26)

which better reproduces the ideal $2\times 2$ pattern of Eq. 24.

In Fig. 5, we simulate the compression of a one-dimensional array pattern,
with and without using the Hadamard gates. Without the Hadamard, Alg. 1
reproduces the original input, but with lowered contrast. Moreover, non-
symmetrical boundary artefacts occur for a ladder, i.e. linear and monotonic,
pattern. This effect increases with the number of discarded qubits, i.e.
inversely with the size of $\operatorname{QFT^{\dagger}}_{1}$. In both cases,
the Hadamard improves the quality of the output: it regularizes the contrast,
while removing the artefacts in the ladder pattern. In Fig. 6 we show that,
for a generic $512\times 512$ image, the Hadamard also reduces the statistical
fluctuations in the output reconstruction, while keeping the same number of
shots.

(a)  (b)

Figure 6: Statistical reconstruction at the algorithm output, without (a) and
with (b) the Hadamard gates. The input image represents a Shepp-Logan phantom,
commonly used in medical tomography [28], which is prepared as a $18$-qubit
quantum state and downsampled for $\tilde{n}=2$. The results for other
downsampling factors are reported in Fig. 7. The simulation is performed with
Qiskit Aer and $2^{14}$ shots. The choice of a sub-optimal sample size
purposely showcases the effect of the statistical fluctuations. The histograms
plot the number of pixels with respect to their standard deviation, obtained
by repeating the reconstruction for $20$ times. The vertical axis is in
$\log_{10}$ scale. The inset displays the standard deviation at each pixel
location. (a) Compression in the standard computational basis, i.e. without
using the Hadamard gates. (b) Compression in the $X$ basis, i.e. with the
Hadamard gates, as reported in Fig. 2. Statistical fluctuations reduce when
using the Hadamard, while keeping the same number of shots.

(a)  (b)  (c)  (d)  (e)  (f)  (g)  (h)

Figure 7: Simulated results for a two $8$-bit digital images with same
resolution of $512\times 512$ pixels. (a-b) Same input image and
reconstruction of Fig. 3, for different downsampling factors. (a) The image is
vectorized and prepared as a $18$-qubit quantum state, then Alg. 1 is taken
with $2^{n_{2}}\times 256^{\nicefrac{{3}}{{2}}}$ shots. (b) $n_{2}=12$,
$64\times 64$ pixels. (c) $n_{2}=8$, $16\times 16$ pixels. (d) $n_{2}=6$,
$8\times 8$ pixels. (e-h) Compression of a highly contrasted and mostly black
image (e) The image is vectorized and prepared as a $18$-qubit quantum state,
then Alg. 1 is taken with $2^{n_{2}}\times 256$ shots. (f) $n_{2}=16$,
$256\times 256$ pixels. (g) $n_{2}=14$, $128\times 128$ pixels. (h)
$n_{2}=12$, $64\times 64$ pixels.

##  APPENDIX B JAYNES-CUMMINGS HARDWARE ENCODING

In this section we show how to obtain the state of Eq. 15 from the multimode
and multiatom Jaynes-Cummings model introduced in [21, 22], also known as
multimode Tavis-Cummings model [29]. We adopt units with $\hbar=1$. We work in
the interaction picture and in the rotating wave approximation [23], in which
the free Hamiltonian reads

$H_{F}=\frac{1}{2}\sum_{m,n=0}^{N-1}\omega_{0}\sigma^{(3)}_{mn}+\int
dk\omega(k)a^{+}(k)a(k)\ ,$ (27)

with $\sigma^{(3)}_{mn}=\ket{1}_{mn}\bra{1}_{mn}-\ket{0}_{mn}\bra{0}_{mn}$,
while the interaction term yields

$H_{I}=\int dk\sum_{m,n=0}^{N-1}\gamma^{*}_{mn}(k)a(k)\sigma_{mn}^{+}+\text{
H.c.}$ (28)

The total Hamiltonian of the system reads

$H_{JC}=H_{F}+\lambda H_{I}\ ,$ (29)

where $\lambda$ is an overall coupling constant.

Prepare the system in the state
$\ket{I}\rangle=\ket{\alpha_{\psi}}\otimes\ket{b}$. Since $[H_{F},H_{I}]=0$,
the evolution of $\ket{I}\rangle$ is completely driven by the unitary operator
generated by $H_{I}$, so that

$U_{t}=\mathds{1}+it\lambda H_{I}+\mathcal{O}(\lambda^{2})\ .$ (30)

The final state $\ket{F}\rangle=U_{t}\ket{I}$ then reads

$\ket{F}\rangle=\ket{\alpha_{\psi}}\otimes\ket{b}+it\lambda
H_{I}\ket{I}+\mathcal{O}(\lambda^{2})\ .$ (31)

We neglect the first term by post-selectively discarding any completely black
image at the output. Then, the leading order contribution becomes dominant and
the evolution is solely controlled by the Jaynes-Cummings Hamiltonian

$\ket{F}\rangle\simeq it\lambda\int
dk\sum_{m,n=0}^{N-1}\gamma^{*}_{mn}(k)a(k)\sigma_{mn}^{+}\ket{\alpha_{\psi}}\otimes\ket{b}\
,$ (32)

where the Hermitian conjugate is annihilated on $\ket{b}$. For the multimode
coherent state

$D(\alpha_{\psi})\ket{\varnothing}\simeq\prod_{k}\exp(\widetilde{\psi}(k)a^{\dagger}(k)+\text{
H.c.})\ ,$ (33)

then $a(k)\ket{\alpha_{\psi}}=\alpha\widetilde{\psi}(k)\ket{\alpha_{\psi}}$. A
projection on the coherent state gives
$\ket{\Omega}=\langle\alpha_{\psi}\ket{F}\rangle$. By substituting the Fourier
transform of $\psi$ and $g^{*}_{mn}$, we get

$\ket{\Omega}=it\lambda\alpha\sum_{m,n=0}^{N-1}\int
dx\psi(x)g^{*}_{mn}(x)\sigma^{+}_{mn}\ket{b}\ ,$ (34)

which is precisely the result shown in Eqs. 15 and 16.

## References

  * Salomon and Motta [2010] D. Salomon and G. Motta,  _Handbook of Data Compression_ (Springer, 2010).
  * rep [1994] _Information technology –- Digital compression and coding of continuous-tone still images: Requirements and guidelines_ , ISO/IEC 10918-1:1994 (International Organization for Standardization, Geneva, Switzerland, 1994).
  * Wang  _et al._ [2022] Z. Wang, M. Xu, and Y. Zhang, Review of quantum image processing, Arch. Computat. Methods Eng. 29, 737 (2022).
  * Yan and Venegas-Andraca [2020] F. Yan and S. E. Venegas-Andraca,  _Quantum Image Processing_ (Springer, 2020).
  * Yan  _et al._ [2016] F. Yan, A. M. Iliyasu, and S. E. Venegas-Andraca, A survey of quantum image representations, Quantum Inf. Process. 15, 1 (2016).
  * Le  _et al._ [2011] P. Q. Le, F. Dong, and K. Hirota, A flexible representation of quantum images for polynomial preparation, image compression, and processing operations, Quantum Inf. Process. 10, 63 (2011).
  * Venegas-Andraca and Bose [2003] S. E. Venegas-Andraca and S. Bose, Storing, processing, and retrieving an image using quantum mechanics, in  _Quantum Information and Computation_, Vol. 5105 (SPIE, 2003) pp. 137 – 147\.
  * Zhang  _et al._ [2013] Y. Zhang, K. Lu, Y. Gao, and M. Wang, NEQR: a novel enhanced quantum representation of digital images, Quantum Inf. Process. 12, 2833 (2013).
  * Yao  _et al._ [2017] X.-W. Yao, H. Wang, Z. Liao, M.-C. Chen, J. Pan, J. Li, K. Zhang, X. Lin, Z. Wang, Z. Luo, W. Zheng, J. Li, M. Zhao, X. Peng, and D. Suter, Quantum image processing and its application to edge detection: Theory and experiment, Phys. Rev. X 7, 031041 (2017).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, 2010).
  * Hales and Hallgren [2000] L. Hales and S. Hallgren, An improved quantum Fourier transform algorithm and applications, in  _Proceedings 41st Annual Symposium on Foundations of Computer Science_ (2000) pp. 515–525.
  * Jiang  _et al._ [2018] N. Jiang, X. Lu, H. Hu, Y. Dang, and Y. Cai, A novel quantum image compression method based on JPEG, Int. J. Theor. Phys. 57, 611 (2018).
  * gui Zhou  _et al._ [2017] R. gui Zhou, W. Hu, P. Fan, and H. Ian, Quantum realization of the bilinear interpolation method for NEQR, Sci. Rep. 7, 2511 (2017).
  * Yan  _et al._ [2021] F. Yan, S. Zhao, S. E. Venegas-Andraca, and K. Hirota, Implementing bilinear interpolation with quantum images, Digit. Signal Process. 117, 103149 (2021).
  * Cui  _et al._ [2023] Z. Cui, S. Jin, A. Sone, and X. Wang, Achieving a significant speedup for quantum image filtering (2023), arXiv:2306.07251 [quant-ph] .
  * Rotondi  _et al._ [2022] A. Rotondi, P. Pedroni, and A. Pievatolo,  _Probability, Statistics and Simulation: With Application Programs Written in R_ (Springer, 2022).
  * Brigham and Morrow [1967] E. O. Brigham and R. E. Morrow, The fast Fourier transform, IEEE Spectr. 4, 63 (1967).
  * [18] S. Roncallo, https://github.com/simoneroncallo/quantum_jpeg.
  * Preskill [2018] J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Boyle and Smith [1970] W. S. Boyle and G. E. Smith, Charge coupled semiconductor devices, Bell Syst. Tech. J. 49, 587 (1970).
  * Emary [2013] C. Emary, Dark-states in multi-mode multi-atom Jaynes-Cummings systems, J. Phys. B: At. Mol. Opt. Phys. 46, 224008 (2013).
  * Wickenbrock  _et al._ [2013] A. Wickenbrock, M. Hemmerling, G. R. M. Robb, C. Emary, and F. Renzoni, Collective strong coupling in multimode cavity QED, Phys. Rev. A 87, 043817 (2013).
  * Gerry and Knight [2004] C. Gerry and P. Knight,  _Introductory Quantum Optics_ (Cambridge University Press, 2004).
  * Chen  _et al._ [2022] B. Chen, H. Wu, H. Yuan, L. Wu, and X. Li, A logarithm depth quantum converter: From one-hot encoding to binary encoding (2022), arXiv:2206.11166 [quant-ph] .
  * Bärtschi and Eidenbenz [2019] A. Bärtschi and S. Eidenbenz, Deterministic preparation of Dicke states, in  _Fundamentals of Computation Theory_ (2019) pp. 126–139.
  * Giovannetti  _et al._ [2008] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Phys. Rev. Lett. 100, 160501 (2008).
  * Gyongyosi  _et al._ [2018] L. Gyongyosi, S. Imre, and H. V. Nguyen, A survey on quantum channel capacities, IEEE Commun. Surv. Tutor. 20, 1149 (2018).
  * Shepp and Logan [1974] L. A. Shepp and B. F. Logan, The Fourier reconstruction of a head section, IEEE Trans. Nucl. Sci 21, 21 (1974).
  * Tavis and Cummings [1968] M. Tavis and F. W. Cummings, Exact solution for an $N$-molecule—radiation-field Hamiltonian, Phys. Rev. 170, 379 (1968).