# Amplitude-Aware Lossy Compression for Quantum Circuit Simulation

Xin-Chuan Wu  Department of Computer Science
University of Chicago
Chicago, USA
<EMAIL_ADDRESS>Sheng Di  Mathematics and Computer Science
Argonne National Laboratory
Lemont, USA
<EMAIL_ADDRESS>Franck Cappello  Mathematics and Computer Science
Argonne National Laboratory
Lemont, USA
<EMAIL_ADDRESS>Hal Finkel  Argonne Leadership Computing Facility
Argonne National Laboratory
Lemont, USA
<EMAIL_ADDRESS>Yuri Alexeev  Computational Science
Argonne National Laboratory
Lemont, USA
<EMAIL_ADDRESS>Frederic T. Chong  Department of Computer Science
University of Chicago
Chicago, USA
<EMAIL_ADDRESS>
###### Abstract

Classical simulation of quantum circuits is crucial for evaluating and
validating the design of new quantum algorithms. However, the number of
quantum state amplitudes increases exponentially with the number of qubits,
leading to the exponential growth of the memory requirement for the
simulations. In this paper, we present a new data reduction technique to
reduce the memory requirement of quantum circuit simulations. We apply our
amplitude-aware lossy compression technique to the quantum state amplitude
vector to trade the computation time and fidelity for memory space. The
experimental results show that our simulator only needs 1/16 of the original
memory requirement to simulate Quantum Fourier Transform circuits with 99.95%
fidelity. The reduction amount of memory requirement suggests that we could
increase 4 qubits in the quantum circuit simulation comparing to the
simulation without our technique. Additionally, for some specific circuits,
like Grover’s search, we could increase the simulation size by 18 qubits.

###### Index Terms:

Quantum Computing, Lossy Compression, Quantum Fourier Transform, Quantum
Circuit Simulation, Message Passing Interface

##  I Introduction

Classical simulation of quantum circuits is crucial for better understanding
the operations and behaviors of quantum computers. Such simulations allow
researchers and developers to evaluate the complexity of new quantum
algorithms and validate the design of quantum circuits. Previous studies have
provided different simulation techniques, such as full amplitude-vector update
[1, 2, 3], Feynman paths [4], and tensor network contractions [5, 6, 7, 8, 9]
to perform the simulation of quantum circuits. Full amplitude-vector update
simulations provide all the amplitudes of the quantum state in detail, and
hence it is the best tool for quantum algorithm debugging, development, and
validation. Full amplitude-vector update simulators generally use complex
double precision amplitudes to represent the state of the quantum systems.
Given $n$ quantum bits (qubits), we need $2^{n}$ amplitudes to describe the
quantum system [10]. As a result, the size of the state vector is $2^{n+4}$
bytes. Since the number of quantum state amplitudes grows exponentially with
the number of qubits in the system, the size of the quantum circuits
simulation is restricted by the memory capacity of the classical computing
system. For example, to store the full quantum state of a 45-qubit system, the
memory requirement is 0.5 petabytes. Table I shows examples of several
supercomputers and the largest quantum system they can simulate theoretically.
Circuits with more than 49-qubit system would require too much memory to
simulate directly.

TABLE I: Examples of supercomputers and the largest quantum system they can simulate. System | Memory (PB) | Max Qubits
---|---|---
TACC Stampede | 0.192 | 43
Titan | 0.71 | 45
Theta | 0.8 | 45
K computer | 1.4 | 46
Exascale | 4-10 | 48-49

Since the simulation size is restricted by the memory capacity of the
classical computing systems, our goal is to trade the computation time for the
memory space. By compressing the state vector, we can reduce the memory
requirement for the quantum circuit simulation. In other words, we are able to
simulate a larger quantum system by using the same memory capacity.
Integrating data compression into the simulation causes certain performance
overhead, while we are able to obtain larger simulation scale that cannot be
reached before with the limited memory capacity.

With compression techniques, the simulation size is determined by the quantum
state vector’s compression ratio. In general, lossy compression algorithms
achieve significantly higher compression ratios than lossless compressors,
while introducing errors to a certain extent. To minimize the error
propagation and guarantee high fidelity results, we develop the _Amplitude-
Aware Lossy Compression_ (AALC) technique by leveraging both Zstandard
lossless compressor [11] and SZ lossy compressor [12, 13, 14]. AALC is
designed for quantum circuit simulators to trade data accuracy for data
reduction. This technique can preserve the most important quantum information.

To evaluate our approach on a working simulator, we implement AALC on Intel-
QS, a quantum circuit simulator developed by Intel [2]. Intel-QS is a
distributed high performance quantum circuit simulator, which uses full state
amplitude-vector update to complete the simulation. Thus, there is no circuit
depth limitation in our simulation framework111In general, most of the
supercomputing systems have a 24-hour wall-time limitation. This run-time
constraint puts a circuit depth limitation on the simulation. However, one can
save the state vector before terminating the job, and then resume the task by
loading the state vector in the next job submission..

Our AALC approach integrates knowledge of quantum computation and data
compression techniques to reduce the memory requirement of quantum circuit
simulation. The main contributions of our work are:

  * •

We identify the feasibility of applying data compression techniques to quantum
circuit simulator.

  * •

We establish the AALC approach to leverage lossless and lossy compressor in
quantum state amplitude vector to reduce the memory requirement for storing
the data.

  * •

We present evaluation results based on AALC technique, and provide
mathematical proofs that our technique can scale the simulation size beyond 49
qubits.

  * •

We implement AALC for amplitude vectors in Intel-QS and show that there is a
good data reduction with high quantum state fidelity.

Our paper is organized as follows. In Section II, we introduce background of
quantum circuit simulation. In Section III, we describe our AALC methodology.
In Section IV, we present the evaluation of our technique in Intel-QS. We
discuss and point out the future directions in Section V.

##  II Background

Figure 1: Example of two-qubit quantum state with single-qubit gate
operations.

A qubit is a two-level quantum systems, and the state $\ket{\psi}$ can be
expressed as

$\ket{\psi}=\alpha_{0}\ket{0}+\alpha_{1}\ket{1}$

where $\alpha_{0}$ and $\alpha_{1}$ are complex amplitudes, and
$|\alpha_{0}|^{2}+|\alpha_{1}|^{2}=1$. $\ket{0}$ and $\ket{1}$ are two
computational orthonormal basis states. The quantum state can also be
represented as

$\ket{\psi}=\alpha_{0}\begin{bmatrix}1\\\
0\end{bmatrix}+\alpha_{1}\begin{bmatrix}0\\\
1\end{bmatrix}=\begin{bmatrix}\alpha_{0}\\\ \alpha_{1}\end{bmatrix}.$

The state of a two-qubit system can be described by using 4 amplitudes.

$\ket{\psi}=\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11}=\begin{bmatrix}\alpha_{00}\\\
\alpha_{01}\\\ \alpha_{10}\\\ \alpha_{11}\end{bmatrix}.$

More generally, the state of an n-qubit quantum system can be represented by
using $2^{n}$ amplitudes.

$\ket{\psi}=\alpha_{0...00}\ket{0...00}+\alpha_{0...01}\ket{0...01}+...+\alpha_{1...11}\ket{1...11}.$

In classical simulation of quantum computation, each amplitude is a double-
precision complex number, which is a 16-byte data type. Thus, storing the full
state vector of an n-qubit quantum system require $2^{n+4}$ bytes.

General single-qubit gates and two-qubit controlled gates are known to be
universal [15]. Applying a quantum single-qubit gate $U$ to the $k\text{-th}$
qubit can be represented by a unitary transformation

$A=I\otimes I\otimes...\otimes U\otimes...\otimes I\otimes I$

where $I$ is $2\times 2$ identity matrix, and U is $2\times 2$ unitary matrix,

$U=\begin{bmatrix}u_{11}&u_{12}\\\ u_{21}&u_{22}\end{bmatrix}.$

However, we do not need to build the entire unitary matrix $A$ to perform the
gate operation. Figure 1 shows an example of applying a single-qubit gate to a
two-qubit system. Applying a gate $U$ to the first qubit is equivalent to
applying the $2\times 2$ unitary matrix to every pair of amplitudes, whose
subscript indices have 0 and 1 in the first bit, and all remaining bits are
the same. In the same way, performing a single-qubit gate to the second qubit
is to apply the unitary to every pair of amplitudes whose subscript indices
differ in the second bit. More extensively, applying a single-qubit gate to
the $k\text{-th}$ qubit of $n$-qubit quantum system is to apply the unitary to
every pair of amplitudes whose subscript indices have 0 and 1 in the
$k\text{-th}$ bit, while all other bits remain the same.

$\begin{bmatrix}\alpha^{\prime}_{*...*0_{k}*...*}\\\
\alpha^{\prime}_{*...*1_{k}*...*}\end{bmatrix}=\begin{bmatrix}u_{11}&u_{12}\\\
u_{21}&u_{22}\end{bmatrix}\begin{bmatrix}\alpha_{*...*0_{k}*...*}\\\
\alpha_{*...*1_{k}*...*}\end{bmatrix}$

As for a generalized two-qubit controlled gate, the unitary is applied to a
target qubit $t$, if the control qubit $c$ is set to $\ket{1}$; otherwise
$t\text{-th}$ is unmodified.

$\begin{bmatrix}\alpha^{\prime}_{*1_{c}...*0_{t}*...*}\\\
\alpha^{\prime}_{*1_{c}...*1_{t}*...*}\end{bmatrix}=\begin{bmatrix}u_{11}&u_{12}\\\
u_{21}&u_{22}\end{bmatrix}\begin{bmatrix}\alpha_{*1_{c}...*0_{t}*...*}\\\
\alpha_{*1_{c}...*1_{t}*...*}\end{bmatrix}$

In quantum information theory, _fidelity_ is a measure of distance between two
quantum states. In this paper, we only consider pure states, so the definition
of fidelity reduces to

$F(\rho,\sigma)=\braket{\psi_{\rho}}{\psi_{\sigma}}.$

For any $\rho$ and $\sigma$, $0\leq F(\rho,\sigma)\leq 1$, and
$F(\rho,\rho)=1$.

##  III Amplitude-Aware Lossy Compression

We analyze the operations of the quantum circuit simulation, and notice that
the gate operation can be performed separately pair by pair as described in
Section II. This finding allow us to divide the whole state vector into
several strides $(s_{1},s_{2},...,s_{n})$, and all the strides are stored in
the compressed format on the memory, so that we can reduce the memory
requirement for storing the state vector. The pseudo-code of the simulation
process is shown in Algorithm 1. The simulation of a quantum program is
processed gate by gate. When a gate is applied to the quantum state, only the
stride, $s_{j}$, under processing can be decompressed, and the unitary
computation is performed on the decompressed stride, and then the stride is
compressed. This is a complete operation cycle for a stride. After a stride is
finished, we process the next stride.

Algorithm 1 Quantum state vector stride update.

1: for gate $U_{i}$ in the program do

2: for stride $s_{j}$ in the state vector do

3: decompress($s_{j}$)

4: gateComputation($U_{i},s_{j}$)

5: compress($s_{j}$)

6: end for

7: end for

Figure 2: Compression ratio results of QFT quantum circuit simulation.

The straightforward idea is to apply lossless compression to the state vector.
We leverage Zstandard (zstd) library [11] as the lossless compression
technique, and get a good compression ratio in the beginning of a quantum
program simulation because most of the amplitudes in the initial state vector
are zero, which is good for data compression. However, when a high complexity
quantum program runs on the simulator, as more gate operations are performed,
more and more non-zero amplitudes are generated in the state vector. As a
result, the compression ratio is low in the end. Figure 2 shows the
compression ratio results from the Quantum Fourier Transform (QFT) circuit
simulation, which consists of 26 qubits and 1710 quantum gates. In the first
400 gates, the compression ratio of the state vector can achieve 8192.
However, after 1600 gates, the compression ratio is less than 2, and the
minimal compression ratio is only 1.02. The minimal compression ratio is the
most important metric to evaluate the memory requirement of the quantum
circuit simulation. Thus, we have to improve the minimal compression ratio.

To improve the compression ratio, we introduce SZ lossy data compression
technique [12, 13, 14] into our simulation framework. SZ allows users to set
an error bound, $\delta$, for the compression. The decompressed data
$D^{\prime}_{i}$ might differ from the original data $D^{\prime}_{i}$ but must
be in the range $[D_{i}-\delta,D_{i}+\delta]$. Since lossy compression
introduces compression errors into the state vector, the sum of the square of
the amplitudes is no longer to be 1. To reduce the error propagation, the
state vector is normalized before the gate computation.

We carefully examine the impact of compression errors on the simulation
result, and trade the data accuracy for the data reduction. As shown in Figure
2, the minimum compression ratio with SZ lossy compressor is 5.68 and the
state fidelity is 99.34%. In addition, we can increase the error bound to get
8.02 compression ratio with 46.92% state fidelity. However, the fidelity
should be improved so that the simulation results can be useful for quantum
algorithm development.

Our Amplitude-Aware Lossy Compression (AALC) technique is designed for further
optimizing the minimal compression ratio and the state fidelity. The improved
version of the simulation framework with AALC is shown in Algorithm 2. Instead
of using a fixed error bound, AALC sets different levels of error bounds, and
also sets a threshold for the minimal compression ratio. When the compression
ratio is great than the threshold, AALC uses the lowest error bound (lossless
compression) for the state vector compression. If the compression ratio is
less than the threshold, AALC re-compresses the state vector again with the
next level of error bound.

Algorithm 2 Quantum circuit simulation with AALC.

1: $\Delta=\delta_{0},\delta_{1},\delta_{2},...,\delta_{n}$

2: $\theta$: compression ratio threshold

3: for gate $U_{i}$ in the program do

4: for stride $s_{j}$ in the state vector do

5: decompress($s_{j}$)

6: normalize($s_{j}$)

7: gateComputation($U_{i},s_{j}$)

8: for $\delta_{k}$ in $\delta_{0},...,\delta_{n}$ do

9: ratio = compress($\delta_{k},s_{j}$)

10: if ratio $\geq\theta$ then

11: break

12: end if

13: end for

14: end for

15: end for

##  IV Experimental Results

(a) Threshold $\theta=4$.

(b) Threshold $\theta=8$.

(c) Threshold $\theta=16$.

(d) Threshold $\theta=32$.

Figure 3: Compression ratio results of QFT quantum circuit simulation with
AALC.

To test the effectiveness of our AALC, we construct a set of error bounds to
compress the state vector efficiently and perform the simulation with
different compression ratio thresholds. We report the experimental results of
QFT. QFT is a fundamental function of several quantum algorithms [16, 17, 18,
19]. Figure 3 shows the compression results with compression ratio threshold
$\theta=4,8,16,\text{and }32$. All the compression ratios of each simulation
are above the threshold.

Figure 4 shows the final state fidelity results with AALC and without AALC.
When we only use the fixed error bound for the lossy compression approach, the
fidelity is 99.34% when the compression ratio is above 4. However, the
fidelity drops to 46.92% when we use a larger error bound such that the
compression ratio is above 8. The fidelity is only 0.05% when the compression
ratio threshold is 16. With our AALC technique, the fidelity results are
99.98% and 99.96% for the thresholds $\theta=4\text{ and }\theta=8$,
respectively. The most significant result is that while the compression
threshold is 16, the state fidelity is 99.95%. When the threshold is 32, the
fidelity drops to 14.57%. This is because the error bound is too large such
that the important quantum information is not maintained properly in the state
amplitude vector.

Figure 4: Fidelity results of QFT quantum circuit simulation.

The simulation time is shown in Figure 5. Since our approach introduces the
processes of data compression and decompression into the simulation, the run-
time overhead comparing between no compression and AALC is from 11 to 32
times. For AALC, the higher threshold needs more time to complete the
simulation because it has to test several error bounds to find the suitable
one to exceed the threshold.

Figure 5: Simulation run-time of QFT quantum circuit simulation.

QFT generates a lot of non-zero amplitudes, and there is no rule for the
distribution of the amplitudes. Hence, amplitudes generated by QFT are hard to
compress. QFT is a worst-case scenario for our approach. Let us see the
effectiveness of AALC on another quantum algorithm. Grover’s search algorithm
is one of the most famous quantum algorithms. In the simulation of Grover’s
search algorithm, most of the state amplitudes are the same value. Such state
vectors allow the our AALC approach to perform high compression ratios. In our
Grover’s search benchmark (30 qubits), the minimum compression ratio is 445144
(Figure 6). The state fidelity is 99.75%, and the simulation run-time overhead
is 19 times in this experiment. This result suggests that using compression
technique in some specific quantum circuit simulation may give us the chance
to increase the simulation size significantly. For example, the compression,
445144, allows us to increase 18 ($\lfloor{log_{2}445144}\rfloor$) qubits for
Grover’s search algorithms simulation.

Figure 6: Compression ratio results of Grover’s search algorithm simulation
with AALC.

##  V Discussion and Future Directions

For general-purpose circuit simulation, AALC is able to reduce the data size
to 1/16. The reduction of memory requirement suggests that we could increase
the size of the quantum circuit simulation by 4 qubits comparing to the
simulation without our AALC approach. For some specific quantum circuits, like
Grover’s search, our experimental results show that we could increase the
simulation size by 18 qubits. In the previous work, it is impossible for full
amplitude vector update simulators to validate the quantum algorithms using
more than 49 qubits. In this paper, we propose a quantum circuits simulation
technique to simulate more qubits than previously reported by using amplitude-
aware lossy data compression. We trade computation power for memory space, and
we further trade data accuracy for higher compression ratio.

Our ongoing work is to improve the integration of AALC and Intel-QS running on
Argonne supercomputer system, Theta. Theta has 0.8 petabytes memory and is
able to simulate a 45-qubit quantum computation. With our AALC approach, we
expect to run 63-qubit Grover’s search algorithm simulation and 49-qubit
general quantum algorithms.

To further improve the simulation size, we need to maximize the compression
ratio. It is essential to build a new type of compression algorithm for
quantum state amplitudes. We plan to further improve AALC by introducing new
type of lossy compression algorithm. This may take more steps to complete the
compression and decompression, but we will be able to simulate the quantum
circuit that we originally cannot simulate.

The run-time performance of AALC is limited by the iteration of searching for
the proper error bound. If we have a good prediction model, then the process
of trying different error bounds can be reduced significantly. In fact, the
gate operation provides a prediction direction. For example, X, CNOT, and
toffoli gates do not change the value of the amplitudes, and they only change
the order of the amplitudes. Since this permutation does not affect the
compression ratio significantly, we could safely use the error bound in the
previous cycle for the current state vector to get similar compression ratio.
In this way, we can save time to search the error bound. In addition, we do
not need to compress every stride if the compression ratio is much higher than
the compression threshold. In this situation, only a portion of the state
vector needs to be compressed to fit in the memory requirement. There are a
lot of opportunities for us to further improve the run-time performance of
AALC.

The enhanced error bound selection algorithm not only improves the run-time
performance but also increase the state fidelity substantially. From the
current compression ratio results, we notice that sometime the compression
ratio is “too good”. This means the selected error bound is too large, and we
can actually choose a smaller error bound such that the compression ratio is
still above the threshold. If there exists an oracle that always returns the
smallest error bound which allows the compression ratio to be still above the
threshold, then we can minimize the error impact on the state fidelity.

##  VI Acknowledgments

This research used resources of the Argonne Leadership Computing Facility,
which is a DOE Office of Science User Facility supported under Contract DE-
AC02-06CH11357. This research was supported by the Exascale Computing Project
(ECP), Project Number: 17-SC-20-SC, a collaborative effort of two DOE
organizations - the Office of Science and the National Nuclear Security
Administration, responsible for the planning and preparation of a capable
exascale ecosystem, including software, applications, hardware, advanced
system engineering and early testbed platforms, to support the nation’s
exascale computing imperative. The material was supported by the U.S.
Department of Energy, Office of Science, and supported by the National Science
Foundation under Grant No. 1619253. This work is funded in part by EPiQC, an
NSF Expedition in Computing, under grant CCF-1730449. This work is also funded
in part by NSF PHY-1818914 and a research gift from Intel.

## References

  * [1] K. De Raedt, K. Michielsen, H. De Raedt, B. Trieu, G. Arnold, M. Richter, T. Lippert, H. Watanabe, and N. Ito, “Massively parallel quantum computer simulator,” _Computer Physics Communications_ , vol. 176, no. 2, pp. 121–136, 2007.
  * [2] M. Smelyanskiy, N. P. Sawaya, and A. Aspuru-Guzik, “qhipster: the quantum high performance software testing environment,” _arXiv preprint arXiv:1601.07195_ , 2016.
  * [3] T. Häner and D. S. Steiger, “0.5 petabyte simulation of a 45-qubit quantum circuit,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_. ACM, 2017, p. 33.
  * [4] E. Bernstein and U. Vazirani, “Quantum complexity theory,” _SIAM Journal on computing_ , vol. 26, no. 5, pp. 1411–1473, 1997.
  * [5] I. L. Markov and Y. Shi, “Simulating quantum computation by contracting tensor networks,” _SIAM Journal on Computing_ , vol. 38, no. 3, pp. 963–981, 2008\.
  * [6] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, and R. Wisnieff, “Breaking the 49-qubit barrier in the simulation of quantum circuits,” _arXiv preprint arXiv:1710.05867_ , 2017\.
  * [7] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, and H. Neven, “Simulation of low-depth quantum circuits as complex undirected graphical models,” _arXiv preprint arXiv:1712.05384_ , 2017.
  * [8] Z.-Y. Chen, Q. Zhou, C. Xue, X. Yang, G.-C. Guo, and G.-P. Guo, “64-qubit quantum circuit simulation,” _Science Bulletin_ , 2018.
  * [9] J. Chen, F. Zhang, M. Chen, C. Huang, M. Newman, and Y. Shi, “Classical simulation of intermediate-size quantum circuits,” _arXiv preprint arXiv:1805.01450_ , 2018.
  * [10] M. A. Nielsen and I. Chuang, “Quantum computation and quantum information,” 2002\.
  * [11] Y. Collet, “Zstandard - real-time data compression algorithm,” _http://facebook.github.io/zstd/_ , 2015.
  * [12] D. T. Z. C. F. C. Xin Liang, Sheng Di, “Efficient transformation scheme for lossy data compression with point-wise relative error bound,” in _CLUSTER_. IEEE, 2018.
  * [13] D. Tao, S. Di, Z. Chen, and F. Cappello, “Significantly improving lossy compression for scientific data sets based on multidimensional prediction and error-controlled quantization,” in _Parallel and Distributed Processing Symposium (IPDPS), 2017 IEEE International_. IEEE, 2017, pp. 1129–1139.
  * [14] S. Di and F. Cappello, “Fast error-bounded lossy hpc data compression with sz,” in _2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 2016, pp. 730–739.
  * [15] D. P. DiVincenzo, “Two-bit gates are universal for quantum computation,” _Physical Review A_ , vol. 51, no. 2, p. 1015, 1995.
  * [16] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” _SIAM review_ , vol. 41, no. 2, pp. 303–332, 1999.
  * [17] A. Y. Kitaev, “Quantum measurements and the abelian stabilizer problem,” _arXiv preprint quant-ph/9511026_ , 1995.
  * [18] M. Mosca and A. Ekert, “The hidden subgroup problem and eigenvalue estimation on a quantum computer,” in _Quantum Computing and Quantum Communications_. Springer, 1999, pp. 174–188.
  * [19] M. Ettinger, P. Hoyer, and E. Knill, “The quantum query complexity of the hidden subgroup problem is polynomial,” _arXiv preprint quant-ph/0401083_ , 2004.


# Open-DDVM: A Reproduction and Extension of Diffusion Model for Optical Flow
Estimation

Qiaole Dong
School of Data Science, Fudan University
<EMAIL_ADDRESS>
&Bo Zhao
Beijing Academy of Artificial Intelligence
<EMAIL_ADDRESS>
Yanwei Fu
School of Data Science, Fudan University
<EMAIL_ADDRESS>

###### Abstract

Recently, Google proposes DDVM [14] which for the first time demonstrates that
a general diffusion model for image-to-image translation task works
impressively well on optical flow estimation task without any specific designs
like RAFT [20]. However, DDVM is still a closed-source model with the
expensive and private Palette-style pretraining. In this technical report, we
present the first open-source DDVM by reproducing it. We study several design
choices and find those important ones. By training on 40k public data with 4
GPUs, our reproduction achieves comparable performance to the closed-source
DDVM. The code and model have been released in
https://github.com/DQiaole/FlowDiffusion_pytorch.

##  1 Introduction

Optical flow is a fundamental modality in computer vision, which provides key
information for various real-world applications, _e.g._ , video frame
interpolation [8], video inpainting [3], and action recognition [19]. Optical
flow estimation aims to estimate a per-pixel displacement vector field between
two consecutive video frames. Previous optical flow estimation methods [9, 23,
18, 2, 7] have achieved remarkable progress based on the successful
architecture of Recurrent All-Pairs Field Transforms (RAFT) [20], which
iteratively updates a flow field with GRU-based operator. Recently, denoising
diffusion probabilistic models [6] have emerged as novel method for
distribution modelling. Saxen et al. for the first time apply diffusion model
for optical flow estimation and achieve impressively good performance as
introduced in DDVM [14].

DDVM [14] takes a noisy version of the optical flow as input and concatenates
two RGB images as the condition. It employs the Efficient U-Net [13]
architecture to predict the noise-free estimation of the 2-channel optical
flow, with the training loss penalizing residual error in the denoised map.
Besides, to train a generic diffusion model for optical flow estimation
without task-specific inductive biases, DDVM utilizes massively synthetic
datasets, including AutoFlow [16], FlyingThings3D [10], TartanAir [22], and
Kubric [5]. Additionally, DDVM requires a Palette-style [12] pretraining on
huge image datasets. During inference, it employs a strategy called coarse-to-
fine for high-resolution input, which refines the noised estimation in a
patch-wise manner based on coarse results from resized low-resolution images.
For more details about DDVM, please refer to the original paper [14].

As mentioned above, training a generic diffusion model for optical flow
estimation without task-specific inductive biases necessitates massive
synthetic datasets and a longer training process. In this paper, we make a
preliminary study and propose to take advantage of multi-scale correlation
volume as a prior for optical flow estimation inspired by classic work [20].
As shown in Fig. 1, we first extract the feature for two input images on 1/8
resolution by a simple ResNet. We then construct a 4-layer multi-scale
correlation volume through matrix multiplication and average pooling. We also
perform lookups operation defined in RAFT [20] on the 4D correlation volume
with the current noised flow, which results in a single feature map containing
all local correlation information. Our U-Net accepts both 8-channel tensors
(two 3-channel RGB images and one 2-channel noised flow) and the correlation
feature as input. Specifically, the U-Net encodes the 8-channel tensor and
concatenates with the correlation feature map at 1/8 resolution of the U-Net
encoder. The denoised optical flow is predicted through a decoder part
network. We train the whole U-Net similarly as in DDVM [14].

Figure 1: Overview of our correlation-volume assisted diffusion model for
optical flow estimation.

##  2 Experiments

#### Dataset and Implementation Details.

We train our model on AutoFlow [16] dataset of 320x448 resolution, which
consists of 40k synthetic image pairs and ground-truth optical flow. Following
previous works [20, 14], we evaluate the zero-shot performance of our model on
the synthetic Sintel [1] and real-world KITTI [4] datasets. We adopt the
Efficient U-Net architecture [13] as our backbone network, without the
Palette-style pretraining. The batch-size is 64. AdamW is utilized as the
default optimizer. We also enable the exponential-moving-average (EMA) during
model training. We train the denoising U-Net with DDPM model [6] of 64 steps
on four NVIDIA A800 GPUs. Besides, to ease the memory requirement and speed up
the training process, we utilize DeepSpeed [11] and mixed precision training
with data type bf16 [21]. We initialize our learning rate with $1\times
10^{-4}$ and half the learning rate when encountering an unstable training
stage due to mixed precision training.

###  2.1 Ablation Study

In this subsection, we determine several important factors for training the
diffusion model for optical flow estimation.

#### Normalization.

As shown in the left part of Tab. 1, normalizing the input and output into the
range of $[-1,1]$ using the height and width of input can greatly improve the
zero-shot performance. Besides, we also observe that normalization helps
stabilize the training process with more smoother loss curve.

#### Augmentation.

We compare the data augmentation operations from RAFT [20], including
photometric and geometric augmentation, with the one from RAFT-it [15]. We
find that utilizing data augmentation from RAFT-it [15], which is also used in
DDVM [14], can boost the performance, as shown in Tab. 1.

#### Noise Augmentation.

We further study the Gaussian noise augmentation in this experiment. Prior
work like PWC-Net [17] observed that training without Gaussian noise can
improve the performance of PWC-Net, while recent RAFT-it [15], which focuses
on improving the training process of optical flow estimation models, employs
the Gaussian noise augmentation. In our experiment shown in Tab. 1, we find
that Gaussian noise augmentation causes little difference. However, we find
that adding noise can stabilize the model training. Thus, we follow the
augmentation from RAFT-it in our later experiments.

#### Refinement.

DDVM [14] performs inference in a coarse-to-fine manner. It first estimates
the flow over the entire field of view at low resolution. It then up-samples
the flow to the original resolution as $f$ and runs forward diffusion to an
intermediate time step $T$, getting a noised flow. Finally, it denoises the
flow in a patch-wise manner and merges the patches. However, we find that
setting $T\geq 2$ will result in local inconsistency in the final denoised
flow, as shown in Fig. 2. Setting $T=1$ can improve the performance as
expected, shown in Tab. 1 and Fig. 2. Therefore, we propose another refinement
method, called warp-refine. Specifically, we first backward the second image
with up-sampled coarse flow. We then estimate the residual flow between the
warped image and the first image in a patch-wise manner with a small amount of
time steps. As shown in Tab. 1 and Fig. 2, our warp-refine can improve the
performance and capture more fine details.

Table 1: _Left_ : Ablation studies on AutoFlow [16]. We evaluate the models on the downsampled KITTI-15 training set of 320x448 resolution and report the end-point-error (EPE). _Right_ : Ablation studies of refinement on the KITTI-15 training set with model trained on AutoFlow. The time step indicates the number of steps used during the refinement stage. The parameters used in our final model are underlined. | Experiment | Method | KITTI-15
---|---|---
_Training: 20k on AutoFlow_
Normalize Flow | No | 15.8
Yes | 7.4
_Training: 100k on AutoFlow_
Augmentation | RAFT [20] | 5.2
RAFT-it [15] | 3.4
Noise Augmentation | No | 3.5
Yes | 3.4
|  | Time Step | EPE | Fl-all
---|---|---|---
Without | - | 5.57 | 20.22%
Coarse-to-fine [14] | T = 8 | 27.60 | 58.65%
T=1 | 5.53 | 19.67%
Warp-refine | T=8 | 5.54 | 18.54%
T=4 | 5.44 | 18.57%
Figure 2: Qualitative comparison with Coarse-to-fine refinement [14] on
KITTI-15. Our proposed Warp-refine performs better in maintaining the whole
coarse structure and refining the fine details. However, we find that Coarse-
to-fine refinement with 2 steps already introduces inconsistent noise into the
final optical flow. Here $T$ represents the total steps used during the
refinement stage.

###  2.2 Optical Flow Estimation Results

In this section, we report the zero-shot optical flow estimation performance
on Sintel and KITTI-15 when trained on AutoFlow. We also report the results of
DDVM with Palette-style pretraining as in Tab. 2. Our reproduced model trained
from the scratch with 900k iterations on AutoFlow results in an EPE of 3.76 in
Sintel Final pass and a Fl-all of 18.57% in KITTI-15, as shown in the third
line of Tab. 2. Besides, our modified network based on a simple correlation
volume as introduced in Fig. 1 indeed performs better than the original
network with the same iteration. With only 1/3 iterations, our correlation
volume based diffusion model can even approach the performance of the original
diffusion model with 900k iterations. We believe that introducing more
sophisticated inductive biases into simple U-Net can further improve the
performance and speed up the training of the diffusion model for optical flow
estimation in the future.

Table 2: Zero-shot optical flow estimation results on Sintel and KITTI-15 training set. All models are trained on AutoFlow [16]. | Pretraining | Network | Iteration | Sintel.clean | Sintel.final | KITTI EPE | KITTI Fl-all
---|---|---|---|---|---|---|---
DDVM [14] | Palette-style | Efficient U-Net | Unknow | 2.04 | 2.55 | 4.47 | 16.59%
Ours | From the Scratch | Efficient U-Net | 305k | 2.96 | 3.97 | 6.21 | 20.38%
Ours | From the Scratch | Efficient U-Net | 900k | 2.77 | 3.76 | 5.44 | 18.57%
Ours | From the Scratch | Efficient U-Net + Corr. Volume | 305k | 2.98 | 3.85 | 5.53 | 19.04%

##  3 Conclusion

In this technical report, we reproduce the DDVM and contribute the first open-
source diffusion model for optical flow estimation. With limited resources,
our reproduced DDVM achieves comparable performance to the original one. Our
experiments reveal that some specific designs, such as employing correlation
volume from prior optical flow models, are important for accurate optical flow
estimation. We hope this open-source model can advance the research of optical
flow estimation.

## References

  * [1] Daniel J Butler, Jonas Wulff, Garrett B Stanley, and Michael J Black.  A naturalistic open source movie for optical flow evaluation.  In European conference on computer vision, pages 611–625. Springer, 2012.
  * [2] Qiaole Dong, Chenjie Cao, and Yanwei Fu.  Rethinking optical flow from geometric matching consistent perspective.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1337–1347, 2023.
  * [3] Chen Gao, Ayush Saraf, Jia-Bin Huang, and Johannes Kopf.  Flow-edge guided video completion.  In European Conference on Computer Vision, pages 713–729. Springer, 2020.
  * [4] Andreas Geiger, Philip Lenz, and Raquel Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In 2012 IEEE conference on computer vision and pattern recognition, pages 3354–3361. IEEE, 2012.
  * [5] Klaus Greff, Francois Belletti, Lucas Beyer, Carl Doersch, Yilun Du, Daniel Duckworth, David J Fleet, Dan Gnanapragasam, Florian Golemo, Charles Herrmann, et al.  Kubric: A scalable dataset generator.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3749–3761, 2022.
  * [6] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  Advances in neural information processing systems, 33:6840–6851, 2020.
  * [7] Zhaoyang Huang, Xiaoyu Shi, Chao Zhang, Qiang Wang, Ka Chun Cheung, Hongwei Qin, Jifeng Dai, and Hongsheng Li.  Flowformer: A transformer architecture for optical flow.  arXiv preprint arXiv:2203.16194, 2022.
  * [8] Huaizu Jiang, Deqing Sun, Varun Jampani, Ming-Hsuan Yang, Erik Learned-Miller, and Jan Kautz.  Super slomo: High quality estimation of multiple intermediate frames for video interpolation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 9000–9008, 2018.
  * [9] Shihao Jiang, Dylan Campbell, Yao Lu, Hongdong Li, and Richard Hartley.  Learning to estimate hidden motions with global motion aggregation.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9772–9781, 2021.
  * [10] Nikolaus Mayer, Eddy Ilg, Philip Hausser, Philipp Fischer, Daniel Cremers, Alexey Dosovitskiy, and Thomas Brox.  A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4040–4048, 2016.
  * [11] Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He.  Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3505–3506, 2020.
  * [12] Chitwan Saharia, William Chan, Huiwen Chang, Chris Lee, Jonathan Ho, Tim Salimans, David Fleet, and Mohammad Norouzi.  Palette: Image-to-image diffusion models.  In ACM SIGGRAPH 2022 Conference Proceedings, pages 1–10, 2022.
  * [13] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  Advances in Neural Information Processing Systems, 35:36479–36494, 2022.
  * [14] Saurabh Saxena, Charles Herrmann, Junhwa Hur, Abhishek Kar, Mohammad Norouzi, Deqing Sun, and David J Fleet.  The surprising effectiveness of diffusion models for optical flow and monocular depth estimation.  arXiv preprint arXiv:2306.01923, 2023.
  * [15] Deqing Sun, Charles Herrmann, Fitsum Reda, Michael Rubinstein, David J Fleet, and William T Freeman.  Disentangling architecture and training for optical flow.  In European Conference on Computer Vision, pages 165–182. Springer, 2022.
  * [16] Deqing Sun, Daniel Vlasic, Charles Herrmann, Varun Jampani, Michael Krainin, Huiwen Chang, Ramin Zabih, William T Freeman, and Ce Liu.  Autoflow: Learning a better training set for optical flow.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10093–10102, 2021.
  * [17] Deqing Sun, Xiaodong Yang, Ming-Yu Liu, and Jan Kautz.  Models matter, so does training: An empirical study of cnns for optical flow estimation.  IEEE transactions on pattern analysis and machine intelligence, 42(6):1408–1423, 2019.
  * [18] Shangkun Sun, Yuanqi Chen, Yu Zhu, Guodong Guo, and Ge Li.  Skflow: Learning optical flow with super kernels.  arXiv preprint arXiv:2205.14623, 2022.
  * [19] Shuyang Sun, Zhanghui Kuang, Lu Sheng, Wanli Ouyang, and Wei Zhang.  Optical flow guided feature: A fast and robust motion representation for video action recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1390–1399, 2018.
  * [20] Zachary Teed and Jia Deng.  Raft: Recurrent all-pairs field transforms for optical flow.  In European conference on computer vision, pages 402–419. Springer, 2020.
  * [21] Paul Teich.  Tearing apart google’s tpu 3.0 ai coprocessor.  High Point: Stackhouse Publishing Inc, 2018.
  * [22] Wenshan Wang, Delong Zhu, Xiangwei Wang, Yaoyu Hu, Yuheng Qiu, Chen Wang, Yafei Hu, Ashish Kapoor, and Sebastian Scherer.  Tartanair: A dataset to push the limits of visual slam.  In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4909–4916. IEEE, 2020.
  * [23] Zihua Zheng, Ni Nie, Zhi Ling, Pengfei Xiong, Jiangyu Liu, Hao Wang, and Jiankun Li.  Dip: Deep inverse patchmatch for high-resolution optical flow.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8925–8934, 2022.