Kangyeol Kim*kangyeolk@kaist.ac.kr1,7 Sunghyun Park*†psh01087@kaist.ac.kr1,2
Junsoo<EMAIL_ADDRESS>Joonseok Leejoonseok2010@gmail.com4,5
Sookyung<EMAIL_ADDRESS>Jaegul Choojchoo@kaist.ac.kr1,7 Edward
<EMAIL_ADDRESS>KAIST AI
Korea Kakao Enterprise
Korea Naver Webtoon
Korea Seoul National University
Korea Google Research
United States Xerox PARC
United States Letsur Inc.
Korea Continuous-Time Video Generation

# Continuous-Time Video Generation via
Learning Motion Dynamics with Neural ODE

###### Abstract

In order to perform unconditional video generation, we must learn the
distribution of the real-world videos. In an effort to synthesize high-quality
videos, various studies attempted to learn a mapping function between noise
and videos, including recent efforts to separate motion distribution and
appearance distribution. Previous methods, however, learn motion dynamics in
discretized, fixed-interval timesteps, which is contrary to the continuous
nature of motion of a physical body. In this paper, we propose a novel video
generation approach that learns separate distributions for motion and
appearance, the former modeled by neural Ordinary Differential Equation (ODE)
to learn natural motion dynamics. Specifically, we employ a two-stage approach
where the first stage converts a noise vector to a sequence of keypoints in
arbitrary frame rates, and the second stage synthesizes videos based on the
given keypoints sequence and the appearance noise vector. Our model not only
quantitatively outperforms recent baselines for video generation, but also
demonstrates versatile functionality such as dynamic frame rate manipulation
and motion transfer between two datasets, thus opening new doors to diverse
video generation applications.

##  1 Introduction

Creating realistic videos from scratch (i.e., unconditional video generation
(UVG)) requires the model to learn the distribution of the video data. In
other words, we are essentially learning a density function from which we can
sample unseen videos. This is typically achieved by employing an adversarial
training framework, thanks to the advances in deep generative models where
GAN-based approaches have shown impressive performance in static image
generation [Karras et al.(2019)Karras, Laine, and Aila, Karras et
al.(2020)Karras, Laine, Aittala, Hellsten, Lehtinen, and Aila, Cho et
al.(2019)Cho, Choi, Park, Shin, and Choo, Lee et al.(2020)Lee, Tseng, Mao,
Huang, Lu, Singh, and Yang]. Video generation, however, differs from image
generation since we must consider the temporal aspect in addition to the
spatial aspect.

Initial UVG approaches tried to learn a single density function for both
temporal and spatial aspects, where based on a single noise vector, a sequence
of video frames were generated at each timestep [Saito et al.(2017)Saito,
Matsumoto, and Saito, Vondrick et al.(2016)Vondrick, Pirsiavash, and
Torralba]. Such approaches, however, were limited to generating short videos
with simple dynamics (e.g., linear motions such as moving trains). This
limitation stems most likely from failing to treat the two aspects
effectively. Specifically, a video can be decomposed into two orthogonal
elements: the motion (i.e., movement of an object(s)) and the appearance
(i.e., background, style of the object(s), etc.), where the former is
concerned with the temporal aspect, and the latter the spatial aspect.

Figure 1: A walking human and corresponding keypoints. Rigid treatment of time
as discretized, fixed-interval timesteps (the 1st and 5th steps) prevents the
model from learning the underlying motion dynamics by missing out frames at
unseen timesteps (motion in the box).

Based on this observation, a couple of recent works tried to learn separate
distributions (one for motion and another for appearance) and have shown
improved video quality as well as more natural motion dynamics [Tulyakov et
al.(2018)Tulyakov, Liu, Yang, and Kautz, Wang et al.(2020)Wang, Bilinski,
Bremond, and Dantcheva]. However, existing approaches, while separately
learning motion and appearance to some extent, fail to learn the true dynamics
of motion as they all treat videos as a sequence of frames bound by
discretized, fixed-interval timesteps. Such rigid treatment of the temporal
aspect limits the model’s capacity to learn natural motions as indicated in
Fig. 1, which eventually leads to generating videos of suboptimal quality.

In this paper, we propose Motion Ordinary Differential Equation GAN (MODE-
GAN), a novel two-stage UVG model that separately learns motion and appearance
distributions. In the first stage, the motion generator is responsible for
converting the motion noise vector to a sequence of keypoints (_i.e._ ,
representation of motion). To learn continuous-time dynamics of a physical
body, we employ a neural ODE [Chen et al.(2018)Chen, Rubanova, Bettencourt,
and Duvenaud], which is a continuous-time model by interpreting the forward
pass of the neural networks as solving an ODE. With neural ODE, our motion
generator can produce a motion in an arbitrary frame rate, which is especially
useful for generating non-linear motion dynamics (_e.g_ , sports) where higher
frame rates at certain segments can help the viewer understanding. In the
second stage, given a sequence of keypoints and an appearance noise vector,
the motion-conditioned video generator synthesizes a video sequence by
combining the two. With this two-stage approach, MODE-GAN provides full
control of the spatio-temporal aspects of the generated video, such as mixing
the motion and appearance from two different datasets. This lends more power
to the user to generate diverse videos that even may not exist in the real
world.

To sum up, MODE-GAN not only generates high-quality videos with continuous
motion dynamics, but also learns completely independent motion density
function and appearance density function. We summarize our contributions to
the domain of UVG as follows:

  * •

We present a _novel two-stage unconditional video generation framework_ MODE-
GAN, which demonstrates high-quality videos in terms of pixel distribution as
well as motion smoothness.

  * •

By employing the neural ODE to generate continuous-time motions, MODE-GAN is
able to _dynamically change the frame rate_ even when generating a single
video sample.

  * •

MODE-GAN learns completely independent density functions for motion and
appearance, enabling _disentanglement of the spatio-temporal aspects_ of the
generated video.

##  2 Related Work

Video Generation from Random Noise. The goal of unconditional video generation
is to learn a mapping function that generates a realistic video given a random
noise vector. Existing approaches tried to decompose a video into several
independent components. In an earlier study, VGAN [Vondrick et
al.(2016)Vondrick, Pirsiavash, and Torralba] decomposed a video into a
foreground object and a background during video synthesis. In addition, TGAN
[Saito et al.(2017)Saito, Matsumoto, and Saito] tried to split each frame into
a fast and slow part. MoCoGAN [Tulyakov et al.(2018)Tulyakov, Liu, Yang, and
Kautz] was the first approach to divide the video signal into appearance and
motion. Lastly, G3AN [Wang et al.(2020)Wang, Bilinski, Bremond, and Dantcheva]
proposed a three-stream video generator to promote the disentanglement of
appearance and motion to improve video quality. Our work is distinguished from
previous approaches by learning completely independent density functions for
motion and appearance where the former is modeled in continuous-time via
neural ODE. This choice or architecture enables not only improved video
quality with smooth motion dynamics in arbitrary frame rates, but also
transferring motion from one dataset to another.

Conditional Video Generation with Additional Input. Generating videos with the
additional inputs such as semantic segmentation [Wang et al.(2018)Wang, Liu,
Zhu, Liu, Tao, Kautz, and Catanzaro, Wang et al.(2019a)Wang, Liu, Tao, Liu,
Catanzaro, and Kautz, Pan et al.(2019)Pan, Wang, Jia, Shao, Sheng, Yan, and
Wang], pose keypoints [Chan et al.(2019)Chan, Ginosar, Zhou, and Efros,
Siarohin et al.(2019b)Siarohin, Lathuilière, Tulyakov, Ricci, and Sebe,
Siarohin et al.(2019a)Siarohin, Lathuilière, Tulyakov, Ricci, and Sebe]
relates to learning the marginal distributions instead of modeling the joint
distributions [Pu et al.(2018)Pu, Dai, Gan, Wang, Wang, Zhang, Henao, and
Duke]. There exist a large body of work, where given a single video frame
[Yang et al.(2018)Yang, Wang, Zhu, Huang, Shi, and Lin, Li et al.(2018b)Li,
Fang, Yang, Wang, Lu, and Yang, Kim et al.(2019)Kim, Nam, Cho, and Kim] or a
sequence of frames [Wang et al.(2019b)Wang, Jiang, Yang, Li, Long, and Fei-
Fei, Wang et al.(2019c)Wang, Zhang, Zhu, Long, Wang, and Yu, Kwon and
Park(2019)], the model predicts the in-between frames or future frames. Some
works among them are related to our work in that they predict video frames by
extracting the pose keypoints from an input image [Yang et al.(2018)Yang,
Wang, Zhu, Huang, Shi, and Lin, Kim et al.(2019)Kim, Nam, Cho, and Kim].
Although these works for conditional video generation also handle video data,
our contribution lies in learning separate density functions for motion and
appearance, rather than making predictions given an initial video frame(s).

Neural ODE. Neural ODEs [Chen et al.(2018)Chen, Rubanova, Bettencourt, and
Duvenaud] represent one of the continuous-depth deep learning models which
employ a neural network to model the dynamics (i.e., vector field) of the
latent state. Equipped with widely used numerical solvers such as Runge-Kutta
and Dormand–Prince method, neural ODE has the capacity to express the latent
state in continuous-depth, or equivalently continuous-time. The continuous
nature of neural ODE paved a way to design the continuous time-series modeling
as shown in following studies [Rubanova et al.(2019)Rubanova, Chen, and
Duvenaud, Yildiz et al.(2019)Yildiz, Heinonen, and Lahdesmaki, De Brouwer et
al.(2019)De Brouwer, Simm, Arany, and Moreau, Dupont et al.(2019)Dupont,
Doucet, and Teh, Park et al.(2020)Park, Kim, Lee, Choo, Lee, Kim, and Choi].
Latent ODE [Rubanova et al.(2019)Rubanova, Chen, and Duvenaud] introduced ODE-
RNN as an encoder and demonstrated the effectiveness of handling the time-
series data taken at non-uniform intervals. Furthermore, ODE2VAE [Yildiz et
al.(2019)Yildiz, Heinonen, and Lahdesmaki] and Vid-ODE [Park et al.(2020)Park,
Kim, Lee, Choo, Lee, Kim, and Choi] performed continuous-time video prediction
conditioned on input video frames, demonstrating the potential to apply neural
ODE to computer vision.

##  3 Method

Problem Statement. Our task is unconditionally generating a video
$\hat{\mathbf{v}}_{1:T}\in\mathbb{R}^{T\times 3\times H\times W}$ given two
noise vectors, the motion noise vector $\mathbf{z}_{m}\in{\mathcal{Z}}_{M}$
and the appearance noise vector $\mathbf{z}_{a}\in{\mathcal{Z}}_{A}$, where
$T$ denotes the number of frames, $H$ and $W$ the height and width of the
generated image, respectively.

Model Overview. We employ a two-stage approach with two separate components:
the _motion generator_ and the _motion-conditioned video generator_. Starting
from $\mathbf{z}_{m}$, the motion generator creates a sequence of keypoints,
which conveys a plausible movement of an object. Given the sequence of
keypoints and $\mathbf{z}_{a}$, the motion-conditioned video generator
synthesizes a realistic video following the geometric information in the
keypoints. In the following, we describe each stage in detail.

###  3.1 Stage I: Motion Generation

Figure 2: Overview of Stage I Motion generator creates a sequence of keypoints
representing the motion of an object. (a) Sample a noise vector
$\mathbf{z}_{m}$ from ${\mathcal{N}}(\mathbf{0},I)$. (b) $\mathbf{z}_{m}$ is
mapped to an initial point $\mathbf{h}_{0}$ via function $P$. (c) By
integrating $\mathbf{h}_{0}$ over the target timesteps
$\\{s_{1},s_{2},\ldots,s_{T}\\}$, latent states for each timestep
$\mathbf{h}_{1:T}$ are obtained. (d) Latent states are projected via function
$Q$ to a set of evolving keypoints $\hat{\mathbf{k}}_{1:T}$.

Fig. 2 depicts the overall process of motion generation via neural ODE. The
motion generator aims to learn a distribution of sequential 2D keypoints
coordinates $\mathbf{k}_{1:T}\in\mathbb{R}^{T\times K\times 2}$, where $K$
denotes the number of keypoints, beginning with a noise vector
$\mathbf{z}_{m}$ drawn from ${\mathcal{N}}(\mathbf{0},\mathbf{I})$. As an
initial step, $\mathbf{z}_{m}$ is fed into the initial value mapper $P$ to
generate the initial value $\mathbf{h}_{0}$ for the ODE solver. Integrating
over the target timesteps $\\{s_{1},s_{2},\ldots,s_{T}\\}$, the ODE solver
produces a sequence of latent states $\mathbf{h}_{1:T}$ which are then
transformed into the a sequence of keypoints
$\hat{\mathbf{k}}_{1:T}\in\mathbb{R}^{T\times K\times 2}$ via a fully
connected neural network $Q$. Overall, the motion generator is described as

$\displaystyle\mathbf{h}_{0}$ $\displaystyle=P(\mathbf{z}_{m}),$
$\displaystyle\mathbf{h}_{1},\mathbf{h}_{2},\ldots,\mathbf{h}_{T}$
$\displaystyle=\text{ODESolve}(f_{\theta},\mathbf{h}_{0},(s_{1},s_{2},\ldots,s_{T})),$
$\displaystyle\text{each}\quad\hat{\mathbf{k}}_{t}$
$\displaystyle=Q(\mathbf{h}_{t})\quad t=1,2,\ldots,T,$ (1)

where $f_{\theta}$ indicates a fully-connected neural network to approximate
$d\mathbf{h}_{t}/dt$. A straightforward way to train the motion generator is
to learn the distribution of real coordinates $\mathbf{k}_{1:T}$ via
adversarial training. However, we observed that the 2D coordinates of the
keypoints led to unstable training, and therefore used 2D Gaussian heatmaps as
an alternative representation. These $K$ Gaussian heatmaps
${\mathcal{H}}_{t}\in\mathbb{R}^{K\times H\times W}$ are obtained by utilizing
a Gaussian-like function centered at $\mathbf{k}_{t}$, which can be formulated
as

$\displaystyle{\mathcal{H}}^{(c,\mathbf{u})}_{t}=\exp\Big{(}-\frac{1}{2\sigma^{2}}\|\mathbf{u}-\mathbf{k}^{c}_{t}\|^{2}\Big{)},$
(2)

where $\mathbf{u}\in\Omega$ is the pixel coordinates and $\mathbf{k}^{c}_{t}$
indicates the coordinates of the $c$-th keypoint at time $t$.

Figure 3:  Overview of Stage II (a) Given an appearance noise vector
$\mathbf{z}_{a}$ and a sequence of Gaussian keypoint heatmaps
${\mathcal{H}}_{t}$ from Stage I, the motion-conditioned video generator $G$
synthesizes a realistic video. (b) The video generator $G$ consists of three
streams: motion (top), video (middle), and appearance (bottom). At first,
$\mathbf{z}_{a}$ is fed into a neural network to produce an appearance feature
vector, which is reshaped to an initial video feature map
$\mathbf{M}^{1}_{t}$. Afterwards, a series of $N$ up-sampling layers and
composition blocks are used to generate a single video frame at timestep $t$.
(c) In the composition block, the resized Gaussian heatmap
$\tilde{{\mathcal{H}}}^{n}_{t}$ and a projected appearance feature
$\mathbf{FC}^{n}(\mathbf{f}_{a})$ are used together to determine learnable
parameters $\alpha_{\gamma}$ and $\alpha_{\beta}$, which are applied to the
video feature $\mathbf{M}^{n}_{t}$, transforming it according to the motion
and appearance information.

Loss Function. We use an adversarial loss to minimize the discrepancy between
the distribution of the real keypoints sequences and that of the generated
ones. For this purpose, we employ two discriminators
$D^{\text{(I)}}_{\text{fr}},D^{\text{(I)}}_{\text{sq}}$, where each receives
Gaussian heatmaps in individual frame and sequence level,
respectively.111Detailed descriptions about adversarial losses are provided in
the supplementary material. Since ODE integration is solely determined by the
initial value, the initial values $\mathbf{h}_{0}$ need to be diverse in order
to generate diverse motions. To this end, we add an diversity loss of initial
value ${\mathcal{L}}^{\text{initial}}_{\text{div}}$ to enforce two different
motion noise vectors
$\mathbf{z}_{m},\mathbf{z}^{\prime}_{m}\in{\mathcal{Z}}_{M}$ to be embedded in
two different places in the initial value space.

$\displaystyle{\mathcal{L}}^{\text{initial}}_{\text{div}}=\frac{\|\mathbf{z}_{m}-\mathbf{z}^{\prime}_{m}\|_{1}}{\|P(\mathbf{z}_{m})-P(\mathbf{z}^{\prime}_{m})\|_{1}}$
(3)

The overall objective function for stage I is formulated as

$\displaystyle\min_{P,Q,f_{\theta}}\max_{D^{\text{(I)}}_{\text{fr}},D^{\text{(I)}}_{\text{sq}}}{\mathcal{L}}^{\text{(I)}}_{\text{adv}}+\lambda^{\text{initial}}_{\text{div}}{\mathcal{L}}^{\text{initial}}_{\text{div}},$
(4)

where ${\mathcal{L}}^{\text{(I)}}_{\text{adv}}$ denotes the adversarial loss
for stage I and $\lambda^{\text{initial}}_{\text{div}}$ is a hyperparamter
controlling the relative importance between the two losses.

###  3.2 Stage II: Motion Conditioned Video Generation

As shown in Fig. 3(a), given a series of keypoints represented as Gaussian
heatmaps ${\mathcal{H}}_{1:T}$, the motion-conditioned video generator $G$
synthesizes a video $\hat{\mathbf{v}}_{1:T}$ where the object follows the
geometric information of the keypoints sequence. Inspired by G3AN [Wang et
al.(2020)Wang, Bilinski, Bremond, and Dantcheva], we use three parallel
streams: a motion stream, a video stream, and an appearance stream. The three
streams undergo $N$ number of upsample-then-compose blocks to generate the
final video, as depicted in Fig. 3(b). Specifically, the appearance noise
vector $\mathbf{z}_{a}$ sampled from ${\mathcal{N}}(\mathbf{0},I)$ is fed into
a fully-connected neural network to produce an appearance feature vector
$\mathbf{f}_{a}\in\mathbb{R}^{L}$, used mainly in the appearance stream to
inject appearance information to the video stream. In the video stream, the
initial video feature map
$\mathbf{M}^{1}_{1:T}\in\mathbb{R}^{\frac{L}{4}\times T\times 2\times 2}$ is
obtained by reshaping $\mathbf{f}_{a}$, then stacking it across the time axis.
In our implementation, we sequentially upsample the feature map from the
initial resolution $2\times 2$ to the final resolution. The motion stream
injects the motion information from the Gaussian heatmaps into the video
stream where at each injection, the $H\times W$ resolution heatmaps are
resized to the spatial size of $\mathbf{M}^{n}_{1:T}$, enabling the model to
consider the motion information in multi-scale. The injection of appearance
and motion information is conducted inside the composition block.

Composition Block. The composition block takes three inputs $\mathbf{f}_{a}$
(appearance feature vector), $\mathbf{M}^{n}_{1:T}$ (video feature map),
$\tilde{{\mathcal{H}}}^{n}$ (resized Gaussian heatmaps), and combines them via
spatially adaptive denormalization [Park et al.(2019)Park, Liu, Wang, and Zhu]
by estimating scale $\gamma$ and shift parameters $\beta$, and produces
$\mathbf{M}^{n+1}_{1:T}$. It consists of standardization over all frames
(i.e., batch size $\times$ $T$ dimension) followed by an adaptive scaling and
shift. Let $(B,C_{n},H_{n},W_{n})$ be the number of frames, the channel
dimension, height and the width of $\mathbf{M}^{n}_{1:T}$. Then, the
transformed activation value at each site ($b\in B,c\in C_{n},i\in H_{n},j\in
W_{n}$) is given by

$\displaystyle\gamma_{c,i,j}(\mathbf{f}_{a},\tilde{{\mathcal{H}}}^{n})\frac{o_{b,c,i,j}-\mu_{c}}{\sigma_{c}}+\beta_{c,i,j}(\mathbf{f}_{a},\tilde{{\mathcal{H}}}^{n}),$
(5)

where $o_{b,c,i,j}$ is an activation value at the site before transformation,
the scale and shift parameters $\gamma_{c,i,j},\beta_{c,i,j}$ are weighted
sums of motion and appearance information obtained from
$\mathbf{FC}^{n}(\mathbf{f}_{a})$ and $\tilde{{\mathcal{H}}}_{t}^{n}$, and
$\mu_{c},\sigma_{c}$ are the mean and standard deviation of
$\mathbf{M}^{n}_{1:T}$ along channel $c$, respectively (See Fig. 3(c) for
details).

Loss Function. The motion-conditioned video generator aims at generating a
realistic video retaining the motion information from
${\mathcal{H}}_{1:T}$.222Detailed descriptions about adversarial losses are
provided in the supplementary material. In addition, we employ the pixel-level
diversity loss to make output videos distinctive given two different
appearance noise vectors
$\mathbf{z}_{a},\mathbf{z}^{\prime}_{a}\in{\mathcal{Z}}_{A}$.

$\displaystyle{\mathcal{L}}^{\text{pixel}}_{\text{div}}=\frac{\|\mathbf{z}_{a}-\mathbf{z}^{\prime}_{a}\|_{1}}{\|G(\mathbf{z}_{a};{\mathcal{H}}_{1:T})-G(\mathbf{z}^{\prime}_{a};{\mathcal{H}}_{1:T})\|_{1}}$
(6)

The complete objective function for stage II is described as

$\displaystyle\min_{G}\max_{D_{\text{img}},D_{\text{vid}}}{\mathcal{L}}^{\text{(II)}}_{\text{adv}}+\lambda^{\text{pixel}}_{\text{div}}{\mathcal{L}}^{\text{pixel}}_{\text{div}},$
(7)

where ${\mathcal{L}}^{\text{(II)}}_{\text{adv}}$ denotes the adversarial loss
for stage II and $\lambda^{\text{pixel}}_{\text{div}}$ adjusts the relative
importance between losses.

##  4 Experiments

Datasets. We evaluate our method on four datasets: 1) Weizmann Action [Blank
et al.(2005)Blank, Gorelick, Shechtman, Irani, and Basri] consists of 90
videos of 9 subjects performing 10 actions (e.g., walk, jumping-jack). 2) From
KTH Action [Schuldt et al.(2004)Schuldt, Laptev, and Caputo], we select videos
of 25 subjects performing three types of actions (boxing, hand waving, and
hand clapping) always having single person in the video. 3) MUG [Aifanti et
al.(2010)Aifanti, Papachristou, and Delopoulos] contains 1,254 video sequences
of six facial expressions, such as anger, disgust, and happiness. 4) UvA-NEMO
[Dibeklioğlu et al.(2012)Dibeklioğlu, Salah, and Gevers] is comprised of 1,240
videos of 400 smiling subjects. We resize the videos to the $64\times 64$
resolution for all datasets.

For training the motion generator, the ground truth keypoints are obtained by
using a pre-trained keypoint detector [Fang et al.(2017)Fang, Xie, Tai, and
Lu, Li et al.(2018a)Li, Wang, Zhu, Mao, Fang, and Lu, Bulat and
Tzimiropoulos(2017)]. In particular, we use 13 out of 68 face keypoints 3332,
9, 16, 20, 25, 38, 42, 45, 47, 49, 52, 55, 58th facial landmark locations
detected using open face alignment library (https://github.com/1adrianb/face-
alignment). We provide a detailed illustration in supplementary material.
including eyes and nose to represent the facial expression for MUG and UvA-
NEMO. And we use 17 pose keypoints for Weizmann Action and KTH Action.

| Weizmann | MUG | UvA | KTH
---|---|---|---|---
VGAN [Vondrick et al.(2016)Vondrick, Pirsiavash, and Torralba] | 99.03 | 104.71 | 103.70 | 103.31
TGAN-v2 [Saito et al.(2020)Saito, Saito, Koyama, and Kobayashi] | 83.90 | 72.60 | 86.91 | 65.03
MoCoGAN [Tulyakov et al.(2018)Tulyakov, Liu, Yang, and Kautz] | 93.93 | 35.12 | 49.58 | 36.90
G3AN [Wang et al.(2020)Wang, Bilinski, Bremond, and Dantcheva] | 64.07 | 21.76 | 39.24 | 44.84
MODE-GAN | 55.06 | 17.90 | 15.38 | 28.28
Table 1: Video FID scores on 4 datasets. Lower values are better. Figure 4:
Qualitative comparison with baselines on human action datasets.

Evaluation on Fixed Frame Rate. We compare our model with unconditional video
generation baselines [Saito et al.(2020)Saito, Saito, Koyama, and Kobayashi,
Tulyakov et al.(2018)Tulyakov, Liu, Yang, and Kautz, Wang et al.(2020)Wang,
Bilinski, Bremond, and Dantcheva, Vondrick et al.(2016)Vondrick, Pirsiavash,
and Torralba] on four datasets. We followed the hyperparameters as presented
in the papers. Table 1 shows qualitative comparison of MODE-GAN with VGAN
[Vondrick et al.(2016)Vondrick, Pirsiavash, and Torralba], TGAN-v2 [Saito et
al.(2020)Saito, Saito, Koyama, and Kobayashi], MoCoGAN [Tulyakov et
al.(2018)Tulyakov, Liu, Yang, and Kautz] and G3AN [Wang et al.(2020)Wang,
Bilinski, Bremond, and Dantcheva] on four different datasets by measuring
video Fréchet Inception Distance (FID) [Wang et al.(2020)Wang, Bilinski,
Bremond, and Dantcheva], which is a widely used metric for evaluating the
quality of videos. As seen in Table 1, MODE-GAN consistently outperforms all
baseline models. This indicates our synthetic videos are not just visually
realistic but keeps the same realistic quality consistently across time
compared to the baselines. Also, Fig. 4 shows visual comparisons using human
action dataset, where MODE-GAN produces the competitive results compared to
the baseline models.444Other visual comparisons using facial expression
dataset are shown in the supplementary material. This state-of-the-art
performance shows that explicitly decomposing the video generation process
into spatial (i.e. appearance) and temporal (i.e. motion) components, and
modeling the latter in the natural continuous-time leads to more realistic
synthetic outcomes.

(a) Recurrent neural network

(b) Neural ODE

Figure 5: Comparison of generated pendulum dynamics (Left: sampled $\theta$
and $\dot{\theta}$, Right: visualization of the bob movement in the gray area
of the left. (a) RNN fails to preserve the smoothness of the pendulum movement
($\theta$ and $\dot{\theta}$ severely fluctuate across time), yielding a rigid
and irregular movement of the bob (b) Neural ODE successfully mimics the
pendulum movement maintaining continuous and smooth bob motion.

Effectiveness of ODE in Learning Dynamics. We compare the effectiveness of
neural ODE with recurrent neural networks (RNNs) in learning the distribution
of dynamics starting from a random noise. Motivated by previous work
[Johansson(1973)] that interprets human motion as a relative pendulum dynamics
of keypoints, we take a pendulum system which is mathematically formulated as

$\displaystyle\ddot{\theta}+\bigg{(}\frac{B}{M}\bigg{)}\cdot\dot{\theta}+\bigg{(}\frac{g}{L}\bigg{)}\cdot\sin(\theta)=0,$
(8)

where $\theta$, $B$, $g$, $L$, and $M$ are the angular displacement, damping
factor, gravity force, length of pendulum, and mass of bob, respectively. Our
goal is to train the generator which is capable of simulating the dynamics of
the pendulum system. For this purpose, the model aims at producing $\theta$
and $\dot{\theta}$, a plausible physical parameters for the pendulum system.
In experiment, $g$ is a constant and fixed to 9.81 $\text{m/s}^{2}$, whereas
$B$, $L$, and $M$ are stochastically determined by sampling each factor from
Gaussian distribution with means of 0.2, 1.0, 1.0 and unit variance,
respectively. As a baseline, we employ an RNN-based motion generator, where we
substitute the neural ODE in stage I with an RNN. The RNN takes Gaussian
noises at each time step and aims to generate a plausible $\theta$ and
$\dot{\theta}$.

As seen in Fig. 5(a), the RNN-based motion generator fails to generate smooth
dynamics, running off the expected trail of the pendulum dynamics. On the
other hand, as in Fig 5(b), our ODE-based motion generator successfully
simulates the pendulum dynamics. This demonstrates that neural ODE has a
benefit in learning the continuous motion dynamics compared to RNN. As seen in
Fig. 5, RNN fails to smoothly interpolate the pendulum trajectory (a) whereas
neural ODE successfully simulates the smooth dynamics of the pendulum (b),
which indicates the potential of neural ODE for learning the dynamics of real-
world videos smoothly. In other words, the capacity of learning the smooth
dynamics can be extended to simulate the unseen dynamics between two frames in
more natural manner without rather unnatural rigid and irregular movements.
Such capability can be seen in Fig. 6, where the motion generator successfully
fills the plausible keypoints at unseen timesteps. Detailed descriptions about
data generation process and model architectures are provided in supplementary
material.

(a) Weizmann Action

(b) KTH Action

Figure 6: Examples of sequence of continuously evolving keypoints: We sample a
sequence of 64 keypoints from MODE-GAN trained at 16 FPS. To visualize the
keypoints dynamics, every 4th frame (i.e. 16 / 64) are marked in bold, while
other frames are faintly illustrated.

Diverse Motions in Continuous-time Space. The motion generator is to learn the
distribution of motions, thereby generating a plausible motion. Specifically,
neural ODE allows the motion generator to model dynamics of keypoints in
continuous-time domain. Fig. 6 shows keypoints representations of various
motions as we integrate densely across time, trained on Weizmann Action and
KTH Action datasets. We see the sampled motions are natural and fluid,
demonstrating that the motion generator has successfully learned the
underlying distribution of video motions.

(a) Fixed Motion

(b) Fixed Appearance

Figure 7: An example of manipulating motion and appearance: (a) Fixed motion
(facial expression) with different appearances, (b) Fixed appearance with
different motions.

Motion and Appearance Manipulation. Recall that our model synthesizes a video
by combining separate representations for motion and appearance. In this
experiment, we demonstrate our model’s capability to generate videos while
maintaining one component (i.e., motion or appearance), by fixing either
$\mathbf{z}_{m}$ or $\mathbf{z}_{a}$ and varying the other.

As shown in Fig. 7, we observe different combinations can successfully produce
videos preserving the fixed component, while altering the other. These results
indicate that we can successfully manipulate the video generation process by
controlling appearance and motion independently.

(a) MUG: Surprise $\Rightarrow$ UvA-NEMO

(b) Weizmann: One hand waving $\Rightarrow$ KTH

Figure 8: Motion transfer results across different video domains (First row:
generated output at source domain, Second row: corresponding keypoints
sequence, Third row: generated output at target domain).

Motion Transfer between Different Video Domains. One of the distinguishing
applications of MODE-GAN is to import a non-existing motion to a different
video domain. Such application stems from the fact that motion-conditioned
video generators share the common motion space expressed as keypoints
representations. Therefore, by connecting the motion generator trained on one
video domain with the motion-conditioned video generator trained on another
one, we can combine motion and appearance from each video domain.

Fig. 8 shows motion transfer examples in facial expression and human action
datasets. (a) Although UvA-NEMO contains only smile motion, surprise
expression can be imported by adopting the motion model trained on MUG
dataset. (b) In a similar manner, we synthesize the KTH Action domain video
using one hand waving motion adopted from the Weizmann Action domain.

Arbitrary Frame Rate Video Generation. Another application of our model is to
generate videos in arbitrary frame rates based on the continuously generated
keypoints from the motion generator. As illustrated in Fig. 9, our model is
capable of synthesizing a video at various frame rates, densely dividing the
continuous-time domain. Synthesized videos successfully fill in the frame at
arbitrary timesteps, demonstrating that our model understand the underlying
dynamics of motion (i.e., two hand waving). Furthermore, we can dynamically
control the frame rate even for a single video (e.g. from slow to fast motion)
by controlling integration time span of the motion generator. Such results are
provided in supplementary material as a video.

(a) Weizmann: Two hand waving

(b) Weizmann: Bending

Figure 9: Videos generated in diverse frame rates by MODE-GAN, trained at 16
FPS.

##  5 Summary and Future Work

In this paper, we propose a novel framework MODE-GAN for unconditional video
generation. Based on the observation that real world videos can be decomposed
into spatial (i.e. static appearance) and temporal (i.e. continuous motion
dynamics) aspects, we employ neural ODE to handle the continuous nature of
video motion. In addition, a two-stage approach enables MODE-GAN to focus on
modeling the motion itself, allowing our model to separately learn motion and
appearance distributions. Experimental results not only demonstrate its
ability to generate high-quality videos but also its versatile functionality
including continuous-time and cross-domain video generation.

Current motion generator of MODE-GAN focuses on modeling the single person’s
dynamics, yet it bears a potential to be used for modelling the dynamics of
multiple people and complex videos. As a future direction, we plan to explore
how to generate highly complicated real world semantics in continuous-time
domain.

## Acknowledgement

This work was supported by the Institute of Information & communications
Technology Planning & Evaluation (IITP) grant funded by the Korean government
(MSIT) (No. 2019-0-00075, Artificial Intelligence Graduate School Program
(KAIST) and No. 2021-0-01778, Development of human image synthesis and
discrimination technology below the perceptual threshold) and by Kakao
Enterprise.

## References

  * [Aifanti et al.(2010)Aifanti, Papachristou, and Delopoulos] Niki Aifanti, Christos Papachristou, and Anastasios Delopoulos.  The MUG facial expression database.  In _International Workshop on Image Analysis for Multimedia Interactive Services_ , 2010.
  * [Blank et al.(2005)Blank, Gorelick, Shechtman, Irani, and Basri] Moshe Blank, Lena Gorelick, Eli Shechtman, Michal Irani, and Ronen Basri.  Actions as space-time shapes.  In _Proc. of the IEEE International Conference on Computer Vision (ICCV)_ , 2005.
  * [Bulat and Tzimiropoulos(2017)] Adrian Bulat and Georgios Tzimiropoulos.  How far are we from solving the 2D & 3D face alignment problem? (and a dataset of 230,000 3D facial landmarks).  In _Proc. of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [Chan et al.(2019)Chan, Ginosar, Zhou, and Efros] Caroline Chan, Shiry Ginosar, Tinghui Zhou, and Alexei A Efros.  Everybody dance now.  In _Proc. of the IEEE International Conference on Computer Vision (ICCV)_ , 2019.
  * [Chen et al.(2018)Chen, Rubanova, Bettencourt, and Duvenaud] Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud.  Neural ordinary differential equations.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2018\.
  * [Cho et al.(2019)Cho, Choi, Park, Shin, and Choo] Wonwoong Cho, Sungha Choi, David Keetae Park, Inkyu Shin, and Jaegul Choo.  Image-to-image translation via group-wise deep whitening-and-coloring transformation.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [De Brouwer et al.(2019)De Brouwer, Simm, Arany, and Moreau] Edward De Brouwer, Jaak Simm, Adam Arany, and Yves Moreau.  GRU-ODE-Bayes: Continuous modeling of sporadically-observed time series.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2019\.
  * [Dibeklioğlu et al.(2012)Dibeklioğlu, Salah, and Gevers] Hamdi Dibeklioğlu, Albert Ali Salah, and Theo Gevers.  Are you really smiling at me? spontaneous versus posed enjoyment smiles.  In _Proc. of the European Conference on Computer Vision (ECCV)_ , 2012\.
  * [Dupont et al.(2019)Dupont, Doucet, and Teh] Emilien Dupont, Arnaud Doucet, and Yee Whye Teh.  Augmented neural ODEs.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2019\.
  * [Fang et al.(2017)Fang, Xie, Tai, and Lu] Hao-Shu Fang, Shuqin Xie, Yu-Wing Tai, and Cewu Lu.  RMPE: Regional multi-person pose estimation.  In _Proc. of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [Gulrajani et al.(2017)Gulrajani, Ahmed, Arjovsky, Dumoulin, and Courville] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville.  Improved training of Wasserstein GANs.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2017\.
  * [Hara et al.(2018)Hara, Kataoka, and Satoh] Kensho Hara, Hirokatsu Kataoka, and Yutaka Satoh.  Can spatiotemporal 3d cnns retrace the history of 2d cnns and imagenet?  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 6546–6555, 2018.
  * [Heusel et al.(2017)Heusel, Ramsauer, Unterthiner, Nessler, and Hochreiter] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  GANs trained by a two time-scale update rule converge to a local nash equilibrium.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2017\.
  * [Jang et al.(2018)Jang, Kim, and Song] Yunseok Jang, Gunhee Kim, and Yale Song.  Video prediction with appearance and motion conditions.  _arXiv preprint arXiv:1807.02635_ , 2018.
  * [Johansson(1973)] Gunnar Johansson.  Visual perception of biological motion and a model for its analysis.  _Perception & psychophysics_, 14(2):201–211, 1973.
  * [Karras et al.(2019)Karras, Laine, and Aila] Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [Karras et al.(2020)Karras, Laine, Aittala, Hellsten, Lehtinen, and Aila] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila.  Analyzing and improving the image quality of styleGAN.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [Kim et al.(2019)Kim, Nam, Cho, and Kim] Yunji Kim, Seonghyeon Nam, In Cho, and Seon Joo Kim.  Unsupervised keypoint learning for guiding class-conditional video prediction.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2019\.
  * [Kwon and Park(2019)] Yong-Hoon Kwon and Min-Gyu Park.  Predicting future frames using retrospective cycle GAN.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [Lee et al.(2020)Lee, Tseng, Mao, Huang, Lu, Singh, and Yang] Hsin-Ying Lee, Hung-Yu Tseng, Qi Mao, Jia-Bin Huang, Yu-Ding Lu, Maneesh Singh, and Ming-Hsuan Yang.  Drit++: Diverse image-to-image translation via disentangled representations.  _International Journal of Computer Vision (IJCV)_ , pages 1–16, 2020\.
  * [Li et al.(2018a)Li, Wang, Zhu, Mao, Fang, and Lu] Jiefeng Li, Can Wang, Hao Zhu, Yihuan Mao, Hao-Shu Fang, and Cewu Lu.  CrowdPose: Efficient crowded scenes pose estimation and a new benchmark.  _arXiv:1812.00324_ , 2018a.
  * [Li et al.(2018b)Li, Fang, Yang, Wang, Lu, and Yang] Yijun Li, Chen Fang, Jimei Yang, Zhaowen Wang, Xin Lu, and Ming-Hsuan Yang.  Flow-grounded spatial-temporal video prediction from still images.  In _Proc. of the European Conference on Computer Vision (ECCV)_ , 2018b.
  * [Pan et al.(2019)Pan, Wang, Jia, Shao, Sheng, Yan, and Wang] Junting Pan, Chengyu Wang, Xu Jia, Jing Shao, Lu Sheng, Junjie Yan, and Xiaogang Wang.  Video generation from single semantic label map.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019.
  * [Park et al.(2020)Park, Kim, Lee, Choo, Lee, Kim, and Choi] Sunghyun Park, Kangyeol Kim, Junsoo Lee, Jaegul Choo, Joonseok Lee, Sookyung Kim, and Edward Choi.  Vid-ODE: Continuous-time video generation with neural ordinary differential equation.  _arXiv:2010.08188_ , 2020.
  * [Park et al.(2019)Park, Liu, Wang, and Zhu] Taesung Park, Ming-Yu Liu, Ting-Chun Wang, and Jun-Yan Zhu.  Semantic image synthesis with spatially-adaptive normalization.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 2337–2346, 2019.
  * [Pu et al.(2018)Pu, Dai, Gan, Wang, Wang, Zhang, Henao, and Duke] Yunchen Pu, Shuyang Dai, Zhe Gan, Weiyao Wang, Guoyin Wang, Yizhe Zhang, Ricardo Henao, and Lawrence Carin Duke.  Jointgan: Multi-domain joint distribution learning with generative adversarial nets.  In _Proc. of the International Conference on Machine Learning (ICML)_ , 2018.
  * [Rubanova et al.(2019)Rubanova, Chen, and Duvenaud] Yulia Rubanova, Tian Qi Chen, and David K Duvenaud.  Latent ordinary differential equations for irregularly-sampled time series.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2019\.
  * [Saito et al.(2017)Saito, Matsumoto, and Saito] Masaki Saito, Eiichi Matsumoto, and Shunta Saito.  Temporal generative adversarial nets with singular value clipping.  In _Proc. of the IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * [Saito et al.(2020)Saito, Saito, Koyama, and Kobayashi] Masaki Saito, Shunta Saito, Masanori Koyama, and Sosuke Kobayashi.  Train sparsely, generate densely: Memory-efficient unsupervised training of high-resolution temporal GAN.  _International Journal of Computer Vision (IJCV)_ , 2020.
  * [Schuldt et al.(2004)Schuldt, Laptev, and Caputo] Christian Schuldt, Ivan Laptev, and Barbara Caputo.  Recognizing human actions: a local svm approach.  In _Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004._ , volume 3, pages 32–36. IEEE, 2004.
  * [Siarohin et al.(2019a)Siarohin, Lathuilière, Tulyakov, Ricci, and Sebe] Aliaksandr Siarohin, Stéphane Lathuilière, Sergey Tulyakov, Elisa Ricci, and Nicu Sebe.  Animating arbitrary objects via deep motion transfer.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019a.
  * [Siarohin et al.(2019b)Siarohin, Lathuilière, Tulyakov, Ricci, and Sebe] Aliaksandr Siarohin, Stéphane Lathuilière, Sergey Tulyakov, Elisa Ricci, and Nicu Sebe.  First order motion model for image animation.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2019b.
  * [Tulyakov et al.(2018)Tulyakov, Liu, Yang, and Kautz] Sergey Tulyakov, Ming-Yu Liu, Xiaodong Yang, and Jan Kautz.  MoCoGAN: Decomposing motion and content for video generation.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * [Vondrick et al.(2016)Vondrick, Pirsiavash, and Torralba] Carl Vondrick, Hamed Pirsiavash, and Antonio Torralba.  Generating videos with scene dynamics.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2016\.
  * [Wang et al.(2018)Wang, Liu, Zhu, Liu, Tao, Kautz, and Catanzaro] Ting-Chun Wang, Ming-Yu Liu, Jun-Yan Zhu, Guilin Liu, Andrew Tao, Jan Kautz, and Bryan Catanzaro.  Video-to-video synthesis.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2018\.
  * [Wang et al.(2019a)Wang, Liu, Tao, Liu, Catanzaro, and Kautz] Ting-Chun Wang, Ming-Yu Liu, Andrew Tao, Guilin Liu, Bryan Catanzaro, and Jan Kautz.  Few-shot video-to-video synthesis.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2019a.
  * [Wang et al.(2020)Wang, Bilinski, Bremond, and Dantcheva] Yaohui Wang, Piotr Bilinski, Francois Bremond, and Antitza Dantcheva.  G3AN: Disentangling appearance and motion for video generation.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * [Wang et al.(2019b)Wang, Jiang, Yang, Li, Long, and Fei-Fei] Yunbo Wang, Lu Jiang, Ming-Hsuan Yang, Li-Jia Li, Mingsheng Long, and Li Fei-Fei.  Eidetic 3D LSTM: A model for video prediction and beyond.  In _Proc. of the International Conference on Learning Representations (ICLR)_ , 2019b.
  * [Wang et al.(2019c)Wang, Zhang, Zhu, Long, Wang, and Yu] Yunbo Wang, Jianjin Zhang, Hongyu Zhu, Mingsheng Long, Jianmin Wang, and Philip S Yu.  Memory in memory: A predictive neural network for learning higher-order non-stationarity from spatiotemporal dynamics.  In _Proc. of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019c.
  * [Yang et al.(2018)Yang, Wang, Zhu, Huang, Shi, and Lin] Ceyuan Yang, Zhe Wang, Xinge Zhu, Chen Huang, Jianping Shi, and Dahua Lin.  Pose guided human video generation.  In _Proc. of the European Conference on Computer Vision (ECCV)_ , 2018\.
  * [Yildiz et al.(2019)Yildiz, Heinonen, and Lahdesmaki] Cagatay Yildiz, Markus Heinonen, and Harri Lahdesmaki.  ODE2VAE: Deep generative second order odes with bayesian neural networks.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2019\.

Supplementary Materials

## A. Background on ODE Formulation

The essence of neural ODEs [Chen et al.(2018)Chen, Rubanova, Bettencourt, and
Duvenaud] lies in employing a neural network $f$ to estimate the vector field
of the latent state $\mathbf{h}$. Formally, $\mathbf{h}$ in the continuous
domain $T\in{\mathcal{T}}$ can be represented as

$\frac{d\mathbf{h}(t)}{dt}=f_{\theta}(\mathbf{h}(t),t),\quad\mathbf{h}(T)=\mathbf{h}(0)+\int_{0}^{T}f_{\theta}(\mathbf{h}(t),t)dt,$

where $\theta$ is a set of trainable parameters of $f$. Regarding time-series
modeling, ${\mathcal{T}}$ corresponds to the continuous time domain, thereby
allowing the model to characterize the latent state over the continuously
evolving time. In our work, the neural ODE is used to model the continuous-
time dynamics of the keypoint sequence, which conveys successive geometric
information on the object movement.

Part | Layer | Activation | Output Shape
---|---|---|---
$\mathbf{z}_{m}$ | - | - | 128
Function $P$ | Linear | ReLU | 128
Linear | ReLU | 128
Linear | ReLU | 128
Linear | - | 128
ODE Solver $f_{\theta}$ | Linear | Tanh | 128
Linear | - | 128
Function $Q$ | Linear | ReLU | 128
Linear | ReLU | 128
Linear | - |  2$\times$K
Heatmaps ${\mathcal{H}}_{1:T}$ | - | - |  T$\times$K$\times$64$\times$64
Table 2: Motion generator architecture of our model.

Part | Layer | Activation | Output Shape
---|---|---|---
Heatmap ${\mathcal{H}}_{t}$ | - | - |  K$\times$64$\times$64
Discriminator $D^{(I)}_{fr}$ | Conv | LeakyReLU |  32$\times$32$\times$32
Conv | LeakyReLU |  64$\times$16$\times$16
Conv | LeakyReLU |  128$\times$8$\times$8
Conv | LeakyReLU |  256$\times$4$\times$4
Conv | LeakyReLU |  256$\times$1$\times$1
| Conv | - | 1
Heatmaps ${\mathcal{H}}_{1:T}$ | - | - |  T$\times$K$\times$64$\times$64
Discriminator $D^{(I)}_{sq}$ | Conv | LeakyReLU |  T$\times$32$\times$32$\times$32
Conv | LeakyReLU |  T/2$\times$32$\times$32$\times$32
Conv | LeakyReLU |  T/2$\times$64$\times$16$\times$16
Conv | LeakyReLU |  T/4$\times$64$\times$16$\times$16
Conv | LeakyReLU |  T/4$\times$128$\times$8$\times$8
Conv | LeakyReLU |  T/8$\times$128$\times$8$\times$8
Conv | LeakyReLU |  T/8$\times$256$\times$4$\times$4
Conv | LeakyReLU |  T/16$\times$256$\times$4$\times$4
Conv | LeakyReLU |  T/16$\times$256$\times$1$\times$1
| Conv | - | 1
Table 3: Motion discriminator architecture of our model.

## B. Implementation details

### B.1. Network Architecture

We provide the architecture details of MODE-GAN, which consists of two stages.
All architectures are described for the purpose of generating 64$\times$64
videos of 16 timesteps. The architectures of the motion generator and the
discriminator are shown in Tables 3 and 3, respectively. Also, the
architectures of the video generator and discriminator are shown in Tables 5
and 5, respectively.

Part | Layer | Activation | Output Shape
---|---|---|---
$\mathbf{z}_{a}$ | - | - | 128
FC | Linear | LeakyReLU | 128
Linear | LeakyReLU | 128
Linear | LeakyReLU | 128
Linear | LeakyReLU | 8192
Generator $G$ | $\mathbf{M}^{1}_{t}$ | - |  512$\times$4$\times$4
Upsample | - |  512$\times$8$\times$8
Comp. Block | - |  512$\times$8$\times$8
Upsample | - |  512$\times$16$\times$16
Comp. Block | - |  256$\times$16$\times$16
Upsample | - |  256$\times$32$\times$32
Comp. Block | - |  128$\times$32$\times$32
Upsample | - |  128$\times$64$\times$64
Comp. Block | - |  64$\times$64$\times$64
Conv3$\times$3 | Tanh |  3$\times$64$\times$64
Table 4: Video generator architecture of our model.

Part | Layer | Activation | Output Shape
---|---|---|---
Frame $\mathbf{v}_{t}$ | - | - |  3$\times$64$\times$64
Discriminator $D^{(I)}_{fr}$ | Conv | LeakyReLU |  64$\times$32$\times$32
Conv | LeakyReLU |  128$\times$16$\times$16
Conv | LeakyReLU |  256$\times$8$\times$8
Conv | LeakyReLU |  512$\times$4$\times$4
Conv | LeakyReLU |  512$\times$1$\times$1
| Conv | - | 1
Video $\mathbf{v}_{1:T}$ | - | - |  T$\times$3$\times$64$\times$64
Discriminator $D^{(I)}_{sq}$ | Conv | LeakyReLU |  T$\times$64$\times$32$\times$32
Conv | LeakyReLU |  T/2$\times$64$\times$32$\times$32
Conv | LeakyReLU |  T/2$\times$128$\times$16$\times$16
Conv | LeakyReLU |  T/4$\times$128$\times$16$\times$16
Conv | LeakyReLU |  T/4$\times$256$\times$8$\times$8
Conv | LeakyReLU |  T/8$\times$256$\times$8$\times$8
Conv | LeakyReLU |  T/8$\times$512$\times$4$\times$4
Conv | LeakyReLU |  T/16$\times$512$\times$4$\times$4
Conv | LeakyReLU |  T/16$\times$512$\times$1$\times$1
| Conv | - | 1
Table 5: Video discriminator architecture of our model.

### B.2. Evaluation Metric

We evaluate all video generation models via Frechet Inception Distance (FID)
[Heusel et al.(2017)Heusel, Ramsauer, Unterthiner, Nessler, and Hochreiter,
Wang et al.(2018)Wang, Liu, Zhu, Liu, Tao, Kautz, and Catanzaro], measuring
the distance between two sets of videos based on their embeddings from a pre-
trained feature extractor [Hara et al.(2018)Hara, Kataoka, and Satoh].
Specifically, the video FID [Wang et al.(2020)Wang, Bilinski, Bremond, and
Dantcheva] is computed as

$\|\mu-\tilde{\mu}\|^{2}+\mathbf{Tr}(\Sigma+\tilde{\Sigma}-2\sqrt{\Sigma\tilde{\Sigma}}),$
(9)

where $\mu$, $\tilde{\mu}$, $\Sigma$, and $\tilde{\Sigma}$ represent the mean
and covariance matrix of real and fake feature maps across all video frames,
respectively. Lower FID means the distribution between the feature vectors of
real and fake are more similar, hence more realistic fake samples.

### B.3. Adversarial Objectives

Adversarial Losses at Stage I. We employ two discriminators
$D^{\text{(I)}}_{\text{fr}},D^{\text{(I)}}_{\text{sq}}$, where each receives
Gaussian heatmaps at an individual frame and sequence level, respectively.
$D^{\text{(I)}}_{\text{fr}}$ plays a role in enhancing the generated keypoints
quality better in single frame-level and $D^{\text{(I)}}_{\text{sq}}$
encourages the generated keypoints sequences to be naturally evolving.

$\displaystyle{\mathcal{L}}^{\text{(I)}}_{\text{adv}}=\mathbb{E}_{{\mathcal{H}}_{t},\hat{{\mathcal{H}}}_{t}}\big{[}\log
D^{\text{(I)}}_{\text{fr}}({\mathcal{H}}_{t})+\log(1-D^{\text{(I)}}_{\text{fr}}(\hat{{\mathcal{H}}}_{t}))\big{]}$
(10)
$\displaystyle+\mathbb{E}_{{\mathcal{H}}_{1:T},\hat{{\mathcal{H}}}_{1:T}}\big{[}\log
D^{\text{(I)}}_{\text{sq}}({\mathcal{H}}_{1:T})+\log(1-D^{\text{(I)}}_{\text{sq}}(\hat{{\mathcal{H}}}_{1:T}))\big{]}.$

In particular, we employ the WGAN-GP [Gulrajani et al.(2017)Gulrajani, Ahmed,
Arjovsky, Dumoulin, and Courville] loss as the adversarial loss.

Adversarial Losses at Stage II. We use adversarial losses to achieve both
goals: (1) the image discriminator loss for generating realistic frames and
(2) the video discriminator loss for retaining motion information, where we
use the WGAN-GP [Gulrajani et al.(2017)Gulrajani, Ahmed, Arjovsky, Dumoulin,
and Courville] loss. To this end, we use two motion conditional adversarial
losses: $D^{\text{(II)}}_{\text{fr}}$, $D^{\text{(II)}}_{\text{sq}}$
encourages the model to generate realistic frames and retaining motion
information.

$\displaystyle{\mathcal{L}}^{\text{(II)}}_{\text{adv}}$
$\displaystyle=\mathbb{E}_{\mathbf{v}_{t},\hat{\mathbf{v}}_{t},{\mathcal{H}}_{t}}\big{[}\log
D^{\text{(II)}}_{\text{fr}}([\mathbf{v}_{t};{\mathcal{H}}_{t}])+\log(1-D^{\text{(II)}}_{\text{fr}}([\hat{\mathbf{v}}_{t};{\mathcal{H}}_{t}]))\big{]}$
(11)
$\displaystyle+\mathbb{E}_{\mathbf{v}_{1:T},\hat{\mathbf{v}}_{1:T},{\mathcal{H}}_{1:T}}\big{[}\log
D^{\text{(II)}}_{\text{sq}}([\mathbf{v}_{1:T};{\mathcal{H}}_{1:T}])+\log(1-D^{\text{(II)}}_{\text{sq}}([\hat{\mathbf{v}}_{1:T};{\mathcal{H}}_{1:T}]))\big{]},$

where $[\boldsymbol{\cdot}\hskip 1.42271pt;\hskip
1.42271pt\boldsymbol{\cdot}]$ denotes concatenation. We adopt the WGAN-GP
[Gulrajani et al.(2017)Gulrajani, Ahmed, Arjovsky, Dumoulin, and Courville]
loss similar to stage I.

(a) RNN-based motion generator (b) Neural ODE-based motion generator

Figure 10: Comparison of RNN and neural ODE-based architectures for pendulum
experiment. The only difference lies in the intermediate neural networks that
generates the hidden states $\mathbf{h}_{1:T}$. For the RNN input, a Gaussian
noise $\epsilon_{t}$ is used for each timesteps $t=1,2,\ldots T$.

### B.4. Details of Pendulum Experiments

Dataset Generation. We used 1,000 simulated pendulum trajectories with fixed
gravity force $g$ of 9.81 m/s2. The damping factor $B$, length of pendulum
$L$, and mass of bob $M$ were each sampled from the Gaussian distribution with
respective means of 0.2, 1.0, 1.0 and unit variance. For trajectory
simulation, Runge-Kutta was used to solve the pendulum equation (first order
differential equations) described below:

$\displaystyle\begin{bmatrix}\big{(}\frac{d\theta}{dt}\big{)}\\\
\big{(}\frac{d\dot{\theta}}{dt}\big{)}\end{bmatrix}=\begin{bmatrix}\dot{\theta}\\\
-\big{(}\frac{g}{L}\big{)}\cdot\sin(\theta)-\big{(}\frac{B}{M}\big{)}\cdot\dot{\theta}\end{bmatrix},$

Figure 11: The 68 2D landmarks used by facial landmarks detector model [Bulat
and Tzimiropoulos(2017)]. We use 13 keypoints among them (red).

where $dt$ is a time unit fixed to 0.1 during data generation.

Comparison of RNN and ODE Motion Generator. Fig. 10 shows the detailed
architectures of RNN and neural ODE-based pendulum dynamics generator. Both
generators are trained using 1,000 simulated pendulum trajectories. After
training, the generators should mimic the plausible dynamics of a pendulum by
estimating two physical variables $\theta$ and $\dot{\theta}$.

### B.5. Dataset Preprocessing

Fig. 11 shows the chosen facial keypoints (2, 9, 16, 20, 25, 38, 42, 45, 47,
49, 52, 55, 58th) for MUG [Aifanti et al.(2010)Aifanti, Papachristou, and
Delopoulos] and UvA-NEMO [Dibeklioğlu et al.(2012)Dibeklioğlu, Salah, and
Gevers]. The facial keypoint selections refer to previous work [Jang et
al.(2018)Jang, Kim, and Song]. We crop and resize to $64\times 64$ pixels for
both datasets.

(a) Recurrent neural network

(b) Neural ODE

Figure 12: Visualization of generated $\theta,\dot{\theta}$ using two
different motoin generators employing (a) RNN and (b) Neural ODE

## C. Additional Experiments

In the following section, we provide additional experiments as follows:

  * •

Analysis on the dynamics of each video dataset.

  * •

Qualitative examples from pendulum experiments using both recurrent neural
network and neural ODE.

  * •

Qualitative examples of sampled keypoints sequence from our motion generator.

  * •

Qualitative comparison results against unconditional video generation
baselines using facial expression datasets.

  * •

Qualitative results of appearance and motion manipulation on UvA-NEMO and MUG.

  * •

Qualitative and quantitative evaluations on dynamic frame rate.

Analysis on Dynamics of Datasets. To analyze the dynamics of each dataset, we
includes the video examples of the four training datasets :Weizmann Action,
KTH Action, MUG, and UvA-NEMO. Due to different frame rates and velocity of
human motions in each dataset, the degree of the movement between the adjacent
frames varies as shown in Fig. 13. We find out that Human action datasets
(i.e., Weizmannn Action and KTH Action) have relatively large movements
compared to facial expression datasets (i.e. MUG and UvA-NEMO). As a result,
our model and baselines display more significant movements in the human action
videos than in the facial expression videos.

Examples of Pendulum Experiment. Fig. 12 shows additional examples of the
generated pendulum dynamics from the RNN and the neural ODE based motion
generators (See Fig. 10 for detailed architecture). As shown in Fig. 12, the
RNN-based motion generator fails to generate smooth dynamics (a). In contrast,
our ODE-based motion generator successfully simulates the pendulum dynamics
(b).

Examples of Sampled Motion. Fig. 14 illustrates the examples of the generated
keypoints sequences from our motion generator trained on Weizmann Action
(purple) or KTH Action dataset (blue). Through these examples, we demonstrate
that our motion generator has the capability in producing diverse and fluid
motions as a form of a sequence of evolving keypoints.

Comparison with baselines using Facial Expression Datasets. Fig. 15 presents
qualitative comparison of MODE-GAN with VGAN [Vondrick et al.(2016)Vondrick,
Pirsiavash, and Torralba], TGAN-v2 [Saito et al.(2020)Saito, Saito, Koyama,
and Kobayashi], MoCoGAN [Tulyakov et al.(2018)Tulyakov, Liu, Yang, and Kautz]
and G3AN [Wang et al.(2020)Wang, Bilinski, Bremond, and Dantcheva] on two
facial expression datasets: UvA-NEMO and MUG. MODE-GAN shows competitive
results compared to the baseline models while most generated videos contain
relatively marginal movement than human action cases due to the restricted
movement characteristics of facial datasets.

Examples of Motion and Appearance Manipulation. As shown in Fig. 16-19, we
further demonstrate the ability of MODE-GAN to separately learn the appearance
and motion representations. We show the examples of manipulating appearance
and motion noise vectors in our video generator trained on MUG and UvA-NEMO
dataset.

Qualitative Evaluation on Dynamic Frame Rate. One major strength of MODE-GAN
which makes it distinguished with other baselines is its ability to generate
videos in continuous-time domain ${\mathcal{T}}$. In other words, MODE-GAN can
generate realistic videos in arbitrary frame rates regardless of the frame
rate of the training samples, by simply integrating (i.e. generating keypoints
sequences) over the desired timesteps. (e.g., MODE-GAN can generate video
frames at 0.17 or 0.81 second by training with 1.0-second time intervals). In
other words, MODE-GAN can flexibly generate a video at an arbitrary frame rate
other than the one used at training (e.g., generating video frames at 0.17 or
0.81 second). In this experiment, we compare the quality of Weizmann Action
videos generated in various frame rates ($\\{16,18,20,22,24\\}$ FPS) by MODE-
GAN and a baseline (MoCoGAN) both trained at 16 FPS. While MODE-GAN learns
motion dynamics based on fixed timesteps
$\\{s_{1},s_{2},\ldots,s_{T}\\}\subset{\mathcal{T}},\text{ where
}0<s_{1}<s_{2}<\cdots<s_{T}$ during training, it can generate videos in
arbitrary frame rates by simply integrating over the desired timesteps during
inference. In this experiment, we compare the quality of videos generated in
various frame rates, both by MODE-GAN and a baseline, namely MoCoGAN. We
define A continuous-time video generation problem aims to generate video
frames $\hat{\mathbf{v}}_{1:L}$ for another set of timesteps
${\mathcal{M}}\equiv\\{m_{1},m_{2},\ldots,m_{L}\\}\subset{\mathcal{T}}$. As a
matter of fact, this task can reduces to discrete-time video generation
problem as previously tackled if we set ${\mathcal{M}}={\mathcal{S}}$.
Furthermore, We evaluate the video quality given the arbitrary length query
timesteps ${\mathcal{M}}$ to demonstrate the capability on synthesizing a
video at continuous-time domain. As MoCoGAN produces motion codes via its RNN
component only for each 1/16 second, we linearly interpolate two adjacent
motion codes from the RNN to obtain the motion representation at unseen
timesteps. 555Unlike MODE-GAN and MoCoGAN, other baselines cannot generate or
interpolate motion features at arbitrary timesteps. 666We take MoCoGAN as a
representative RNN-based model for generating motion features at arbitrary
timesteps. Note that G3 AN cannot generate or interpolate motion features at
arbitrary timesteps. Fig. 20 shows a comparison between synthetic videos
generated by MoCoGAN and MODE-GAN at 20 FPS. While MoCoGAN generates frames
that looks like a mixture of multiple images, MODE-GAN generates distinct
frames, showing the advantage of the ODE-based approach in handling continuous
time. These results demonstrate that simply interpolating different motion
representations to generate in-between frames yields sub-optimal outcomes
(i.e. mixed frames at the pixel level).

Quantitative Evaluation on Dynamic Frame Rate. Fig. 21 shows the video FID
scores of the videos generated at increasing frame rates (from 16 to 24) using
the two models traine at 16 FPS. Based on the the monotonic increase of video
FID scores by both models, it is evident that the denser the frame rate, the
more challenging the video generation becomes. However, the steeper slope of
MoCoGAN than MODE-GAN clearly indicates that MODE-GAN is quite robust to the
increasing FPS. In other words, MODE-GAN is more comfortable than MoCoGAN in
generating videos in continuous-time domain, even at a higher frame rate than
the training frame rate.

(a) Weizmann Action

(b) KTH Action

(c) MUG

(d) UvA-NEMO

Figure 13: Video samples from each dataset. Figure 14: Examples of generated
keypoints sequences from our motion generator. Figure 15: Qualitative
comparison with baselines on facial expression datasets. Figure 16:
Qualitative results of our method on the MUG dataset. Every three row has the
same $\mathbf{z}_{a}$ (i.e. appearance noise vector) with different
$\mathbf{z}_{m}$ (i.e. motion noise vector). Figure 17: Qualitative results of
our method on the MUG dataset. Every three row has same $\mathbf{z}_{m}$ (i.e.
motion noise vector) with different $\mathbf{z}_{a}$ (i.e. appearance noise
vector). Figure 18: Qualitative results of our method on the UvA-NEMO dataset.
Every three row has same $\mathbf{z}_{a}$ (i.e. appearance noise vector) with
different $\mathbf{z}_{m}$ (i.e. motion noise vector). Figure 19: Qualitative
results of our method on the UvA-NEMO dataset. Every three row has same
$\mathbf{z}_{m}$ (i.e. motion noise vector) with different $\mathbf{z}_{a}$
(i.e. appearance noise vector).

(a) Ours

(b) MoCoGAN

Figure 20: 20-FPS videos generated by two models. Figure 21: Video FID scores
with varied frame rates on Weizmann Action. MODE-GAN consistently outperforms
MoCoGAN, showing marginal performance drop to generate at higher frame rate.


# Linear Depth QFT over IBM Heavy-hex Architecture

Xiangyu Gao  New York University<EMAIL_ADDRESS>,  Yuwei Jin  Rutgers
University<EMAIL_ADDRESS>,  Minghao Guo  Rutgers University
<EMAIL_ADDRESS>,  Henry Chen  Rutgers University
<EMAIL_ADDRESS>and  Eddy Z. Zhang  Rutgers University
<EMAIL_ADDRESS>
###### Abstract.

Compiling a given quantum algorithm into a target hardware architecture is a
challenging optimization problem. The compiler must take into consideration
the coupling graph of physical qubits and the gate operation dependencies. The
existing noise in hardware architectures requires the compilation to use as
few running cycles as possible. Existing approaches include using SAT solver
or heuristics to complete the mapping but these may cause the issue of either
long compilation time (e.g., timeout after hours) or suboptimal compilation
results in terms of running cycles (e.g., exponentially increasing number of
total cycles).

In this paper, we propose an efficient mapping approach for Quantum Fourier
Transformation (QFT) circuits over the existing IBM heavy-hex architecture.
Such proposal first of all turns the architecture into a structure consisting
of a straight line with dangling qubits, and then do the mapping over this
generated structure recursively. The calculation shows that there is a linear
depth upper bound for the time complexity of these structures and for a
special case where there is 1 dangling qubit in every 5 qubits, the time
complexity is 5N$+O(1)$. All these results are better than state of the art
methods.

††copyright: none††isbn: ††price:

##  1\. Introduction

Quantum computing has become more and more popular across multiple fields,
such as chemistry simulation, financial modeling, and cybersecurity. People
develop quantum algorithms to realize many computations that cannot be
completed within a reasonable amount of time using traditional computation
methods. One influential algorithm in this domain is Shor’s algorithm (Shor,
1994), which brings people’s attention to quantum computing because this
algorithm can provide an exponential speed up to factor larger numbers into
prime factors. This brings huge risks for several encryption methods,
including the most popularly used RSA algorithm. Quantum Fourier
Transformation (QFT) sits at the heart of Shor’s algorithm, and therefore, it
is one of the most important algorithms in quantum computing. In general, QFT
requires all qubits to execute a Hadamard gate and all qubit pairs to execute
a CPHASE gate. Figure 1 shows a concrete example of all quantum gates for
5-qubit QFT.

Figure 1. All necessary CPHASE gate operations over a QFT. H represents the
Hadamard gate and Ri represents the CPHASE gate.

The development of quantum computing also motivates a proliferation of quantum
hardware architectures by industrial participants, including Google Sycamore,
IBM heavy hex, LNN, and 2D grid. The concrete coupling graph varies from
architecture to architecture. Typically, the number of connection links is
relatively small with respect to the total number of qubits within the
hardware compared with an all-to-all connection among all qubits. The compiler
must consider the connection link as a constraint to do efficient circuit
transformation and qubit mapping.

Prior work In this paper, we focus on the mapping algorithm for QFT over the
IBM heavy-hex architecture. Prior work has tackled similar problems by
developing general mapping algorithms for multiple architectures. However,
they may cause the problem of long compilation time(Tan and Cong, 2020; Tan et
al., 2022; Molavi et al., 2022; Murali et al., 2019), or suboptimal mapping
results (Li et al., 2019), or be too restricted to particular type of
architectures with a Hamiltonian path to connect all qubits (Maslov, 2007). We
cannot directly transplant those works to solve the QFT mapping over IBM
heavy-hex architecture and generate satisfying outcomes.

Our approach. We generate a coupling graph of one major line with dangling
qubits from heavy-hex architecture by deleting a tiny portion of connection
links. Then, we label each qubit’s number in increasing order from left to
right, from up to bottom. The proposed QFT mapping algorithm leverages the
proposed linear QFT by Maslov (Maslov, 2007) and Zhang _et al_ (Zhang et al.,
2021) in linear nearest neighbor (LNN) architecture, with some modification.
Based on our transformed heavy-hex coupling graph, we could implement the QFT
mapping algorithm recursively. In our approach, we can have $m$ dangling
nodes; each time there is a SWAP gate operation between a qubit in the major
line and a dangling qubit, it reduces to the problem with $m-1$ dangling
nodes. The base case is the coupling graph with no dangling nodes, and this is
exactly the same as the linear QFT scenario.

Contributions Our contributions are multi-fold. We used a coupling graph
tailored to IBM heavy-hex architecture containing repeated patterns. This
coupling graph makes it possible for us to leverage a “recursive” algorithm
design to tackle the QFT mapping. Furthermore, we develop a mapping algorithm
that takes linear complexity to map a QFT algorithm into the heavy-hex
architecture. We have achieved $5N+O(1)$ complexity for a heavy hex
architecture with $N$ qubits. Last but not least, we show the correctness of
the proposal and calculate both the upper bound for a general case
architecture and the exact time complexity for one special case. The head-to-
head comparison offers significant improvement in the time complexity over an
existing linear depth approach over the IBM heavy-hex architecture (Jin et
al., 2023).

##  2\. Qubit Mapping for IBM Heavy-hex

In this section, we are going to describe the mapping algorithms for QFT over
the IBM heavy-hex architecture in detail. We, first of all, present the
concrete coupling graph of heavy-hex architecture; then, based on the coupling
graph, an initial mapping of logical qubits to physical qubits is provided to
place each logical qubit in its initial position; Finally, we provide a
detailed algorithm to show the gate operations in each step during the QFT
mapping process.

###  2.1. Coupling Graph

From heavy-hex to a generalized coupling graph. We want the coupling graph to
have repeated patterns so that the final solution can be generalized to an
arbitrary number of such patterns with larger sizes. However, finding such
patterns directly from the heavy-hex architecture is not straightforward. If
we look at the original heavy-hex architecture on the left-hand side of Figure
2, it is not obvious to find repeated patterns directly from it. In other
words, unlike LNN, 2D grid, or even Google Sycamore architecture where
repeated patterns exist, we are unable to describe the given heavy-hex
architecture by some parameter n.

To realize the goal, we simplify the coupling graph of the original heavy hex
by deleting some connection lines in the architecture. Here is the current
coupling graph. Each pattern consists of 2 parts: major line and dangling
qubits. All qubits with only one qubit as its neighbor will be defined as
dangling qubits. All other qubits can form one straight line and are defined
as the major line qubits. As for a concrete heavy-hex example in Figure 2, the
right-hand side shows a generated coupling graph with nine dangling nodes
(labeled by 1), and all the rest (labeled by 0) are qubits in the major line.

Figure 2. Turn heavy-hex (left-hand side) to our transformed coupling graph
(right-hand side) with repeated patterns by removing some connection links
(highlight by X). The transformed coupling graph consists of a major line
(labeled by 0) with dangling points (labeled by 1).

Therefore, the architecture can be represented in a structured way using two
types of qubits. This strikes a balance between qubit connectivity and pattern
generalization. On the one side, it lets clear patterns exhibit from the
heavy-hex architecture; on the other hand, it keeps the majority of connection
links, maximizing the utilization of the existing hardware architecture.

It is worthwhile to highlight some potential benefits of such coupling graph
design, which would be leveraged in the mapping algorithm later. The coupling
graph is close to LNN architecture. Most of all qubits are located in the
major line, meaning they can be regarded as an extension of the LNN
architecture. Besides, given a heavy-hex architecture, we have multiple ways
to build the coupling graph by deciding which connection link to avoid. In the
original setting, each “dangling qubit” has two links to connect to 2 neighbor
qubits. We can delete either of them to get the final transformed coupling
graph. This brings the possibility of error mitigation when particular links
are prone to error.

###  2.2. Definitions

We describe a few definitions before describing the initial mapping and the
qubit mapping algorithm.

  * •

N1: the number of qubits on the major line.

  * •

N2: the number of dangling qubits.

  * •

N: the total number of qubits. N $=$ N1 + N2.

  * •

n: the total number of repeated groups/patterns in the coupling graph.

###  2.3. Initial Mapping

We put logical qubits’ initial mapping/placement in Figure 3. In general, the
qubits’ number has an increasing order from left to right and up to down. The
initial mapping should follow such a rule: when we compare any two adjacent
qubits, the qubit in the right/down position has a larger index.

Figure 3. Initial mapping for Heavy-hex with dangling qubits: for any node $i$
that has both a node connected to it from the below and a node connected to it
from the right (a “T” junction node), the below node has index $i+1$, and the
right node has index $i+2$. For any node $i$ that is not involved in a “T”
junction does not have a node below, its left node will be $i-1$, and the
right node will be $i+1$.

We have also considered alternative mapping methods but they might cause
potential problems. Suppose there are N qubits, N1 of which are placed in the
major line, while the remaining N2 qubits are located as dangling points. One
candidate choice is to label all qubits in the major line from 0 to N1 - 1 and
the remaining qubits in the dangling positions from N1 to N - 1. This could
lead to a problem where we have to relabel some of the qubits if we increase
the number of groups in our particular design. In our case, the existing
initial mapping method guarantees that adding a new group (a set of nodes with
one dangling point) will not affect the previous qubit mapping. This brings
potential benefits to calculating the time complexity by induction since we
could do this with a focus on the extra steps required from the added group)
rather than doing everything from scratch every time.

###  2.4. Qubit Mapping Algorithm

Before describing the algorithm details, we define a few terms in this domain.
We can see from Figure 6 that there are two types of nodes in our defined
coupling graph of heavy-hex. The first type contains $N1$ qubits, and we call
it the major line, while the second type contains the remaining $N2$ qubits
dangling from the major line. So we call them dangling points.

####  2.4.1. Revisit the linear QFT mapping algorithm

Before describing our proposal for QFT mapping over the heavy-hex
architecture, we would revisit the QFT mapping over linear nearest
neighbor(LNN) structure (Zhang et al., 2021) because there would be several
similarities. In general, QFT mapping over LNN has interleaving steps between
CPHASE cycle and SWAP cycle. For each pair consisting of CPHASE and SWAP, they
would appear in the same link in two consecutive steps. A concrete example
with 4 qubits in a line is shown in Figure 4. We could see that the final
mapping after QFT ($q_{3}$ to $q_{0}$) is a mirror image of the initial
mapping ($q_{0}$ to $q_{3}$).

Figure 4. The concrete steps in QFT mapping for LNN over a line with 4 qubits.
Each pair consists of one CPHASE step and SWAP step occurring in the same
connection links.

####  2.4.2. Special Case of Only One Dangling Point

Let’s consider the special case when there is only one dangling node from the
major line. We will extend it to the case of multiple dangling points later.

Below are concrete steps of our QFT mapping solution. We start running QFT as
if it is on a line of nodes from $q_{0}$ to $q_{i+1}$ first until a certain
point.

Figure 5. Rules of gate operations for the QFT mapping with one dangling
point. The LHS shows the process of turning the QFT mapping into 3 phases:
before $q_{0}$ moves to the place above $q_{4}$, interaction between $q_{0}$
and $q_{4}$, all steps afterwards. The initial state of the third phase is an
intermediate step of RHS where we do QFT for $q_{1}$ to $q_{n-1}$, realizing
the reduction from one dangling point to none.

  * •

The first time when q0 is above (connected to) $q_{i+1}$ (the dangling point),
as shown in Figure 6, we will perform SWAP(q0, $q_{i+1}$). Then, the positions
of qubits of the major line are similar to that in an intermediate step when
we do linear QFT over a straight line starting from q1 to $q_{N1-1}$, and the
timing is right before $q_{1}$ swaps with $q_{i+1}$.

  * •

Then let it continue with the steps of doing QFT for $q_{1}$ to $q_{N1-1}$ on
a straight line until done. Note that whenever a qubit $q_{j}$ such that $j>i$
is moved to next to $q_{0}$ in the dangling position for the first time, we
pause and let $q_{0}$ perform a CPHASE with it. And then the algorithm is
done.

A concrete example is shown in Figure 5, where the dangling point $i+1$ is set
as 4.

From the above, one can see what all nodes from $q_{1}$ to $q_{N1-1}$ can
perform CPHASE gates using the usual linear QFT solution. What about the node
$q0$? Since we moved it to the dangling position, we kept it there until the
end of the algorithm. Before it is moved to the dangling position, it has
interacted with qubits $q_{1}$ to $q_{i}$. Then how do we ensure it also
performs CPHASE with nodes from $q_{i+1}$ to $q_{N1-1}$? In the straight line
QFT, as shown in prior work (Zhang et al., 2021; Maslov, 2007), each qubit $i$
moves towards the left first, stops for one step, and then to the right, for
$N1-1$ distance all altogether (we define the distance between two adjacent
qubits as 1), where $N1$ is the length of the major straight line. All nodes
after $q_{i+1}$ on the original line are to the right of $q_{0}$’s fixed
location in the dangling point. And these nodes haven’t started moving when
$q_{0}$ is moved to the dangling location. Each of them needs to move $N1-1$
distance. Among all such nodes, the farthest node to $q_{0}$’s dangling
location has a distance of $N1-i-1$, smaller than $N1-1$. Hence when these
nodes move to the left, they will be above $q_{0}$ at one time point. Whenever
they meet $q_{0}$, we let $q_{0}$ perform a CPHASE with these qubits. Hence
the interaction between $q_{0}$ and the nodes from $q_{i+2}$ to $q_{N1-1}$ are
completed.

Now the problem is solved; all qubits interact. The dependence is also
satisfied. We sketch the proof here. As $q_{0}$ interacts with these nodes
from $q_{i+2}$ to $q_{N1-1}$, due to the fact that a node moves faster than a
node that is originally on its right. However, $q_{1}$ could interact with
$q_{i+2}$ to $q_{N1-1}$ earlier. This is okay. It is because the true
dependence in QFT, is that a gate ($q_{i}$, $q_{j}$) where $q_{i}$ is the
control and $q_{j}$ is the target, has to execute after ($q_{k}$, $q_{i}$)
$k<=i$. Since ($q_{0}$, $q_{i+2}$) and ($q_{1}$, $q_{i+2}$) do not have
dependence, they can run in any order. Moreover, the time ($q_{1}$, $q_{k}$)
where $k>1$ runs, ($q_{0}$, $q_{1}$) has already happened, as $q_{1}$ has
already moved past $q_{0}$.

Figure 6. Recursive pattern: reducing one dangling node from the coupling
graph after two steps: one CPHASE gate and one SWAP gate between the qubit
above and the dangling point itself.

####  2.4.3. Extending to the Case of More than One Dangling Points

Now we describe the case of more than one dangling point. We show how it is
handled in a recursive manner. Specifically, we could reduce the number of
dangling nodes by one each time. Let’s assume we have two nodes dangling from
the major line, as shown in Figure 6, $q_{i+1}$ and $q_{j+1}$. We follow the
solution that is the same as the single-dangling-point case. The first time we
swap $q_{0}$ with $q_{i+1}$, it is as if we can remove $q_{0}$ from the entire
line, and then it reduces to the problem of having only one dangling point. We
continue the solution for a straight line with one dangling point, and the
problem is solved. Note that $q_{0}$ is in a fixed position now (the first
dangling position), and all the remaining nodes to the right of $q_{i+1}$ will
move to the left first, and they can interact with $q_{0}$.

Hence, we proved the case from one to two dangling points. The same idea works
for from $k$ dangling points to $k+1$ dangling points. The reason is that the
previous $k$ qubits $q_{0}$ to $q_{k-1}$ have already moved to the fixed
dangling locations (as if the are already removed), and the remaining sequence
on the major line starts from $q_{k}$, and that is reduced to the single-
dangling-node problem again. And we can prove that $q_{k-1}$, whenever it is
moved to the $k$-th dangling location, it will later interact with all nodes
to the right of it in the original placement.

We haven’t talked about CPHASE gates yet. For the straight-line QFT case, the
CPHASE happens in the same way as the linear QFT. A special scenario is when a
right qubit (right of the original locations of the first $k$ qubits) reaches
the “T-junction” for the first time, where there is a dangling qubit below. If
dependence is satisfied, we let the qubit above and below in the “T-junction”
perform a CPHASE gate.

###  2.5. Special Case

Figure 5 is a special case where each group consists of 5 qubits such that we
define a group of 5 qubits as that 4 of which are in the major line and one is
in the dangling position. This is similar to what we have unrolled from the
heavy-hex architecture. There is a dangling qubit for every four (or eight)
qubits on the major line. We will show the complexity result of that later.

##  3\. Case Study and General Complexity

In this section, we will first present a detailed analysis of a special case
where there will be a dangling qubit in every five qubits with initial mapping
in Figure 7 and final mapping in Figure 8. Correctness analysis and time
complexity analysis are given to show that our proposed algorithm can
correctly complete with the time complexity to be $5N+O(1)$ where N is the
total number of qubits within the hardware architecture. Later, we will show
that for general cases where there is an arbitrary number of dangling points,
the complexity is at most $6N+O(1)$.

###  3.1. Correctness Analysis

Guaranteeing the correctness of our implementation is always the first
priority. We verify the correctness of QFT gate execution in 2 major aspects.
First, we check whether or not all CPHASE gates have been executed.
Specifically, in a heavy-hex architecture with N qubits, there should be one
CPHASE gate per qubit pair and hence unduplicated $\frac{N(N-1)}{2}$ CPHASE
gates in total. In addition, all these gate executions should follow the
dependency constraints in QFT, e.g., any $q_{i}$ cannot take the control qubit
role before the completion of all CPHASE gates where $q_{i}$ is the target
qubit.

Figure 7. Initial mapping for Heavy-hex with 5n qubits (with 5 qubits per
group). Figure 8. Final mapping for Heavy-hex with 5n qubits (with 5 qubits
per group).

Gate count verification. As is shown in Table 1, the simulator collects the
information of $\\#$ depth, $\\#$ SWAP and the $\\#$ CPHASE. It passes the
verification that $\\#$ CPHASE = $\frac{N(N-1)}{2}$ empirically.

Gate operation dependency verification. Furthermore, we should guarantee no
duplicate CPHASE operations and that all gate operations follow the dependency
relationship. As we can check from our proposal, The proof starts from
understanding the path of each qubit. Figure 9 plots all possible paths for
each qubit during the QFT mapping process. In general, each qubit has at least
two phases: moving to the left until it hits the end and then moving in the
right direction. Two additional actions may happen, such that one node moves
down to a dangling point or out of a dangling point.

When one qubit moves to the left, it will meet all qubits whose number is
smaller than itself; every time it is adjacent to another qubit with a smaller
index, there is a CPHASE gate execution in between. Therefore, before reaching
the leftmost position, all qubits have completed the CPHASE gate operations,
where they act as target qubits. As this qubit moves to the right, it would
play the control-qubit role in CPHASE gate operation. This ensures all
necessary CPHASE gate operations follow the gate operation dependency
described before and are executed once and exactly once during our scheduling
algorithm.

In terms of those qubits whose initial or final positions are in the dangling
position. Depending on the initial place of the qubits and the qubit’s index,
it might need an extra step to move up from the dangling position and an extra
step to move down to the dangling position (its final destination). This would
not cause any issues either because each time one qubit arrives at a position
where the qubit below has a larger number, there would be a CPHASE gate
followed by a SWAP gate in between, which sets the qubit with a smaller number
to its final destination and initiates the move for the qubit with a larger
number. Then it will follow the mapping order described in the paragraph
above.

Figure 9. All possible paths for each qubit during QFT mapping. Black path is
required for all qubits while red path is only for qubits whose initial/final
position is in dangling nodes.

Such analysis proves the correctness of our proposed QFT mapping algorithm.

Architecture | # qubits | Our approach
---|---|---
|  | Depth | # SWAP | # CPHASE
Heavy-hex | 2*5 | 39 | 40 | 45
Heavy-hex | 3*5 | 64 | 90 | 105
Heavy-hex | 4*5 | 89 | 160 | 190
Heavy-hex | 5*5 | 114 | 250 | 300
Heavy-hex | 6*5 | 139 | 360 | 435
Heavy-hex | 7*5 | 164 | 490 | 595
Heavy-hex | 8*5 | 189 | 640 | 780
Table 1. Resource usage of our approach over heavy-hex configurations with
different # qubits. Assuming there are 5 qubits per group, 4 of which are in
major line and the remaining one is the dangling point.

###  3.2. Time Complexity

####  3.2.1. Complexity for this special case

One benefit of our initial mapping design is that when adding a new qubit
group into the architecture, the labeling of the previous qubits keeps
unchanged. This means that a lot of gate operations will be overlapped.
Specifically, comparing heavy-hex architecture with 5n qubits vs that with
5(n+1) qubits, several steps would execute the same or similar gate
operations. For instance, in Figure 11, in a heavy-hex architecture with
5(n+1) qubits, before $q_{n-1}$ arrives at its final location (the penultimate
member of the dangling positions), every gate operation in each step identical
with that architecture with 5n qubits.

Figure 10. The place where extra steps appear. The LHS is the QFT mapping for
architecture with n groups while the RHS is for architecture with (n+1)
groups. They share the same cycles in transition 1 and transition 2 but the
RHS has to use added steps to complete additional gate operations for newly
added qubits.

Hence, instead of directly calculating the time complexity, we could leverage
the architecture features in our initial mapping and only focus on the extra
steps required for an added qubit group. Then, the time complexity could be
achieved by induction proof.

Figure 10 decouples the QFT mapping into multiple states and captures the
added portion if we add one more group into the architecture. To get the extra
steps, we should pay attention to just the operation over the physical qubits
rather than the logical qubits. The LHS of Figure 10 divides the QFT mapping
for 5n qubits into three states: initial state, the state when the qubit with
the biggest number $q_{5n-1}$ is one step before $q_{n}$, and the final state.
Let’s use $Q_{k}$ to label the physical qubit where $q_{5n-1}$ sits after
transition 1. Compared with the version where there are 5n + 5 qubits in the
RHS, the added steps occur to move $q_{n}$ to its final destination after
transition 1 and move the qubit with the biggest number $q_{5n+4}$ to physical
qubit $Q_{k}$. The remaining steps are overlapped.

As for the added steps, we divide them into 2 phases shown in Figure 11. The
first phase is to move $q_{n}$ forward until its final destination is located
at the end of dangling positions; the second phase is to move $q_{5n+4}$
backward to the places where $q_{5n-2}$ sits before phase 1. There are ten
steps in the first phase to move $q_{n}$ forward until the last location of
the dangling positions, and another 15 steps are necessary in the second phase
to move $q_{5n+4}$ backward to the correct place.

Figure 11. Extra steps required for one added qubit group. The top figure
shows the steps in the first phase, while the bottom figure shows that in the
second phase.

After summing up the steps of these 2 phases, here is the conclusion that each
time we add another pattern that consists of 5 qubits, we need an extra 25
steps to complete the QFT mapping. Therefore, as the number of qubits grows,
the time complexity would be 5N $+O(1)$, where N is the total number of qubits
in the heavy-hex architecture.

Considering the fact that the QFT mapping algorithm in (Zhang et al., 2021)
with complexity 4N+O(1) works for LNN architecture where we could connect all
qubits within one line, the target of our architecture is a much more complex
coupling graph so the proposed QFT approach completes with a slightly higher
time complexity 5N+O(1).

####  3.2.2. Upper bound for general cases.

In addition to the We also calculate the upper bound for a general case where
there are N1 qubits in the major line with N2 dangling nodes (label them as
$q_{k_{0}}$ … $q_{k_{N2-1}}$) in the dangling positions. However, the distance
between 2 nearby dangling nodes might be different.

In order to calculate the upper bound, we could decompose the whole QFT
mapping process into multiple parts. There could be potential opportunities to
merge steps among different parts, but the focus here is to get the upper
bounds. We leave the next-step optimization to future work. The concrete
description of the different parts is as follows:

Part I: QFT mapping in the major line only. As for this part, we could
leverage the results from (Zhang et al., 2021). It shows that the QFT mapping
over an LNN consists of phases with only CPHASE gate operations and with SWAP
operations. In a straight line with N1 qubits, there are 2*N1-3 CPHASE cycles
and 2*N1-3 SWAP cycles. Therefore, the total number of cycles is 4*N1-6.

Part II: interaction between the major line and dangling points. This part can
be divided into two categories. The first category is related to the steps
required to SWAP the qubit in the major line with the dangling point above.
Specifically, given there are N2 dangling points, the final mapping shows that
qubits from $q_{0}$ to $q_{N2-1}$ should finally be located in the dangling
position. This means a SWAP operation is required to change the location
between $q_{i}$ and the dangling qubit above when it reaches the “T junction”
above its final destination from the left. In addition to the SWAP operation,
there is a CPHASE operation before, so for each of these N2 qubits, it needs
an extra 2 phases to do such interaction, and the total time complexity is
2*N2; the second category is related to the CPHASE gate operation between
dangling points and major lines where the dangling qubit is used as the
control qubit. These steps should be added when the major line is doing LNN
QFT mapping. As we can see from the existing QFT mapping over LNN, there will
be interleaving between CPHASE and SWAP cycles. The CPHASE cycle will do
CPHASE gate operations, not changing the relative qubit position while SWAP
cycle will change some qubits’ position. Therefore, the extreme case is that
every time we have a SWAP cycle, we need to stop for another cycle to allow
this second category of CPHASE gate operations. The total time complexity is
2*N1-3.

By summing up the complexity from Part I and II, we could get the upper bound
of our approach, which is 6N1 - 9 + 2N2. Since there is a known fact that
$N1+N2=N$, $N1\leq N$, and $N2\leq N$, the upper bound time complexity is
2N+4N1+O(1) $\leq$ 6N+O(1). As for a sanity check, in our special case where
N1=$\frac{4}{5}$N, we could get the upper bound time complexity to be
5.2N+O(1), which is bigger than the actual time complexity, 5N+O(1).

##  4\. Conclusion

We introduce a new approach to do QFT scheduling over the currently emerging
IBM heavy-hex architecture by considering it as a coupling graph with major
row and dangling qubits. Compared with state-of-the-art approaches, the
scheduling result we generate uses fewer usage of circuit depth. We hope our
results will encourage engineers to transplant such an idea to do qubit
mapping for more emerging quantum algorithms over this architecture in the
future.

## References

  * (1)
  * Jin et al. (2023) Yuwei Jin, Xiangyu Gao, Minghao Guo, Henry Chen, Fei Hua, Chi Zhang, and Eddy Z. Zhang. 2023.  Quantum Fourier Transformation Circuits Compilation.  (2023).  arXiv:quant-ph/2312.16114
  * Li et al. (2019) Gushu Li, Yufei Ding, and Yuan Xie. 2019.  Tackling the qubit mapping problem for NISQ-era quantum devices.  Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (2019), 1001–1014.
  * Maslov (2007) Dmitri Maslov. 2007.  Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures.  Physical Review A 76, 5 (Nov 2007).  https://doi.org/10.1103/physreva.76.052310
  * Molavi et al. (2022) A. Molavi, A. Xu, M. Diges, L. Pick, S. Tannu, and A. Albarghouthi. 2022.  Qubit Mapping and Routing via MaxSAT. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO). IEEE Computer Society, Los Alamitos, CA, USA, 1078–1091.  https://doi.org/10.1109/MICRO56248.2022.00077
  * Murali et al. (2019) Prakash Murali, Jonathan M. Baker, Ali Javadi Abhari, Frederic T. Chong, and Margaret Martonosi. 2019.  Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers.  Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (4 2019), 1015–1029.  https://doi.org/10.1145/3297858.3304075
  * Shor (1994) Peter W. Shor. 1994.  Algorithms for quantum computation: Discrete logarithms and factoring.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (1994).  https://doi.org/10.1109/SFCS.1994.365700
  * Tan et al. (2022) Bochen Tan, Dolev Bluvstein, Mikhail D. Lukin, and Jason Cong. 2022.  Qubit Mapping for Reconfigurable Atom Arrays. In Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design (ICCAD ’22). Association for Computing Machinery, New York, NY, USA, Article 107, 9 pages.  https://doi.org/10.1145/3508352.3549331
  * Tan and Cong (2020) Bochen Tan and Jason Cong. 2020.  Optimal Layout Synthesis for Quantum Computing.  Proceedings of the 39th International Conference on Computer-Aided Design (2020).  https://doi.org/10.1145/3400302.3415620
  * Zhang et al. (2021) Chi Zhang, Ari B Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Eddy Z Zhang. 2021.  Time-Optimal Qubit Mapping (ASPLOS 2021). Association for Computing Machinery, New York, NY, USA, 360–374.  https://doi.org/10.1145/3445814.3446706