long time will achieve a thermal equilibrium which erases the initial
condition, the MBL system as an isolated many-body quantum system resists such
thermalization — in a local subsystem the information of the initial state is
remembered forever. While a theoretical understanding of MBL still remains
challenging since its introduction by Anderson in 1958 [5], tremendous
numerical works on various systems have been conducted through recent years
(for example, see [82, 4, 1] for reviews). A typical example for numeric
studies of MBL is one-dimensional Heisenberg model [82, 78, 38]. Due to the
difficulty of simulating many-body dynamics classically, quantum simulations
can investigate properties of MBL in larger systems intractable for classical
computers.

Following [38], we consider the problem of simulating the one-dimensional
nearest-neighbor Heisenberg model with a random magnetic field in the $z$
direction. More concretely, we will simulate an $n$-qubit Hamiltonian

$H=\sum_{w\in[n]}\left\lparen
X_{w}X_{w+1}+Y_{w}Y_{w+1}+Z_{w}Z_{w+1}+h_{w}Z_{w}\right\rparen,$ (22)

where $h_{w}\in[-1,1]$ is chosen uniformly at random, the subscript $w$
indicates the qubit $w$ that the Pauli matrix acts on, and $w=n$ is equivalent
to $w=0$ by assuming the periodic boundary conditions.

First observe that $H$ is a $(2,n)$-local Hamiltonian with local clause
$H_{w}:=X_{w}X_{w+1}+Y_{w}Y_{w+1}+Z_{w}Z_{w+1}+h_{w}Z_{w}$ for $w\in[n]$. The
locality of $H_{w}$ is indicated by an $n$-bit string $s(w)$ with the
$u^{\text{th}}$ bit defined as

$s(w)_{u}:=[\\![w=u\vee w+1=u]\\!]$

for all $u\in[n]$, given by the oracle $\mathcal{O}_{P}$ as in Lemma 3.28.
Then by Lemma 3.28, $H$ is $m$-uniform-structured with $m=n$, thus we can
apply Theorem 5.5 to simulate $H$. For comparison, take the simulation time
$t=n$ as in [38]. Since $\left\lVert
H\right\rVert_{\max}\leq\sum_{w\in[n]}\left\lVert
H_{w}\right\rVert_{\max}=O\left\lparen n\right\rparen$, to simulate $H$ for
time $t$, it is equivalent to simulate a normalized $H$ with max norm $\leq 1$
for a rescaled time $\tilde{t}:=\lVert H\rVert_{\max}t=O\left\lparen
n^{2}\right\rparen$. Thus we can determine the parameters in Theorem 5.5:
$\tau=O\left\lparen n^{3}\right\rparen$, $\gamma=O\left\lparen\log\left\lparen
n/\epsilon\right\rparen\right\rparen$ and $b=O\left\lparen\log\left\lparen
n/\epsilon\right\rparen\right\rparen$.

For the total complexity of the algorithm, one should also compute the gate
complexities for implementing the oracle $\mathcal{O}_{H}^{b}$ and
$\mathcal{O}_{P}$.

  * •

To implement $\mathcal{O}_{P}$, that is, to perform the mapping
$\ket{w}\ket{0}\mapsto\ket{w}\ket{s(w)}$, one can first prepare the state
$\ket{0,\ldots,n-1}$ in the second register, then make $n$ copies of $\ket{w}$
by applying $\mathrm{COPY}_{n}^{\lceil\log n\rceil}$, and finally calculate
each Boolean function $s(w)_{u}$ for $u\in[n]$ in parallel followed by garbage
cleaning. Together with Lemma 2.6, this can be done by $O\left\lparen\log
n\right\rparen$-depth and $O\left\lparen n\log n\right\rparen$-size of gates.

  * •

To implement $\mathcal{O}_{H}^{b}$, one needs to first generate $n$ uniform
random $h_{w}\in[-1,1]$ to $b$-bit precision in the preprocessing. This can be
done by $O\left\lparen 1\right\rparen$-depth and $O\left\lparen
nb\right\rparen$-size of Hadamard gates followed by single-qubit measurements.
The preprocessing only needs to be done once. Later when a $h_{w}$ is required
each time we can apply a $\mathrm{COPY}^{b}$ gate to prepare a new copy of it.

To perform the mapping $\ket{j,k,0}\mapsto\ket{j,k,H_{jk}}$, one can calculate
an entry $H_{jk}$ by summing up those $\left\lparen H_{w}\right\rparen_{jk}$
with $\left\lparen j,k\right\rparen\in\mathsf{H}_{w}$. Recall that
$[\\![\left\lparen j,k\right\rparen\in\mathsf{H}_{w}]\\!]$ is arithmetic-
depth-efficiently computable for uniform-structured $H$, and $\left\lparen
H_{w}\right\rparen_{jk}$ is easy to determine given a copy of $h_{w}$,
therefore the above procedure can be implemented by an
$O\left\lparen\log^{2}n+\log b\right\rparen$-depth and $O\left\lparen
n^{5}+nb\right\rparen$-size quantum circuit (in a way analogous to computing
$c(j,k)$ in the proof of Lemma A.3).

Thus, we obtain the following:

######  Corollary 7.1 (Parallel simulation of the Heisenberg model).

The Heisenberg Hamiltonian defined in (22) can be simulated for time $t=n$ to
precision $\epsilon$ by $O\left\lparen
n^{3}\log^{3}n\cdot\log^{3}\log\left\lparen
1/\epsilon\right\rparen\right\rparen$-depth and $O\left\lparen
n^{8}\log^{5}\left\lparen n/\epsilon\right\rparen\right\rparen$-size of
quantum gates.

In [38] the performance of different quantum simulation algorithms on this
task are compared, amongst which the asymptotically best one is based on
quantum signal processing [74, 73], which achieves a gate complexity
$O\left(n^{3}\log
n+\frac{\log\left(1/\epsilon\right)}{\log\log\left(1/\epsilon\right)}\cdot
n\log n\right)$. Later a quantum algorithm to simulate lattice Hamiltonians
[59] shows a better dependence on $n$ in the gate complexity, consisting of
$O\left\lparen n\operatorname{polylog}\left\lparen
n/\epsilon\right\rparen\right\rparen$-depth and $O\left\lparen
n^{2}\operatorname{polylog}\left\lparen
n/\epsilon\right\rparen\right\rparen$-size of gates. We note that in the gate
depth all these works have a $\operatorname{polylog}\left\lparen
1/\epsilon\right\rparen$ dependence, while Corollary 7.1 only contains a
$\operatorname{polylog}\log\left\lparen 1/\epsilon\right\rparen$ factor.

###  7.2 Simulation of the Sachdev-Ye-Kitaev Model

The Sachdev-Ye-Kitaev (SYK) model [90, 66], a simple but important exactly
solvable many-body system, has drawn an increasing interest in the condense
matter physics and high energy physics communities due to its many striking
properties [90, 66, 80, 86, 88] and its potential to have an interesting
holographic dual [66, 80]. Like the MBL problem in Section 7.1, numeric
studies of a larger SYK model enabled by quantum simulation could extend our
understandings about its features and dual interpretation.

Following [49, 11], we consider the problem of simulating the SYK model
evolving under a Hamiltonian

$H=\frac{1}{4\cdot
4!}\sum_{p,q,r,s=0}^{2n-1}J_{pqrs}\gamma_{p}\gamma_{q}\gamma_{r}\gamma_{s},$
(23)

where each $J_{pqrs}\sim\mathcal{N}\left\lparen 0,\sigma^{2}\right\rparen$ is
chosen randomly from a normal distribution with variance
$\sigma^{2}=\frac{3!J^{2}}{\left\lparen 2n\right\rparen^{3}}$ ($J$ is assumed
to be a constant), and $\gamma_{p}$ are Majorana fermion operators such that
$\left\\{\gamma_{p},\gamma_{q}\right\\}=2\left[\\![p=q\right]\\!]\mathbbm{1}$.
The Majorana operator can be expressed as a tensor product of Pauli matrices
by the Jordan-Wigner transformation

$\gamma_{p}\mapsto\begin{cases}Z_{0}\ldots Z_{p/2-1}X_{p/2}&\text{$p$ is
even}\\\ Z_{0}\ldots Z_{\left\lparen p-3\right\rparen/2}Y_{\left\lparen
p-1\right\rparen/2}&\text{$p$ is odd}\end{cases}$ (24)

for $p\in[2n]$ (unlike in [49], our index starts from $0$), where as usual the
subscript of a Pauli matrix indicates the qubit it acts on. Now $H$ can be
expressed as a Pauli sum on $n$ qubits:

$H=\alpha\sum_{w\in[2n]^{4}}J_{w}H_{w}$ (25)

where $\alpha$ is a constant, $J_{w}$ is chosen randomly from a normal
distribution, and each $H_{w}$ is a tensor product of Pauli matrices.

It can be seen by Lemma 3.27 that the SYK Hamiltonian in (25) is $m$-uniform-
structured with $m=(2n)^{4}$, thus we can apply Theorem 5.5 to simulate it.
Note that

$\left\lVert H\right\rVert_{\max}\leq\sum_{w\in[2n]^{4}}\alpha\left\lVert
J_{w}H_{w}\right\rVert_{\max}\leq\sum_{w\in[2n]^{4}}\alpha\mathop{\bf
E\/}\left[\left\lvert J_{w}\right\rvert\right]=\alpha\left\lparen
2n\right\rparen^{4}\cdot\frac{\sqrt{2}\sigma}{\sqrt{\pi}}=O\left\lparen
n^{2.5}\right\rparen$

where we use $J_{w}\sim\mathcal{N}\left\lparen 0,\sigma^{2}\right\rparen$ with
$\sigma^{2}=O\left\lparen 1/n^{3}\right\rparen$. Thus, to simulate $H$ for
time $t$, it is equivalent to simulate its normalized Hamiltonian with max
norm $\leq 1$ for a rescaled time $\tilde{t}:=\lVert
H\rVert_{\max}t=O\left\lparen n^{2.5}t\right\rparen$. We can determine the
parameters in Theorem 5.5: $\tau=O\left\lparen n^{6.5}t\right\rparen$,
$\gamma=O\left\lparen\log\left\lparen nt/\epsilon\right\rparen\right\rparen$
and $b=O\left\lparen\log\left\lparen nt/\epsilon\right\rparen\right\rparen$.

For the total complexity of the algorithm, we starts from defining
$\mathcal{P}:[2n]^{4}\rightarrow\left\\{1,i,-1,-i\right\\}\times\left\\{\mathbbm{1},X,Y,Z\right\\}^{n}\simeq[4]^{n+1}$
to be a function that maps $w\in[m]$ to the Pauli string (with a global phase)
of $H_{w}$. For example, if $H_{w}=-iX\otimes Z\otimes Z$ then
$\mathcal{P}(w)=\left\lparen-i,X,Z,Z\right\rparen$. One can also write the
Jordan-Wigner transformation in (24) as a function
$\mathcal{J}:[2n]\rightarrow\left\\{\mathbbm{1},X,Y,Z\right\\}^{n}\simeq[4]^{n}$,
which can be computed by an $O\left\lparen\log n\right\rparen$-depth and
$O\left\lparen n\log n\right\rparen$-size quantum circuit. To see this, that
is, to perform the mapping
$\ket{p}\ket{0}\mapsto\ket{p}\ket{\mathcal{J}\left\lparen p\right\rparen}$, we
can first prepare the state $\ket{0,\ldots,n-1}$ in the second register, then
make $n$ copies of $\ket{p}$, and finally compute the $q^{\text{th}}$ bit of
$\mathcal{J}\left\lparen p\right\rparen$:

$\mathcal{J}\left\lparen
p\right\rparen_{q}:=\begin{cases}3[\\![q<p/2]\\!]+[\\![q=p/2]\\!]&\text{$p$ is
even}\\\ 3[\\![q<(p-1)/2]\\!]+2[\\![q=(p-1)/2]\\!]&\text{$p$ is
odd}\end{cases}\in[4]$

for all $q\in[n]$ in parallel followed by garbage cleaning. By Lemma 2.6, this
can be done by $O\left\lparen\log n\right\rparen$-depth and $O\left\lparen
n\log n\right\rparen$-size of gates. Since for all $(p,q,r,s)\in[2n]^{4}$, the
function $\mathcal{P}\left\lparen p,q,r,s\right\rparen$ can be computed from
$\mathcal{J}\left\lparen p\right\rparen,\mathcal{J}\left\lparen
q\right\rparen,\mathcal{J}\left\lparen r\right\rparen,\mathcal{J}\left\lparen
s\right\rparen$ by calculating Pauli algebra on each entry of these $n$-tuples
and gathering up the global phases, $\mathcal{P}\left\lparen w\right\rparen$
can be computed by an $O\left\lparen\log n\right\rparen$-depth and
$O\left\lparen n\log n\right\rparen$-size quantum circuit.

Now we will determine the gate complexities for implementing the oracle
$\mathcal{O}_{H}^{b}$ and $\mathcal{O}_{P}$:

  * •

To implement $\mathcal{O}_{P}$, note that $s(w)$ in Lemma 3.27 is easily
computable from $\mathcal{P}(w)$ by function restriction, thus
$\mathcal{O}_{P}$ can be implemented by $O\left\lparen\log
n\right\rparen$-depth and $O\left\lparen n\log n\right\rparen$-size of gates.

  * •

To implement $\mathcal{O}_{H}^{b}$, one needs to first generate $m$
independent $J_{w}\in\mathcal{N}\left\lparen 0,\sigma^{2}\right\rparen$ to
$b$-bit precision in the preprocessing. This can be done by the Box-Muller
transform [24], which derives two independent standard normally distributed
variables from two independent uniformly distributed variables in $[0,1]$ by
elementary arithmetics. Thus it suffices to generate $m$ uniformly random
variables in $[0,1]$ to $b$-bit precision by $O\left\lparen
1\right\rparen$-depth and $O\left\lparen n^{4}b\right\rparen$-size of Hadamard
gates followed by single-qubit measurements, and then use Lemma 2.6 to perform
the Box-Muller transform with a scaling $\sigma$ by an
$O\left\lparen\log^{2}b\right\rparen$-depth and $O\left\lparen
n^{4}b^{4}\right\rparen$-size quantum circuit. The preprocessing only needs to
be done once. Later when a $J_{w}$ is required each time we can apply a
$\mathrm{COPY}^{b}$ gate to make a new copy of it.

We perform the mapping $\ket{j,k,0}\mapsto\ket{j,k,H_{jk}}$ in a way similar
to the one in Section 7.1; that is, sum up those $\left\lparen
H_{w}\right\rparen_{jk}$ with $\left\lparen
j,k\right\rparen\in\mathsf{H}_{w}$. Recall that each $[\\![\left\lparen
j,k\right\rparen\in\mathsf{H}_{w}]\\!]$ is arithmetic-depth-efficiently
computable for uniform-structured $H$, and $\left\lparen
H_{w}\right\rparen_{jk}$ is easy to compute from the function $\mathcal{P}(w)$
and a copy of $J_{w}$. Therefore, the above procedure can be implemented by an
$O\left\lparen\log^{2}n+\log b\right\rparen$-depth and $O\left\lparen
n^{8}+n^{4}b\right\rparen$ quantum circuit (in a way analogous to the proof of
Lemma A.3).

Applying Theorem 5.5, we obtain the following:

######  Corollary 7.2 (Parallel simulation of the SYK model).

The SYK model defined in (23) can be simulated for time $t$ to precision
$\epsilon$ by $O\left\lparen n^{6.5}\log^{3}n\cdot t\log^{3}\log\left\lparen
t/\epsilon\right\rparen\right\rparen$-depth and $O\left\lparen
n^{14.5}t\log^{5}\left\lparen nt/\epsilon\right\rparen\right\rparen$-size of
quantum gates.

The prior best algorithm based on asymmetric qubitization [11] for this task
has gate complexity $O\left\lparen
n^{3.5}t+n^{2.5}t\operatorname{polylog}\left\lparen
n/\epsilon\right\rparen\right\rparen$, which improves the product-formula-
based algorithm [49] with gate complexity $O\left\lparen
n^{10}t^{2}/\epsilon\right\rparen$. Later work [98] proposes a sparse SYK
model also of physical interest and gives a simulation algorithm based on
qubitization with a $\operatorname{polylog}\left\lparen
1/\epsilon\right\rparen$ dependence in the gate complexity. Compared to these
works, by introducing parallelism Corollary 7.2 only has a
$\operatorname{polylog}\log\left\lparen 1/\epsilon\right\rparen$ dependence in
the gate depth.

###  7.3 Simulation of Quantum Chemistry in Second Quantization

One of the most attractive prospects of quantum simulation is in quantum
chemistry to study the static and dynamic properties of chemicals [101, 31,
14]. Prior works on quantum simulation algorithm for chemistry mainly focus on
exploiting the special structure of molecular Hamiltonians (e.g. based on
first or second quantization, using Gaussian orbital bases or plane wave
bases, etc.) to obtain better complexities (see [14] for a review). Compared
to these fault-tolerant quantum algorithms, diverse variational quantum
algorithms to circumvent a direct simulation (e.g. variational quantum
eigensolver [84]) also have been explored in recent years due to their
potential for immediate applications in the NISQ era [7].

Following [9] we consider the problem of simulating a molecular electronic
structure Hamiltonian in the second-quantized form. In this form, we will
simulate a Hamiltonian

$H=\sum_{p,q\in[n]}h_{pq}a_{p}^{\dagger}a_{q}+\frac{1}{2}\sum_{p,q,r,s\in[n]}h_{pqrs}a_{p}^{\dagger}a_{q}^{\dagger}a_{r}a_{s}$
(26)

where $n$ represents the number of spin orbitals, $h_{pq},h_{pqrs}$ are one-
electron and two-electron integrals, and $a_{p}^{\dagger},a_{p}$ are fermionic
creation and annihilation operators satisfying the relations

$\left\\{a_{p}^{\dagger},a_{q}\right\\}=\left[\\![p=q\right]\\!]\mathbbm{1},\qquad\left\\{a_{p}^{\dagger},a_{q}^{\dagger}\right\\}=\left\\{a_{p},a_{q}\right\\}=0.$

As in the “database” algorithm [9], we assume that these $b$-bit precise
$h_{pq}$ and $h_{pqrs}$ are precomputed and stored in a database; for example,
an $O\left\lparen(nb)^{4}\right\rparen$-size quantum-read/classical-write RAM
(QCRAM), to which one quantum access can be performed by
$O\left\lparen\log\left\lparen nb\right\rparen\right\rparen$-depth and
$O\left\lparen(nb)^{4}\right\rparen$-size of gates.

One can apply Jordan-Wigner transformation to the creation and annihilation
operators $a_{p}^{\dagger},a_{p}$ to obtain Hamiltonians acting on qubits:

$\displaystyle a_{p}^{\dagger}$ $\displaystyle\mapsto\frac{1}{2}Z_{0}\ldots
Z_{p-2}\left\lparen X_{p-1}-iY_{p-1}\right\rparen$ (27) $\displaystyle a_{p}$
$\displaystyle\mapsto\frac{1}{2}Z_{0}\ldots Z_{p-2}\left\lparen
X_{p-1}+iY_{p-1}\right\rparen$ (28)

for $p\in[n]$, where as usual the subscript of a Pauli matrix indicates the
qubit it acts on. Note that each resulting qubit Hamiltonian in (27) and (28)
is a sum of two tensor products of Pauli matrices, hence by splitting them and
applying the transformation to (26) we obtain $H$ as a Pauli sum on $n$
qubits:

$H=\sum_{w\in[m]}h_{w}H_{w},$ (29)

where $m=O\left\lparen n^{4}\right\rparen$, each $h_{w}$ is some $h_{pq}$ or
$h_{pqrs}$ in (26) (up to a constant factor), and each $H_{w}$ is a tensor
product of Pauli matrices. Here we omit the explicit mapping from the indices
$p,q,r,s$ in (26) to the index $w$ in (29), but mention that the mapping can
be efficiently performed by $O\left\lparen 1\right\rparen$-size of gates.

Similar to the SYK model, we see by Lemma 3.27 that the molecular Hamiltonian
$H$ in (29) is $m$-uniform-structured with $m=O\left\lparen
n^{4}\right\rparen$. According to [9], we have $\sum_{w\in[m]}\left\lvert
h_{w}\right\rvert=O\left\lparen n^{4}\right\rparen$. Thus the max norm of $H$
is bounded by $\lVert H\rVert_{\max}\leq\sum_{w\in[m]}\lVert
h_{w}H_{w}\rVert_{\max}\leq\sum_{w\in[m]}\left\lvert
h_{w}\right\rvert=O\left\lparen n^{4}\right\rparen$. To simulate $H$ for time
$t$ it is equivalent to simulate its normalized Hamiltonian for a rescaled
time $\tilde{t}:=\lVert H\rVert_{\max}t=O\left\lparen n^{4}t\right\rparen$.
The parameters in Theorem 5.5 can be determined as follows:
$\tau=O\left\lparen n^{8}t\right\rparen$,
$\gamma=O\left\lparen\log\left\lparen nt/\epsilon\right\rparen\right\rparen$
and $b=O\left\lparen\log\left\lparen nt/\epsilon\right\rparen\right\rparen$ .

Now let us compute the gate complexities for implementing the oracle
$\mathcal{O}_{H}^{b}$ and $\mathcal{O}_{P}$:

  * •

The construction of $\mathcal{O}_{P}$ is similar to the one in Section 7.2.
Here we will omit the details and claim that it can be implemented by an
$O\left\lparen\log n\right\rparen$-depth and $O\left\lparen n\log
n\right\rparen$-size quantum circuit.

  * •

To implement $\mathcal{O}_{H}^{b}$, that is, to perform the mapping
$\ket{j,k,0}\mapsto\ket{j,k,H_{jk}}$, we sum up those $\left\lparen
H_{w}\right\rparen_{jk}$ with $\left\lparen j,k\right\rparen\in\mathsf{H}_{w}$
to obtain $H_{jk}$. Recall that $[\\![\left\lparen
j,k\right\rparen\in\mathsf{H}_{w}]\\!]$ is arithmetic-depth-efficiently
computable for uniform-structured $H$. Also $\left\lparen
H_{w}\right\rparen_{jk}$ is easy to compute given: a copy of $h_{w}$ which can
be read out from the database by $O\left\lparen\log\left\lparen
nb\right\rparen\right\rparen$-depth and
$O\left\lparen(nb)^{4}\right\rparen$-size of gates; together with a string
characterizing the Pauli string of $H_{w}$ (like the function $\mathcal{P}(w)$
for the SYK model) computable by $O\left\lparen\log n\right\rparen$-depth and
$O\left\lparen n\log n\right\rparen$-size of gates. Therefore the above
procedure can be implemented by an $O\left\lparen\log^{2}n+\log
b\right\rparen$-depth and $O\left\lparen n^{8}b^{4}\right\rparen$-size quantum
circuit (in a way analogous to the proof of Lemma A.3).

As an application of Theorem 5.5, we have the following:

######  Corollary 7.3 (Parallel simulation of molecular Hamiltonians).

The molecular Hamiltonian defined in (26) can be simulated for time $t$ to
precision $\epsilon$ by $O\left\lparen n^{8}\log^{3}n\cdot
t\log^{3}\log\left\lparen t/\epsilon\right\rparen\right\rparen$-depth and
$O\left\lparen n^{16}t\log^{5}\left\lparen
nt/\epsilon\right\rparen\right\rparen$-size of gates.

Prior work [9] gives a quantum simulation algorithm for molecular Hamiltonians
with gate complexity $O\left\lparen\frac{n^{8}t\log\left\lparen
nt/\epsilon\right\rparen}{\log\log\left\lparen
nt/\epsilon\right\rparen}\right\rparen$. Later algorithmic improvements (e.g.
[12, 13, 67, 10, 23]) focus on parameters other than the precision $\epsilon$,
and all these works have a poly-logarithmic dependence on $\epsilon$ as the
Hamiltonian simulation subroutines used there have such dependence. By
allowing parallelism, Corollary 7.3 exponentially improves the dependence to
$\operatorname{polylog}\log\left\lparen 1/\epsilon\right\rparen$ with respect
to the depth.

##  8 Discussion

In this paper, we proposed a parallel quantum algorithms for Hamiltonian
simulation that achieves a doubly (poly-)logarithmic precision dependence in
the depth complexity. Thus, for the first time it is shown that parallelism
can provide a significant speed-up in the Hamiltonian simulation problem. This
result is achieved by introducing a novel notion of parallel quantum walk and
identifying a class of Hamiltonians, called uniform-structured Hamiltonians,
for which the simulation can be executed efficiently in parallel. We believe
that the techniques developed in this paper can be applied to design other
parallel quantum algorithms.

In our work, the dependence on the simulation precision $\epsilon$ is improved
from $\operatorname{polylog}\left\lparen 1/\epsilon\right\rparen$ to
$\operatorname{polylog}\log\left\lparen 1/\epsilon\right\rparen$ by
parallelization. One open question, as mentioned in Section 1.3, is whether
parallelization can improve the dependence on the simulation time $t$; more
precisely, what kind of Hamiltonians can be simulated for time $t$ by a
quantum circuit with depth $\operatorname{polylog}\lparen t\rparen$, by
allowing parallel queries?

Intuitively, the power of parallelism is provided by the use of ancilla
qubits. We have not explicitly counted the number of ancillae used in our
parallel quantum algorithm, but it obviously depends on the precision
$\epsilon$. Therefore, another question for future research is how many
ancillae are required for a significant parallel speed-up? More generally, the
trade-off between the circuit depth and the number of ancillae will be be an
interesting issue in the studies of more parallel quantum algorithms.

## References

  * [1] Dmitry A. Abanin, Ehud Altman, Immanuel Bloch and Maksym Serbyn  “Colloquium: Many-body localization, thermalization, and entanglement”  In _Reviews of Modern Physics_ 91, 2019, pp. 021001
  * [2] Dmitry A. Abanin and Zlatko Papić  “Recent progress in many-body localization”  In _Annalen der Physik_ 529.7, 2017, pp. 1700169
  * [3] Dorit Aharonov and Amnon Ta-Shma  “Adiabatic quantum state generation and statistical zero knowledge”  In _Proceedings of the 35th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC ’03, 2003, pp. 20–29
  * [4] Fabien Alet and Nicolas Laflorencie  “Many-body localization: An introduction and selected topics”  In _Comptes Rendus Physique_ 19.6, 2018, pp. 498–525
  * [5] Philip W. Anderson  “Absence of diffusion in certain random lattices”  In _Physical Review_ 109.5, 1958, pp. 1492–1505
  * [6] Joran van Apeldoorn, András Gilyén, Sander Gribling and Ronald de Wolf  “Quantum SDP-solvers: Better upper and lower bounds”  In _Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science_ , FOCS ’17, 2017, pp. 403–414
  * [7] Frank Arute et al.  “Hartree-Fock on a superconducting qubit quantum computer”  In _Science_ 369.6507, 2020, pp. 1084–1089
  * [8] Yosi Atia and Dorit Aharonov  “Fast-forwarding of Hamiltonians and exponentially precise measurements”  In _Nature Communications_ 8.1572, 2017
  * [9] Ryan Babbush, Dominic W. Berry, Ian D. Kivlichan, Annie Y. Wei, Peter J. Love and Alán Aspuru-Guzik  “Exponentially more precise quantum simulation of fermions in second quantization”  In _New Journal of Physics_ 18, 2016, pp. 033032
  * [10] Ryan Babbush, Dominic W. Berry, Jarrod R. McClean and Hartmut Neven  “Quantum simulation of chemistry with sublinear scaling in basis size”  In _npj Quantum Information_ 5.92, 2019
  * [11] Ryan Babbush, Dominic W. Berry and Hartmut Neven  “Quantum simulation of the Sachdev-Ye-Kitaev model by asymmetric qubitization”  In _Physical Review A_ 99, 2019, pp. 040301
  * [12] Ryan Babbush et al.  “Exponentially more precise quantum simulation of fermions in the configuration interaction representation”  In _Quantum Science and Technology_ 3.1, 2017, pp. 015006
  * [13] Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven and Garnet Kin-Lic Chan  “Low-depth quantum simulation of materials”  In _Physic Review X_ 8, 2018, pp. 011044
  * [14] Bela Bauer, Sergey Bravyi, Mario Motta and Garnet Kin-Lic Chan  “Quantum algorithms for quantum chemistry and quantum materials science”  In _Chemical Reviews_ 120.22, 2020, pp. 12685–12717
  * [15] Robert Beals et al.  “Efficient distributed quantum computing”  In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 469.2153, 2013, pp. 20120686
  * [16] Charles H. Bennett  “Logical reversibility of computation”  In _IBM Journal of Research and Development_ 17.6, 1973, pp. 525–532
  * [17] Debajyoti Bera, Frederic Green and Steven Homer  “Small depth quantum circuits”  In _SIGACT News_ 38.2, 2007, pp. 35–50
  * [18] Dominic W. Berry, Graeme Ahokas, Richard Cleve and Barry C. Sanders  “Efficient quantum algorithms for simulating sparse Hamiltonians”  In _Communications in Mathematical Physics_ 270.2, 2006, pp. 359–371
  * [19] Dominic W. Berry and Andrew M. Childs  “Black-box Hamiltonian simulation and unitary implementation”  In _Quantum Information & Computation_ 12.1–2, 2012, pp. 29–62
  * [20] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari and Rolando D. Somma  “Exponential improvement in precision for simulating sparse Hamiltonians”  In _Proceedings of the 46th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC ’14, 2014, pp. 283–292
  * [21] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari and Rolando D. Somma  “Simulating Hamiltonian dynamics with a truncated Taylor series”  In _Physical Review Letters_ 114, 2015, pp. 090502
  * [22] Dominic W. Berry, Andrew M. Childs and Robin Kothari  “Hamiltonian simulation with nearly optimal dependence on all parameters”  In _Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science_ , FOCS ’15, 2015, pp. 792–809
  * [23] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean and Ryan Babbush  “Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization”  In _Quantum_ 3, 2019, pp. 208
  * [24] George E.. Box and Mervin E. Muller  “A note on the generation of random normal deviates”  In _The Annals of Mathematical Statistics_ 29.2, 1958, pp. 610–611
  * [25] Sergey Bravyi, David Gosset and Robert König  “Quantum advantage with shallow circuits”  In _Science_ 362.6412, 2018, pp. 308–311
  * [26] Sergey Bravyi, David Gosset, Robert König and Marco Tomamichel  “Quantum advantage with noisy shallow circuits”  In _Nature Physics_ 16.10, 2020, pp. 1040–1045
  * [27] Anne Broadbent and Elham Kashefi  “Parallelizing quantum circuits”  In _Theoretical Computer Science_ 410.26, 2009, pp. 2489–2510
  * [28] Dan Browne, Elham Kashefi and Simon Perdrix  “Computational depth complexity of measurement-based quantum computation”  In _Theory of Quantum Computation, Communication, and Cryptography_ 6519, 2011, pp. 35–46
  * [29] Paul Burchard  “Lower bounds for parallel quantum counting”, 2019  arXiv:1910.04555 [quant-ph]
  * [30] Earl Campbell  “Random compiler for fast Hamiltonian simulation”  In _Physical Review Letters_ 123, 2019, pp. 070503
  * [31] Yudong Cao et al.  “Quantum chemistry in the age of quantum computing”  In _Chemical Reviews_ 119.19, 2019, pp. 10856–10915
  * [32] Shantanav Chakraborty, András Gilyén and Stacey Jeffery  “The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation”  In _Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)_ 132, 2019, pp. 33:1–33:14
  * [33] Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng and Joel A. Tropp  “Quantum simulation via randomized product formulas: Low gate complexity with accuracy guarantees”, 2020  arXiv:2008.11751 [quant-ph]
  * [34] Nai-Hui Chia, Kai-Min Chung and Ching-Yi Lai  “On the need for large quantum depth”  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , STOC ’20, 2020, pp. 902–915
  * [35] Andrew M. Childs  “On the relationship between continuous- and discrete-time quantum walk”  In _Communications in Mathematical Physics_ 294.2, 2009, pp. 581–603
  * [36] Andrew M. Childs and Robin Kothari  “Simulating sparse Hamiltonians with star decompositions”  In _Theory of Quantum Computation, Communication, and Cryptography_ Springer Berlin Heidelberg, 2011, pp. 94–103
  * [37] Andrew M. Childs, Robin Kothari and Rolando D. Somma  “Quantum algorithm for systems of linear equations with exponentially improved dependence on precision”  In _SIAM Journal on Computing_ 46.6, 2017, pp. 1920–1950
  * [38] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross and Yuan Su  “Toward the first quantum simulation with quantum speedup”  In _Proceedings of the National Academy of Sciences_ 115.38, 2018, pp. 9456–9461
  * [39] Andrew M. Childs, Aaron Ostrander and Yuan Su  “Faster quantum simulation by randomization”  In _Quantum_ 3, 2019, pp. 182
  * [40] Andrew M. Childs and Yuan Su  “Nearly optimal lattice simulation by product formulas”  In _Physical Review Letters_ 123, 2019, pp. 050503
  * [41] Andrew M. Childs and Nathan Wiebe  “Hamiltonian simulation using linear combinations of unitary operations”  In _Quantum Information & Computation_ 12.11–12, 2012, pp. 901–924
  * [42] Carlo Ciliberto et al.  “Quantum machine learning: a classical perspective”  In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 474.2209, 2018, pp. 20170551
  * [43] Richard Cleve and John Watrous  “Fast parallel circuits for the quantum Fourier transform”  In _Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science_ , FOCS ’00, 2000, pp. 526–536
  * [44] Matthew Coudron and Sanketh Menda  “Computations with greater quantum depth are strictly more powerful (relative to an oracle)”  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , STOC ’20, 2020, pp. 889–901
  * [45] Paul K. Faehrmann, Mark Steudtner, Richard Kueng, Maria Kieferova and Jens Eisert  “Randomizing multi-product formulas for improved Hamiltonian simulation”, 2021  arXiv:2101.07808 [quant-ph]
  * [46] Edward Farhi, Jeffrey Goldstone and Sam Gutmann  “A Quantum Approximate Optimization Algorithm”, 2014  arXiv:1411.4028 [quant-ph]
  * [47] Stephen Fenner, Frederic Green, Steven Homer and Yong Zhang  “Bounds on the power of constant-depth quantum circuits”  In _Proceedings of the 15th International Conference on Fundamentals of Computation Theory_ , FCT ’05, 2005, pp. 44–55
  * [48] Richard P. Feynman  “Simulating physics with computers”  In _International Journal of Theoretical Physics_ 21.6–7, 1982, pp. 467–488
  * [49] Laura García-Álvarez, Íñigo Luis Egusquiza, Lucas Lamata, Adolfo del Campo, Julian Sonner and Enrique Solano  “Digital quantum simulation of minimal AdS/CFT”  In _Physical Review Letters_ 119, 2017, pp. 040501
  * [50] András Gilyén, Yuan Su, Guang Hao Low and Nathan Wiebe  “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , STOC ’19, 2019, pp. 193–204
  * [51] Robert M. Gingrich, Colin P. Williams and Nicolas J. Cerf  “Generalized quantum search with parallelism”  In _Physical Review A_ 61, 2000, pp. 052313
  * [52] Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash and William Zeng  “Low depth algorithms for quantum amplitude estimation”, 2020  arXiv:2012.03348 [quant-ph]
  * [53] Frederic Green, Steven Homer, Cristopher Moore and Christopher Pollett  “Counting, fanout and the complexity of quantum ACC”  In _Quantum Information & Computation_ 2.1, 2002, pp. 35–65
  * [54] Frederic Green, Steven Homer and Christopher Pollett  “On the complexity of quantum ACC”  In _Proceedings 15th Annual IEEE Conference on Computational Complexity_ , 2000, pp. 250–262
  * [55] Lov K. Grover  “A fast quantum mechanical algorithm for database search”  In _Proceedings of the 28th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC ’96, 1996, pp. 212–219
  * [56] Lov K. Grover and Jaikumar Radhakrishnan  “Quantum search for multiple items using parallel queries”, 2004  arXiv:quant-ph/0407217 [quant-ph]
  * [57] Lov K. Grover and Terry Rudolph  “Creating superpositions that correspond to efficiently integrable probability distributions”, 2002  arXiv:quant-ph/0208112 [quant-ph]
  * [58] Shouzhen Gu, Rolando D. Somma and Burak Şahinoğlu  “Fast-forwarding quantum evolution”, 2021  arXiv:2105.07304 [quant-ph]
  * [59] Jeongwan Haah, Matthew B. Hastings, Robin Kothari and Guang Hao Low  “Quantum algorithm for simulating real time evolution of lattice Hamiltonians”  In _Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science_ , FOCS ’18, 2018, pp. 350–360
  * [60] Aram W. Harrow, Avinatan Hassidim and Seth Lloyd  “Quantum algorithm for linear systems of equations”  In _Physical Review Letters_ 103.15, 2009, pp. 150502
  * [61] Peter Høyer and Robert Špalek  “Quantum fan-out is powerful”  In _Theory of Computing_ 1.5, 2005, pp. 81–103
  * [62] Stacey Jeffery, Frédéric Magniez and Ronald de Wolf  “Optimal parallel quantum query algorithms”  In _Algorithmica_ 79.2, 2017, pp. 509–529
  * [63] Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu and Jialin Zhang  “Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis”  In _Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’20, 2020, pp. 213–229
  * [64] Richard Jozsa  “An introduction to measurement based quantum computation”, 2005  arXiv:quant-ph/0508124 [quant-ph]
  * [65] Iordanis Kerenidis and Anupam Prakash  “Quantum recommendation systems”  In _8th Innovations in Theoretical Computer Science Conference (ITCS 2017)_ 67, 2017, pp. 49:1–49:21
  * [66] Alexei Y. Kitaev  “A simple model of quantum holography” Talks at KITP, April 7, 2015 and May 27, 2015  URL: http://online.kitp.ucsb.edu/online/entangled15/kitaev/
  * [67] Ian D. Kivlichan et al.  “Quantum simulation of electronic structure with linear depth and connectivity”  In _Physical Review Letters_ 120, 2018, pp. 110501
  * [68] Robin Kothari  “Efficient algorithms in quantum query complexity”, 2014
  * [69] Lucas Lamata, Adrian Parra-Rodriguez, Mikel Sanz and Enrique Solano  “Digital-analog quantum simulations with superconducting circuits”  In _Advances in Physics: X_ 3.1, 2018, pp. 1457981
  * [70] François Le Gall  “Average-case quantum advantage with shallow circuits”  In _Proceedings of the 34th Computational Complexity Conference_ , CCC ’19, 2019, pp. 1–20
  * [71] Seth Lloyd  “Universal quantum simulators”  In _Science_ 273.5278, 1996, pp. 1073–1078
  * [72] Guang Hao Low  “Hamiltonian simulation with nearly optimal dependence on spectral norm”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , STOC ’19, 2019, pp. 491–502
  * [73] Guang Hao Low and Isaac L. Chuang  “Hamiltonian simulation by qubitization”  In _Quantum_ 3, 2019, pp. 163
  * [74] Guang Hao Low and Isaac L. Chuang  “Optimal Hamiltonian simulation by quantum signal processing”  In _Physical Review Letters_ 118, 2017, pp. 010501
  * [75] Guang Hao Low, Vadym Kliuchnikov and Nathan Wiebe  “Well-conditioned multiproduct Hamiltonian simulation”, 2019  arXiv:1907.11679 [quant-ph]
  * [76] Guang Hao Low and Nathan Wiebe  “Hamiltonian simulation in the interaction picture”, 2019  arXiv:1805.00675 [quant-ph]
  * [77] Guang Hao Low, Theodore J. Yoder and Isaac L. Chuang  “Methodology of resonant equiangular composite quantum gates”  In _Physical Review X_ 6, 2016, pp. 041067
  * [78] David J. Luitz, Nicolas Laflorencie and Fabien Alet  “Many-body localization edge in the random-field Heisenberg chain”  In _Physical Review B_ 91, 2015, pp. 081103
  * [79] Frédéric Magniez, Ashwin Nayak, Jérémie Roland and Miklos Santha  “Search via quantum walk”  In _SIAM Journal on Computing_ 40.1, 2011, pp. 142–164
  * [80] Juan Maldacena and Douglas Stanford  “Remarks on the Sachdev-Ye-Kitaev model”  In _Physical Review D_ 94, 2016, pp. 106002
  * [81] Cristopher Moore and Martin Nilsson  “Parallel quantum computation and quantum codes”  In _SIAM Journal on Computing_ 31.3, 2002, pp. 799–815
  * [82] Rahul Nandkishore and David A. Huse  “Many-body localization and thermalization in quantum statistical mechanics”  In _Annual Review of Condensed Matter Physics_ 6.1, 2015, pp. 15–38
  * [83] Michael A. Nielsen and Isaac L. Chuang  “Quantum Computation and Quantum Information: 10th Anniversary Edition”  Cambridge University Press, 2010
  * [84] Alberto Peruzzo et al.  “A variational eigenvalue solver on a photonic quantum processor”  In _Nature Communications_ 5.1, 2014
  * [85] Paul Pham and Krysta M. Svore  “A 2D nearest-neighbor quantum architecture for factoring in polylogarithmic depth”  In _Quantum Information & Computation_ 13.11–12, 2013, pp. 937–962
  * [86] Joseph Polchinski and Vladimir Rosenhaus  “The spectrum in the Sachdev-Ye-Kitaev model”  In _Journal of High Energy Physics_ 2016.4, 2016, pp. 1–25
  * [87] John H. Reif  “Logarithmic depth circuits for algebraic functions”  In _SIAM Journal on Computing_ 15.1, 1986, pp. 231–242
  * [88] Vladimir Rosenhaus  “An introduction to the SYK model”  In _Journal of Physics A: Mathematical and Theoretical_ 52.32, 2019, pp. 323001
  * [89] Martin Rötteler and Rainer Steinwandt  “A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth $O(\log^{2}n)$”  In _Quantum Information & Computation_ 14.9–10, 2014, pp. 888–900
  * [90] Subir Sachdev and Jinwu Ye  “Gapless spin-fluid ground state in a random quantum Heisenberg magnet”  In _Physical Review Letters_ 70, 1993, pp. 3339–3342
  * [91] Peter W. Shor  “Algorithms for quantum computation: discrete logarithms and factoring”  In _Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science_ , FOCS ’94, 1994, pp. 124–134
  * [92] Rolando D. Somma, Gerardo Ortiz, James E. Gubernatis, Emanuel Knill and Raymond Laflamme  “Simulating physical phenomena by quantum networks”  In _Physical Review A_ 65, 2002, pp. 042323
  * [93] Mario Szegedy  “Quantum speed-up of Markov chain based algorithms”  In _Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science_ , FOCS ’04, 2004, pp. 32–41
  * [94] Yasuhiro Takahashi and Seiichiro Tani  “Collapse of the hierarchy of constant-depth exact quantum circuits”  In _Proceedings of the 28th IEEE Conference on Computational Complexity_ , 2013, pp. 168–178
  * [95] Barbara M. Terhal and David P. DiVincenzo  “Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games”  In _Quantum Information & Computation_ 4.2, 2004, pp. 134–145
  * [96] Adam Bene Watts, Robin Kothari, Luke Schaeffer and Avishay Tal  “Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , STOC ’19, 2019, pp. 515–526
  * [97] Nathan Wiebe, Dominic W. Berry, Peter Høyer and Barry C. Sanders  “Higher order decompositions of ordered operator exponentials”  In _Journal of Physics A: Mathematical and Theoretical_ 43.6, 2010, pp. 065203
  * [98] Shenglong Xu, Leonard Susskind, Yuan Su and Brian Swingle  “A sparse model of quantum holography”, 2020  arXiv:2008.02303 [cond-mat.str-el]
  * [99] Mingsheng Ying and Yuan Feng  “An algebraic language for distributed quantum computing”  In _IEEE Transactions on Computers_ 58, 2009, pp. 728–743
  * [100] Mingsheng Ying, Li Zhou and Yangjia Li  “Reasoning about parallel quantum programs”, 2019  arXiv:1810.11334 [cs.LO]
  * [101] Man-Hong Yung, James D. Whitfield, Sergio Boixo, David G. Tempel and Alán Aspuru-Guzik  “Introduction to quantum algorithms for physics and chemistry”  In _Advances in Chemical Physics_ John Wiley & Sons, Inc., 2014, pp. 67–106
  * [102] Christof Zalka  “Grover’s quantum searching algorithm is optimal”  In _Physical Review A_ 60, 1999, pp. 2746–2751

##  Appendix A Details Omitted in Section 3.3

In this appendix we provide details of Section 3.3.

###### Proof of Lemma 3.25.

Similar to the proof of Lemma 3.8, we can write
$\ket{\Psi_{j_{0}}^{(r,m)}}=\ket{\Phi_{j_{0}}^{(r,m)}}+\ket{\Phi_{j_{0}}^{(r,m)\bot}}$,
where the subnormalized state

$\ket{\Phi_{j_{0}}^{(r,m)}}:=\frac{1}{\sqrt{(md)^{r}}}\sum_{\boldsymbol{w}\in[m]^{r}}\sum_{\boldsymbol{j}\in\mathsf{H}^{\boldsymbol{w}}}\ket{\boldsymbol{w}}\ket{\boldsymbol{j}}\otimes\sqrt{\tilde{H}_{j_{0}j_{1}}^{*}\ldots\tilde{H}_{j_{r-1}j_{r}}^{*}}\ket{\boldsymbol{j}}$

These subnormalized states also satisfy some orthogonal relations analogous to
Lemma 3.7: for all $j,k\in[N]$,

  1. 1.

$\bra{\Phi_{j}^{(r,m)}}S^{(r,m)}\ket{\Phi_{k}^{(r,m)}}=\left\lparen\left\lparen\frac{H}{md}\right\rparen^{r}\right\rparen_{jk}$.

  2. 2.

$\bra{\Phi_{j}^{(r,m)}}S^{(r,m)}\ket{\Phi_{k}^{(r,m)\bot}}=\bra{\Phi_{j}^{(r,m)\bot}}S^{(r,m)}\ket{\Phi_{k}^{(r,m)\bot}}=0$.

We omit the proof details here, but mention that this can done by the same
techniques as in the proof of Lemma 3.7, combined with the fact that
$\sum_{w\in[m]}\tilde{H}_{j_{s}j_{s+1}}=H_{j_{s}j_{s+1}}$. Using the
orthogonal relations the conclusion is easy to obtain as in the proof of Lemma
3.8. ∎

###### Proof of Lemma 3.27.

The proof is similar to the proof of Lemma 3.14. We verify the conditions in
Definition 3.26. Observe that $L(w,j,t)=j\oplus x(w)$ where $\oplus$ is the
bit-wise XOR operator.

  * •

We have

$L^{(r)}\left\lparen\boldsymbol{w},j,\boldsymbol{t}\right\rparen=j\oplus
s(w_{0})\oplus\ldots\oplus s(w_{r-1});$

that is, take $f(j,k)=j\oplus k$, $g(w,t)=s(w)$ and $\circ$ to be $\oplus$ in
(18).

    * –

These functions and operators are arithmetic-depth-efficiently computable,
where computing $g(w,t)$ requires $O\left\lparen 1\right\rparen$ queries to
$\mathcal{O}_{P}$.

    * –

The XOR $\oplus$ is associative.

  * •

Take the inverse function to be $L^{-1}\left\lparen
w,j,k\right\rparen=s\left\lparen w\right\rparen$, which can be computed by a
single query to $\mathcal{O}_{P}$.

  * •

Observe that $(j,k)\in\mathsf{H}_{w}$ if and only if $j\oplus k=x(w)$; that
is, $[\\![\left\lparen j,k\right\rparen\in\mathsf{H}_{w}]\\!]=[\\![j\oplus
k=x(w)]\\!]$, which is obviously arithmetic-depth-efficiently computable with
$O\left\lparen 1\right\rparen$ queries to $\mathcal{O}_{P}$.

∎

###### Proof of Lemma 3.28.

In this proof we use superscript $i$ to denote the $i^{\text{th}}$ bit of a
number. We verify the conditions in Definition 3.26. Observe that
$L(w,j,t)=j\vartriangleleft_{s(w)}\left\lparen
t\mathord{\upharpoonright}_{s(w)}\right\rparen$, with $\vartriangleleft_{s}$
and $\mathord{\upharpoonright}_{s}$ defined in the proof of Lemma 3.15.

  * •

We have

$L^{(r)}\left\lparen\boldsymbol{w},j,\boldsymbol{t}\right\rparen=j\vartriangleleft\left\lparen
t_{0}\mathord{\upharpoonright}_{s(w_{0})},s(w_{0})\right\rparen\vartriangleleft^{\vee}\ldots\vartriangleleft^{\vee}\left\lparen
t_{r-1}\mathord{\upharpoonright}_{s(w_{r-1})},s(w_{r-1})\right\rparen;$

that is, take $f\left\lparen j,(k,x)\right\rparen=j\vartriangleleft(k,x)$,
$g\left\lparen w,t\right\rparen=\left\lparen
t\mathord{\upharpoonright}_{s(w)},s(w)\right\rparen$, and $\circ$ to be
$\vartriangleleft^{\vee}$, where
$\vartriangleleft:[N]\times[N]^{2}\rightarrow[N]$ and
$\vartriangleleft^{\vee}:[N]^{2}\times[N]^{2}\rightarrow[N]^{2}$ are defined
as

$a\vartriangleleft(b,x):=a\vartriangleleft_{x}b,\qquad(a,x)\vartriangleleft^{\vee}(b,y):=(a\vartriangleleft_{y}b,x\vee
y)$

for all $a,b,x,y\in[N],i\in[n]$, with $\vee$ the bit-wise OR operator.

    * –

As shown in the proof of Lemma 3.15, the operator $\vartriangleleft_{s}$ is
arithmetic-depth-efficiently computable with $O\left\lparen 1\right\rparen$
queries to $\mathcal{O}_{P}$, also $\vee$ is obviously arithmetic-depth-
efficiently computable, thus $\vartriangleleft$, $\vartriangleleft^{\vee}$ and
$f$ are arithmetic-depth-efficiently computable with $O\left\lparen
1\right\rparen$ queries.

The mapping
$\ket{w}\ket{0}\mapsto\ket{w}\frac{1}{\sqrt{d}}\sum_{t\in[d]}\ket{g(w,t)}$ can
be performed by first querying $\mathcal{O}_{P}$ to obtain $\ket{s\left\lparen
w\right\rparen}$ in an ancilla space, then conditioned on which performing $n$
controlled Hadamard gates in parallel, assuming $d$ is a power of two w.l.o.g.
This is arithmetic-depth-efficient with $O\left\lparen 1\right\rparen$
queries.

    * –

To see that $\vartriangleleft^{\vee}$ is associative, note that
$a\vartriangleleft_{x}b\vartriangleleft_{y}c=a\vartriangleleft_{x}\left\lparen
b\vartriangleleft_{y}c\right\rparen$ for all $a,b,c,x,y\in[N]$. Together with
the obvious associativity of $\vee$ we have the associativity of
$\vartriangleleft^{\vee}$.

  * •

Take the inverse function to be $L^{-1}\left\lparen
w,j,k\right\rparen=\left\lparen k\wedge s(w),s(w)\right\rparen$ with $\wedge$
the bit-wise AND operator. This is arithmetic-depth-efficiently computable
with $O\left\lparen 1\right\rparen$ queries to $\mathcal{O}_{P}$.

  * •

Observe that $(j,k)\in\mathsf{H}_{w}$ if and only if $j^{i}=k^{i}$ for all $i$
with $s(w)^{i}=0$; that is,

$[\\![\left\lparen
j,k\right\rparen\in\mathsf{H}_{w}]\\!]=\bigwedge_{i\in[n]}\left\lparen
j^{i}k^{i}+(1-j^{i})(1-k^{i})\right\rparen\cdot\left\lparen
1-s(w)^{i}\right\rparen$

which is arithmetic-depth-efficiently computable by an $O\left\lparen\log
n\right\rparen$-depth and $O(n)$-size quantum circuit by taking $\circ$ to be
AND gate in Lemma 2.3, with additional $O(1)$ queries to $\mathcal{O}_{P}$ to
compute $s(w)$.

∎

###  A.1 Proof of Theorem 3.30

Recall that the Hamiltonians considered in Section 3.3 has the form
$H=\sum_{w\in[m]}H_{w}$. To prove Theorem 3.30, following the same line of
analysis as in Section 3.2, we will show that:

  1. 1.

for $m$-uniform-structured Hamiltonians, the pre-walk, i.e., preparing the
pre-walk state $\ket{p_{j_{0}}^{(r,m)}}$ in (17), can be implemented by a
parallel quantum circuit;

  2. 2.

the re-weight can be efficiently implemented in parallel;

  3. 3.

the (extended) parallel quantum walk for uniform-structured Hamiltonians can
be efficiently implemented in parallel.

Firstly we have the following lemma as a generalization of Corollary 3.19.

######  Lemma A.1.

For an $m$-uniform-structured Hamiltonian $H$, the mapping

$\ket{\boldsymbol{w},j_{0},g\left\lparen\boldsymbol{w},\boldsymbol{t}\right\rparen}\mapsto\ket{\boldsymbol{w}}\ket{\boldsymbol{j}}$

for all $j_{0}\in[N],\boldsymbol{w}\in[m]^{r},\boldsymbol{t}\in[d]^{r}$, where
$g\left\lparen\boldsymbol{w},\boldsymbol{t}\right\rparen:=\left\lparen
g\left\lparen w_{0},t_{0}\right\rparen,\ldots,g\left\lparen
w_{r-1},t_{r-1}\right\rparen\right\rparen$ and
$\boldsymbol{j}\in\mathsf{H}^{r}$ satisfies $j_{s+1}=L\left\lparen
w_{s},j_{s},t_{s}\right\rparen$ for $s\in[r]$, can be implemented by a quantum
circuit with

  * •

$O\left\lparen 1\right\rparen$-depth and $O\left\lparen r\right\rparen$-size
of queries to $\mathcal{O}_{P}$, and

  * •

$O\left\lparen\log r\cdot\log^{2}n\right\rparen$-depth and $O\left\lparen
r^{2}n^{4}\right\rparen$-size of gates.

###### Proof.

The lemma can be proved along the same line as Lemma 3.17, Corollary 3.18 and
Corollary 3.19. Recall that $m=\operatorname{poly}n$. We omit the proof
details here, but mention that only the first two conditions of Definition
3.26 are needed. ∎

Then the following lemma shows that an $(r,m)$-pre-walk can be implemented by
a parallel quantum circuit, as a generalization of Lemma 3.20.

######  Lemma A.2 (Pre-walk on $m$-uniform-structured Hamiltonians).

An $(r,m)$-pre-walk on an $m$-uniform-structured Hamiltonian $H$, i.e.,
preparing the state $\ket{p_{j_{0}}^{(r,m)}}$, can be implemented by a quantum
circuit with

  * •

$O\left\lparen 1\right\rparen$-depth and $O\left\lparen r\right\rparen$-size
of queries to $\mathcal{O}_{P}$, and

  * •

$O\left\lparen\log r\cdot\log^{2}n\right\rparen$-depth and $O\left\lparen
r^{2}n^{4}\right\rparen$-size of gates.

###### Proof.

Let
$\mathcal{H}^{W}\otimes\mathcal{H}^{J}=\left\lparen\bigotimes_{s\in[r]}\mathcal{H}_{s}^{W}\right\rparen\otimes\left\lparen\bigotimes_{s\in[r+1]}\mathcal{H}_{s}^{J}\right\rparen$
be the state space with $\mathcal{H}_{s}^{W}=\mathbbm{C}^{m}$ and
$\mathcal{H}_{s}^{J}=\mathbbm{C}^{N}$. The process of preparing
$\ket{p_{j_{0}}^{(r,m)}}$ is presented below, starting from the initial state
$\ket{0}^{\otimes mr}\ket{j_{0}}\ket{0}^{\otimes Nr}$ with
$\ket{j_{0}}\in\mathbbm{C}^{N},\ket{0}\in\mathbbm{C}$.

  1. 1.

Prepare a superposition over computational basis states of size $m^{r}$ in the
subspace $\mathcal{H}^{W}$:

$\frac{1}{\sqrt{m^{r}}}\sum_{\boldsymbol{w}\in[m]^{r}}\ket{\boldsymbol{w}}\ket{j_{0}}\ket{0}^{\otimes
Nr}.$

  2. 2.

For each $s\in[r]$, perform in parallel the mapping
$\ket{w_{s}}\ket{0}\mapsto\ket{w_{s}}\frac{1}{\sqrt{d}}\sum_{t_{s}\in[d]}\ket{g\left\lparen
w_{s},t_{s}\right\rparen}$ in the subspace
$\mathcal{H}_{s}^{W}\otimes\mathcal{H}_{s+1}^{J}$, to obtain the state

$\frac{1}{\sqrt{(md)^{r}}}\sum_{\boldsymbol{w}\in[m]^{r}}\sum_{\boldsymbol{t}\in[d]^{r}}\ket{\boldsymbol{w}}\ket{j_{0}}\ket{g\left\lparen\boldsymbol{w},\boldsymbol{t}\right\rparen}$

  3. 3.

Apply Lemma A.1 to obtain the goal state
$\ket{p_{j_{0}}^{(r,m)}}=\frac{1}{\sqrt{\left\lparen
md\right\rparen^{r}}}\sum_{\boldsymbol{w}\in[m]^{r}}\sum_{\boldsymbol{j}\in\mathsf{H}^{\boldsymbol{w}}}\ket{\boldsymbol{w}}\ket{\boldsymbol{j}}$.

Step 1 can be done by applying Hadamard gates of $O(1)$-depth and
$O\left\lparen r\log m\right\rparen$-size in parallel, assuming $m$ is a power
of two w.l.o.g. Each mapping
$\ket{w}\ket{0}\mapsto\ket{w}\frac{1}{\sqrt{d^{r}}}\sum_{t\in[d]}\ket{g(w,t)}$
in Step 2 is arithmetic-depth-efficient with $O\left\lparen
1\right\rparen$-queries to $\mathcal{O}_{P}$ due to Definition 3.26. Recall
that $m=\operatorname{poly}n$, the final complexity follows from summing up
these complexities combined with Lemma A.1. ∎

Now we move to the re-weight analysis.

######  Lemma A.3.

Re-weight of $\ket{p_{j_{0}}^{(r,m)}}$, i.e., performing the mapping
$\ket{p_{j_{0}}^{(r,m)}}\mapsto\ket{\Psi_{j_{0}}^{(r,m)}}$, where
$\ket{\Psi_{j_{0}}^{(r,m)}}$ is defined in (16), can be implemented to
precision $\epsilon$ by a quantum circuit with

  * •

$O(1)$-depth and $O(r)$-size of queries to $\mathcal{O}_{H}^{b}$ with
$b=O\left\lparen\log\left\lparen m/\epsilon\right\rparen\right\rparen$,

  * •

$O\left\lparen 1\right\rparen$-depth and $O\left\lparen rm\right\rparen$-size
of queries to $\mathcal{O}_{P}$, and

  * •

$O\left\lparen\log^{2}n+\log^{2}\log\left\lparen
m/\epsilon\right\rparen\right\rparen$-depth and $O\left\lparen
r\left[mn^{4}+\log^{4}\left\lparen
m/\epsilon\right\rparen\right]\right\rparen$-size of gates.

for $r=\operatorname{polylog}\left\lparen 1/\epsilon\right\rparen$.

###### Proof.

The analysis is exactly the same as in Lemma 3.21, with additional
complexities of:

  1. 1.

Computing $c(j,k)=\sum_{w\in[m]}[\\![\left\lparen
j,k\right\rparen\in\mathsf{H}_{w}]\\!]$ in $r$ subspaces, each of which can be
implemented by a quantum circuit with

     * •

$O\left\lparen 1\right\rparen$-depth and $O\left\lparen m\right\rparen$-size
of queries to $\mathcal{O}_{P}$, and

     * •

$O\left\lparen\log^{2}n\right\rparen$-depth and $O\left\lparen
mn^{4}\right\rparen$-size of gates.

To see this, note that for each subspace, one can first creates $m$ copies of
$(j,k)$ by $\mathrm{COPY}^{2n}_{m}$, then compute each $[\\![\left\lparen
j,k\right\rparen\in\mathsf{H}_{w}]\\!]$ arithmetic-depth-efficiently with
$O\left\lparen 1\right\rparen$ queries to $\mathcal{O}_{P}$ for $w\in[m]$ in
parallel, due to the third condition in Definition 3.26. Finally apply
Corollary 2.4 to compute $c(j,k)$ in each subspace, followed by garbage
cleaning by reverse computation. The final complexity follows from the
assumption $m=\operatorname{poly}n$.

  2. 2.

Scaled total precision $\tilde{\epsilon}=\epsilon/m$ for the aforementioned
construction of the oracle $\mathcal{O}_{\tilde{H}}$.

  3. 3.

Arithmetic-depth-efficient circuits for the division
$\tilde{H}_{jk}=H_{jk}/c(j,k)$ by Lemma 2.6.

∎

Finally, combining Lemma A.2, Lemma A.3 and the negligible complexity of
implementing $S^{(r,m)}$ gives the complexity of the $(r,m)$-parallel quantum
walk $Q^{(r,m)}$ for $m$-uniform-structured Hamiltonians in Theorem 3.30.

##  Appendix B Definition of State Preparation

In this appendix we show that the state preparation unitary in Definition 4.2
is a special case of Definition 51 in [50]:

######  Definition B.1 (State preparation pair [50]).

Let $\boldsymbol{a}\in\mathbbm{C}^{R}$ and
$\lVert\boldsymbol{a}\rVert_{1}\leq\alpha$, the pair of unitaries
$(V_{C},V_{D})$ is called an $(\alpha,b,\epsilon)$-state-preparation-pair of
$\boldsymbol{a}$ if $V_{C}\ket{0}=\sum_{r\in[2^{b}]}c_{r}\ket{r}$ and
$V_{D}\ket{0}=\sum_{r\in[2^{b}]}d_{r}\ket{r}$ with
$\ket{0}\in\mathbbm{C}^{2^{b}}$, such that
$\sum_{r\in[R]}\left\lvert\alpha\left\lparen c_{r}^{*}d_{r}\right\rparen-
a_{r}\right\rvert\leq\epsilon$ and for all $r\in R,\ldots,2^{b}-1$ we have
$c_{r}^{*}d_{r}=0$.

This is shown more precisely in the following lemma.

######  Lemma B.2.

Let $\boldsymbol{a}\in\mathbbm{C}^{R}$ and
$\alpha:=\lVert\boldsymbol{a}\rVert_{1}$, where we assume $R=2^{s}\geq 4$
w.l.o.g. Let $V$ be an $(\alpha,\epsilon)$-state-preparation-unitary of
$\boldsymbol{a}$, then $(V^{\dagger},V)$ is an $(\alpha,s,\alpha
R\epsilon)$-state-preparation-pair of $\boldsymbol{a}$.

###### Proof.

Let $V\ket{0}=\sum_{r\in[R]}\sqrt{v_{r}}\ket{r}$. By Definition 4.2, we have

$\sqrt{\sum_{r\in[R]}\left\lvert\sqrt{v_{r}}-\sqrt{\frac{a_{r}}{\alpha}}\right\rvert^{2}}\leq\epsilon.$
(30)

Note that

$\sum_{r\in[R]}\left\lvert
v_{r}-\frac{a_{r}}{\alpha}\right\rvert\leq\sum_{r\in[R]}\left\lvert\sqrt{v_{r}}-\sqrt{\frac{a_{r}}{\alpha}}\right\rvert\cdot\left\lvert\sqrt{v_{r}}+\sqrt{\frac{a_{r}}{\alpha}}\right\rvert\leq
2\sum_{r\in[R]}\left\lvert\sqrt{v_{r}}-\sqrt{\frac{a_{r}}{\alpha}}\right\rvert.$
(31)

By the well-known inequality between $l_{1}$-norm and $l_{2}$-norm:
$\lVert{\boldsymbol{x}}\rVert_{1}\leq\sqrt{R}\cdot\lVert{\boldsymbol{x}}\rVert_{2}$
for ${\boldsymbol{x}}\in\mathbbm{C}^{R}$, the RHS of (31) is upper bounded by

$2\sqrt{R}\cdot\sqrt{\sum_{r\in[R]}\left\lvert\sqrt{v_{r}}-\sqrt{\frac{a_{r}}{\alpha}}\right\rvert^{2}}\leq
2\sqrt{R}\epsilon\leq R\epsilon,$

where the first inequality comes from (30), and the second inequality uses the
assumption $R\geq 4$. Thus we have $\sum_{r\in[R]}\left\lvert
v_{r}-\frac{a_{r}}{\alpha}\right\rvert\leq R\epsilon$. Now take $b=s$,
$V_{C}=V^{\dagger}$ and $V_{D}=V$ in Definition B.1, it immediately follows
that $\sum_{r\in[R]}\left\lvert\alpha\left\lparen c_{r}^{*}d_{r}\right\rparen-
a_{r}\right\rvert=\alpha\sum_{r\in[R]}\left\lvert
v_{r}-\frac{a_{r}}{\alpha}\right\rvert\leq\alpha R\epsilon$, which implies
that $\left\lparen V^{\dagger},V\right\rparen$ is an $\lparen\alpha,s,\alpha
R\epsilon\rparen$-state-preparation-pair of $\boldsymbol{a}$. ∎

We note that in the above lemma, the upper bound $\alpha R\epsilon$ on the
precision of the state preparation pair is very loose, which is for simplicity
of the proofs in Section 4 with the final results unchanged.


# Think you have Solved Direct-Answer Question Answering?
Try ARC-DA, the Direct-Answer AI2 Reasoning Challenge

Sumithra Bhakthavatsalam, Daniel Khashabi, Tushar Khot, Bhavana Dalvi Mishra,
Kyle Richardson, Ashish Sabharwal, Carissa Schoenick, Oyvind Tafjord, Peter
Clark

Allen Institute for Artificial Intelligence, Seattle, WA, U.S.A.
<EMAIL_ADDRESS>
###### Abstract

We present the ARC-DA dataset, a direct-answer (“open response”, “freeform”)
version of the ARC (AI2 Reasoning Challenge) multiple-choice dataset. While
ARC has been influential in the community, its multiple-choice format is
unrepresentative of real-world questions, and multiple choice formats can be
particularly susceptible to artifacts. The ARC-DA dataset addresses these
concerns by converting questions to direct-answer format using a combination
of crowdsourcing and expert review. The resulting dataset contains 2985
questions with a total of 8436 valid answers (questions typically have more
than one valid answer). ARC-DA is one of the first DA datasets of natural
questions that often require reasoning, and where appropriate question
decompositions are not evident from the questions themselves. We describe the
conversion approach taken, appropriate evaluation metrics, and several strong
models. Although high, the best scores (81% GENIE, 61.4% F1, 63.2% ROUGE-L)
still leave considerable room for improvement. In addition, the dataset
provides a natural setting for new research on explanation, as many questions
require reasoning to construct answers. We hope the dataset spurs further
advances in complex question-answering by the community.111 ARC-DA is
available at https://allenai.org/data/arc-da

MC: Many animals depend on plants for (A) shelter [correct] (B) pollination
(C) seed dispersal (D) sunlight DA: Many animals depend on plants for what?
food $|$ shelter MC: A solution with a pH of 2 can be increased to a pH above
7 by adding (A) an acid. (B) water. (C) a base. [correct] (D) hydrogen. DA: A
solution with a pH of 2 can be increased to a pH above 7 by adding what? a
base What best describes skin? (A) stiff (B) flexible [correct] (C) brittle
(D) hard DA: [Rejected: Too ambiguous as a DA question] MC: Water freezing is
an example of a (A) liquid changing to a solid [correct] (B) solid changing to
a liquid (C) gas changing to a solid (D) gas changing to a liquid DA: Water
freezing is an example of what? liquid changing to a solid $|$ phase
transition $|$ change of state of matter $|$ a change in state $|$ state
change MC: How are the stem of a tree and the stem of a flower most similar?
(A) Both are soft. (B) Both have thorns. (C) Both support the plant. [correct]
(D) Both have woody bark. DA: How are the stem of a tree and the stem of a
flower most similar? both support the plant $|$ support leaves $|$ both carry
water $|$ both carry nutrients $|$ they support the plant

Figure 1: Multiple-choice (MC) questions from ARC, and their direct answer
(DA) equivalents in the new ARC-DA dataset. Alternative DA answers are
separated by a $|$.

## Introduction

Multiple-choice (MC) datasets are popular and common in the NLP community,
e.g., CommonsenseQA Talmor et al. (2019), OpenbookQA Mihaylov et al. (2018),
and VCR Zellers et al. (2019), in particular because of the ease of automatic
evaluation. However, they have two notable drawbacks: First, they are
unnatural (real-world questions rarely come with answer options). Second, the
multiple-choice format is particularly susceptible to artifacts, where systems
learn short-cuts to obtain a high score Gururangan et al. (2018).

Similarly, while there are many NLP datasets of direct-answer questions (also
called “open response” or “freeform” questions), e.g., SQuaD Rajpurkar et al.
(2016), TriviaQA Joshi et al. (2017), and NaturalQuestions Kwiatkowski et al.
(2019), the majority of these are span-retrieval (“lookup”) tasks where a
question is matched against a given/retrieved sentence or paragraph to
identify an answer span. The few DA datasets that do target reasoning, e.g.,
HotpotQA Yang et al. (2018), DROP Dua et al. (2019), and ROPES Lin et al.
(2019), are crowdsourced, and thus tend to explore a single, specific style of
reasoning in a controlled setting.

What is missing, still, are direct-answer (DA) datasets of natural questions
exploring a wide variety of problem types and reasoning styles, and where
answers are not constrained to be spans of a source text. This work alleviates
this gap by supplying such a dataset, namely ARC-DA, a direct-answer version
of the ARC (AI2 Reasoning Challenge) multiple-choice dataset Clark et al.
(2018). Note that ARC-DA questions are not necessarily more difficult than the
original ARC questions (we find scores on ARC-DA are roughly similar to those
on ARC), rather they are more natural, avoiding the multiple-choice format.

The original ARC dataset contained questions collected from a large number of
science exam and quiz sources. It has proven useful for the community,
stimulating new research in reasoning-based QA, e.g., Musa et al. (2019);
Boratko et al. (2018); Ni et al. (2019); Xie et al. (2020), and as of January
2021 has 35 entries on its
leaderboard222https://leaderboard.allenai.org/arc/submissions/public. ARC is
particularly interesting from an NLP perspective: the questions were authored
by human experts (e.g., examination boards), they are sensible and high
quality, they avoid the repetition common to crowdsourced datasets, they are
highly varied in both the language they use and the reasoning skills they are
designed to probe, and they are practical, understandable, and motivating.
Arguably, the combination of these factors makes the dataset a useful “Grand
Challenge” for the field Clark and Etzioni (2016) (The current top score on
ARC-Challenge is 81.1%, thus still with room for improvement). The work here,
ARC-DA, thus builds on this, providing a direct-answer version of part of the
ARC dataset. Several examples of original ARC questions and the ARC-DA
versions are shown in Figure 1.

We first describe the method used for the conversion, and then present
baseline scores using strong T5-based models. Evaluating DA questions poses an
additional challenge, compared with scoring MC questions. To address this
challenge, we use both human judgements (obtained with GENIE, an automated
crowdscoring pipeline Khashabi et al. (2021)), and automated metrics. Although
high, the best scores (81% GENIE, 61.4% F1, 63.2% ROUGE-L) still leave
considerable room for improvement. In addition, the dataset provides a natural
setting for new research on explanation, as many questions require reasoning
to construct answers. We encourage the community to make use of this dataset
to make further progress in advanced question-answering.

## ARC-DA Dataset

Naïvely, one can convert MC to DA simply by removing the answer choices, and
using the correct answer choice as the target answer.333Indeed, this is the
approach taken by Lin et al. (2020) to use (a filtered subset of) ARC in a
direct-answer setting. However, there are several problems that can arise:

  * •

There may be multiple ways of wording the correct answer.

  * •

There may be multiple possible correct answers, and in some cases too many to
enumerate all of them.

  * •

The question itself may be ill-defined without answer options.

To address these problems, we convert the 7787 ARC MC questions to DA using
the process described below.

### Crowdworker Annotation

We start with a large scale crowdsourcing process to filter questions to those
suitable for the DA setting and collect alternative correct answers for them:

  1. 1.

Initial Question Filtering: Remove questions where the question sentence444
Many questions are multi-sentence, with a preamble before the actual question
sentence. contains one of several empirically-chosen filter phrases, e.g.,
“Which of”.555 The filter phrases are: which of, most, best, least, est,
order, supports, characteristic, trait, which object, which statement, below,
which is, which are, example, which term, conclusion, which would, which item,
which action, which two, which sentence, which one, sequence, which fact,
which $<$VERB$>$. Questions containing these phrases were observed to usually
be ill-formed without the answer options, e.g., “Which of these items contains
only a liquid?”.

  2. 2.

Collecting Answers: Each question was then posed to five independent
crowdworkers as a DA question, and the workers were asked to:

     * •

Answer the question (enter a free-form answer). If there were multiple
answers, they were asked to enter two or three.

     * •

Identify if the question had one, several, or many answers, or if the question
was nonsensical.

If the question was too ambiguous or nonsensical, the crowdworker had the
option of not providing an answer. The crowdworker interface is shown in
Appendix A.

  3. 3.

Additional Filtering: The questions were further filtered, only retaining:

     * •

questions that had answers from at least two workers.

     * •

questions where at least two worker-provided answers had some non-stop-word
overlap.

Otherwise the question was deemed too open-ended and rejected.

### In-House Review

The resulting questions were then reviewed by in-house (“expert”) workers, who
performed the following operations:

  1. 1.

Question Filtering: Rejected questions that still appeared too open-ended
(e.g., “Name an insect.”).

  2. 2.

Answer Verification: Reviewed crowdworker answers to remove incorrect answers,
and add additional missed answers.

  3. 3.

Question Rewording: Reworded questions that were poorly phrased or incomplete
as standalone questions, e.g., “The cell structure that makes a plant cell
more rigid than an animal cell is the” becomes “The cell structure that makes
a plant cell more rigid than an animal cell is called what?”

  4. 4.

Answer Modification: For long (wordy) answers, ensure that a shorter version
including just the salient terms is also present. For example, for the
question: “In what form does water vapor exist in the atmosphere?”, the
crowdworkers gave two answers: “An invisible gas in the air”, and “An
invisible gas”. As the simple answer “gas” is sufficient for this question,
the expert would add “gas” as an additional answer option.

This process was run over the entire ARC question set. Approximately 60% of
the original questions were removed during crowdworker annotation (50% in the
initial question filtering, 10% more in the additional filtering), followed by
another 10% during in-house review, resulting in 2985 questions in the final
ARC-DA dataset. Although the final dataset is less that half the size of ARC,
it is still large enough for models to learn the style of the task (e.g., see
Table 3 later), without simply memorizing the task itself, thus avoiding
large-scale supervised training pitfalls. This trend towards more
realistically sized datasets is seen elsewhere also, e.g., OBQA Mihaylov et
al. (2018), QASC Khot et al. (2019), TRACIE Zhou et al. (2020).

| Train | Dev | Test
---|---|---|---
num. questions | 1250 | 338 | 1397
num. answers per qn (avg) | 2.75 | 2.72 | 2.92
num. words per answer (avg) | 2.11 | 1.94 | 2.27
Table 1: Statistics of ARC-DA, with 2985 total questions.

### Train/Dev/Test Split

We retain the same train/dev/test labels for questions as in the original ARC
dataset, resulting in approximately similar proportions as ARC. We also do not
separate the original ARC-Easy and ARC-Challenge questions, but instead merge
them into a single dataset. We do this because the labels “Easy” and
“Challenge” were based on the MC choices. (Switching from MC to DA can result
in a “Hard” question becoming conceptually easy, and vice versa). However, we
do retain the original Easy/Challenge labels as metadata in the ARC-DA
dataset. The resulting dataset statistics are summarized in Table 1.

### Knowledge and Reasoning Types

We found that the distribution of knowledge and reasoning types required by
ARC-DA questions, as classified by Boratko et al. (2018), to be roughly the
same as in ARC, see Figure 2 (created using Boratko et al’s data). For a
detailed description of these categories, see Boratko et al. (2018).

Knowledge Types

Reasoning Types

Figure 2: Comparison of the distribution of questions among different knowledge (top) and reasoning types (bottom), comparing ARC with ARC-DA. Overall, the distributions are roughly similar. Data is from sampled annotations created by Boratko et al. (2018). For a detailed description of the categories, see Boratko et al. (2018).  Rating | Score
---|---
strongly agree | 1.00
agree | 0.75
neutral | 0.50
disagree | 0.25
strongly disagree | 0.00
Table 2: GENIE’s crowdworker ratings of a model’s answers are mapped to real-
value scores as shown.

### Evaluation Metrics

It’s not immediately clear how one should score answers to DA questions. Doing
this is more difficult than for MC questions, as (usually) the set of gold DA
answers is incomplete. Further, even if the answer is unique conceptually
(e.g., the answer “gravity”) it may be phrased in multiple ways (“the force of
gravity” “gravitational force”, “gravitation”, …). As a result, scoring is
necessarily approximate. However, this should not be a reason to shy away from
such problems; valid comparisons can still be made, and there are obvious
benefits to working in the more realistic DA setting.

We propose two ways to score answers to ARC-DA: The first is human scoring via
GENIE666Available at https://genie.apps.allenai.org/, a human-in-the-loop
leaderboard framework that scores answers using an automated crowdsourced
pipeline Khashabi et al. (2021). GENIE streamlines the human scoring of
machine-generated answers by automatically posting them on crowdsourcing
platforms, collecting qualitative human judgements (converted to numeric
scores using the rubric in Table 2), then performing statistical analyses to
quantify uncertainty. It also includes various constraints to ensure quality
control. To use GENIE, we submit our answers to the leaderboard, then wait for
the task to complete (which follows a fixed, periodic schedule). Note that
GENIE is publicly available for other researchers interested in this dataset.

Second, we consider two popular automatic metrics to score answers by
comparing them to the (typically incomplete) set of gold answers, namely ROUGE
and an F1 word-overlap measure.

For ROUGE Lin et al. (2006), we use the F1 score for the ROUGE-L variant which
considers the longest common subsequence, thus penalizing words out of
order.777We use the implementation from https://github.com/google-
research/google-research/tree/master/rouge, with stemming turned on. For the
simple F1 word-overlap measure, we adopt the conventions from the SQuAD
dataset Rajpurkar et al. (2016) in terms of ignoring punctuation and a few
stop words. For both ROUGE and F1, we take the maximum score over all of the
gold answers for a given question (i.e., an answer is scored against its best-
matching gold answer), and then average over all the questions.

We note that both ROUGE and F1 have known intrinsic pitfalls. For example, as
F1 ignores word order, the prediction “from solid to liquid” would be
considered a perfect match for the gold answer “from liquid to solid”.

For these reasons, our preferred metric for ARC-DA is GENIE (despite the
turnaround time), which also alleviates the problem of missing gold answers.

## Empirical Evaluation

We next describe a few strong baseline systems for ARC-DA and report their
performance.

### Baseline Models

To build a strong baseline model, we start with (a reimplementation of)
UnifiedQA Khashabi et al. (2020), a QA system trained on multiple QA datasets
using the text-to-text pretrained T5 transformer Raffel et al. (2020) (we use
the 11B version). We then fine-tune two models on ARC-DA, one using sentences
retrieved from a general corpus of text $K$, and one without. The input to
these models is the question $Q$ (plus retrieved sentences, for the first
model). The desired output is a correct answer to $Q$. We call the resulting
models UnifiedQA + ARC-DA.

For the “with IR” (Information Retrieval) variant of UnifiedQA + ARC-DA, given
a question $Q$, we retrieve 10 sentences $K_{1},...,K_{10}$ from the corpus
$K$ using $Q$ as the search query (here, using ElasticSearch). For $K$, we use
the Aristo Corpus, a Web-crawled corpus containing 280GB of general and
science-related sentences augmented with $\approx$80k additional science
textbook sentences Clark et al. (2016). The input to the model is then:

> $question$ =  Q ; $context$ =  $K_{1}...K_{10}$

The desired output of the model is a correct answer to the question. To train
the model, since we (typically) have multiple, alternative gold target answers
$A_{1},...,A_{n}$ in the training data, we generate $N_{a}$ training examples
for each question, where each example uses a randomly sampled answer from
$A_{i}$. In other words, each individual gold answer (of which there are a few
per question) and unique question are used to construct an individual training
example, capped at a max of $N_{a}$ training examples per question. In our
experiments, we used $N_{a}=4$. Each training instance thus has a single gold
answer, and the fine-tuning otherwise follows the T5 procedure of using
teacher forcing Williams and Zipser (1989). Note there is a (deliberate)
asymmetry in train/test: Each training instance encourages the system to
predict a particular gold answer, while each test output is considered correct
if it predicts any of the gold answers. This style of teaching for questions
with multiple answers has been found effective in previous work, e.g.,
Bosselut et al. (2019); Rashkin et al. (2018).

For the “without IR” variant, the same process is applied except the input to
the model is simply:

> $question$ =  $Q$

Since UnifiedQA is question-format agnostic,888 That is, given an MC question,
UnifiedQA will output an answer choice label; while given a DA question,
UnifiedQA will generate an answer directly. we also create variants of the
above models (again with and without retrieval) by fine-tuning them jointly on
ARC-DA as described above as well as on the original multiple choice questions
of ARC. The resulting models are referred to as UnifiedQA + ARC-DA/MC.

| Score (Test Set)
---|---
Model: | GENIE | F1 | ROUGE-L
T5 + ARC-DA (no IR) | 66${}^{+3}_{-3}$ |  | 50.0
UnifiedQA + ARC-DA (no IR) | 72${}^{+2}_{-3}$ | 53.5 | 55.7
UnifiedQA + ARC-DA (w/ IR) | 75${}^{+2}_{-2}$ | 59.6 | 61.2
UnifiedQA + ARC-DA/MC (no IR) | 75${}^{+2}_{-2}$ | 55.4 | 57.5
UnifiedQA + ARC-DA/MC (w/ IR) | 81${}^{+2}_{-2}$ | 61.4 | 63.2
Table 3: Results on ARC-DA test set (1397 questions), both without and with IR, according to different metrics. GENIE is a human (crowdsourced) metric, F1 and ROUGE-L are automated metrics. The GENIE score includes a confidence interval (+/-), as shown. (GENIE is our preferred measure.)  | Score (Dev Set)
---|---
Model: | EXPERT | F1 | ROUGE-L
UnifiedQA + ARC-DA (no IR) | 78.8 | 53.9 | 55.4
UnifiedQA + ARC-DA (w/ IR) | 84.0 | 63.0 | 65.2
UnifiedQA + ARC-DA/MC (no IR) | 78.7 | 55.5 | 59.5
UnifiedQA + ARC-DA/MC (w/ IR) | 85.9 | 63.7 | 66.8
Table 4: Results on ARC-DA dev set (338 questions). Here we show human
evaluation by one of the authors (EXPERT), rather than GENIE scores.

### Results

The results for the models are shown in Table 3. To help interpret the GENIE
scores, note that crowdworkers label answers according to the rubric and
corresponding real values as shown in Table 2. For comparison, one of the
authors manually scored the answers on the development set, using a principle
of partial credit for non-ideal answers; this is shown under the EXPERT column
of Table 4.

There are several results of note. First, the scores are high in absolute
terms, with the human-scored GENIE/EXPERT numbers being roughly comparable to
scores on the original MC questions, found to be 86.8%/92.6% without/with
IR.999 To obtain these MC scores, we ran the same UnifiedQA model, before
fine-tuning on ARC-DA, on the original ARC multiple-choice versions of the
1397 ARC-DA test questions. This suggests that the DA questions are not
necessarily harder than the MC versions, despite the format change, although
they are more natural (non-multiple-choice). While intuitively one might
expect DA questions to be more difficult to answer as the number of potential
answers changes from 4 to a potentially infinite number, some may also be
easier as any correct answer is valid, allowing the model to sidestep subtle
distinctions that may be used in the MC choices.

Second, the GENIE scores slightly underestimate the “true” score, which we
take as the EXPERT score (Table 4), namely the score one might expect to
receive in an examination setting with a professional grader. This may be due
to occasional annotation errors and/or unreliable annotators that slip through
GENIE’s quality controls. (Also note the GENIE score in Table 3 is on the test
set, while the EXPERT score in Table 4 is on dev, which may account for some
of the difference (test performance is typically slightly worse than dev)).
While in principle the upper bound on the EXPERT score is 100%, namely for a
perfect set of answers, our preliminary tests suggest the GENIE upper bound
(for ARC-DA) may be around 90% for a perfect set of answers due to this noise,
given GENIE’s current pipeline (additional improvements to GENIE are under
consideration).

Third, the automated metrics are only a loose approximation of the true
target. In absolute terms, there is a significant gap between the automated
metrics (F1 and ROUGE-L) and the human evaluations (GENIE and EXPERT),
suggesting that there are indeed additional answers and answer phrasings
missing in ARC-DA gold answers. We also see that the rank-ordering of models
based on human vs. automated metrics is not identical (although is generally
similar). Assuming that the human-based scores are the most accurate (although
expensive), this indicates that automatic metrics should be used with caution:
While they can be used as a useful proxy, it is not appropriate to draw
conclusions from them based on small (e.g., 1%) differences.

### Impact on MC Question-Answering

As an unexpected corollary, we ran the UnifiedQA + ARC-DA/MC model on the
original ARC MC dataset,101010 As before, note that UnifiedQA is format-
agnostic, outputing an answer option label given an MC question, or a direct
answer given a DA question. and obtained new state-of-the-art results (81.4%
on ARC-Challenge and 92.7% on ARC-
Easy).111111https://leaderboard.allenai.org/arc/submissions/public Note also
that this model has the highest score on ARC-DA (GENIE score of 81%, Table 3).
This suggests that there is some additional training signal provided by the DA
training questions that is assisting in MC QA, and likewise that the
additional MC training is helping answer DA questions. This phenomenon is
reminiscent of the discovery in the original UnifiedQA paper that multi-format
training can provide an overall boost in individual scores Khashabi et al.
(2020).

## Summary

Progress in QA requires new datasets in more realistic settings, for example
using natural questions that require more than a “lookup” answer. The ARC-DA
dataset addresses this need, containing a direct answer version of (a subset
of) the ARC multiple-choice questions. These questions are expert (examination
board) authored, high quality, sensible, and avoid the repetition common to
crowdsourced datasets, making them of particular interest to NLP. We have also
shown that baseline scores, although strong, are far from perfect, offering a
new challenge to the NLP community, as well as a new setting to study
explanation in the context of questions requiring reasoning. We invite readers
to take up this challenge!

The ARC-DA dataset is available at https://allenai.org/data/arc-da, and the
GENIE human evaluation framework is publicly available at
https://genie.apps.allenai.org.

## Acknowledgements

Thanks to all in the Aristo team and the additional expert reviewers Kirsten
Barber, Rosann Morrow-Clark, Tao Li, and Anjali Tandon who contributed to this
dataset. The TPU machines for conducting experiments were provided by Google.

## References

  * Boratko et al. (2018) M. Boratko, H. Padigela, D. Mikkilineni, P. Yuvraj, R. Das, A. McCallum, M. Chang, A. Fokoue, P. Kapanipathi, N. Mattei, R. Musa, K. Talamadupula, and M. Witbrock.  A systematic classification of knowledge, reasoning, and context within the ARC dataset.  In QA@ACL, 2018.
  * Bosselut et al. (2019) A. Bosselut, H. Rashkin, M. Sap, C. Malaviya, A. Celikyilmaz, and Y. Choi.  COMET: Commonsense transformers for automatic knowledge graph construction.  In ACL, 2019.
  * Clark et al. (2018) P. Clark, I. Cowhey, O. Etzioni, T. Khot, A. Sabharwal, C. Schoenick, and O. Tafjord.  Think you have solved question answering? Try ARC, the AI2 Reasoning Challenge.  ArXiv, abs/1803.05457, 2018.
  * Clark and Etzioni (2016) P. Clark and O. Etzioni.  My computer is an honor student – but how intelligent is it? standardized tests as a measure of AI.  AI Magazine, 37:5–12, 2016.
  * Clark et al. (2016) P. Clark, O. Etzioni, T. Khot, A. Sabharwal, O. Tafjord, P. D. Turney, and D. Khashabi.  Combining retrieval, statistics, and inference to answer elementary science questions.  In AAAI, 2016.
  * Dua et al. (2019) D. Dua, Y. Wang, P. Dasigi, G. Stanovsky, S. Singh, and M. Gardner.  DROP: A reading comprehension benchmark requiring discrete reasoning over paragraphs.  In NAACL-HLT, 2019.
  * Gururangan et al. (2018) S. Gururangan, S. Swayamdipta, O. Levy, R. Schwartz, S. R. Bowman, and N. A. Smith.  Annotation artifacts in natural language inference data.  In NAACL-HLT, 2018.
  * Joshi et al. (2017) M. Joshi, E. Choi, D. S. Weld, and L. S. Zettlemoyer.  Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension.  In ACL, 2017.
  * Khashabi et al. (2020) D. Khashabi, S. Min, T. Khot, A. Sabharwal, O. Tafjord, P. Clark, and H. Hajishirzi.  Unifiedqa: Crossing format boundaries with a single QA system.  In EMNLP, 2020.
  * Khashabi et al. (2021) D. Khashabi, G. Stanovsky, J. Bragg, N. Lourie, J. Kasai, Y. Choi, N. A. Smith, and D. S. Weld.  GENIE: A leaderboard for human-in-the-loop evaluation of text generation.  preprint arXiv:2101.06561, 2021.
  * Khot et al. (2019) T. Khot, P. Clark, M. Guerquin, P. Jansen, and A. Sabharwal.  QASC: A dataset for question answering via sentence composition.  arXiv preprint arXiv:1910.11473, 2019.
  * Kwiatkowski et al. (2019) T. Kwiatkowski, J. Palomaki, O. Redfield, M. Collins, A. P. Parikh, C. Alberti, D. Epstein, I. Polosukhin, J. Devlin, K. Lee, K. Toutanova, L. Jones, M. Kelcey, M.-W. Chang, A. M. Dai, J. Uszkoreit, Q. Le, and S. Petrov.  Natural Questions: A benchmark for question answering research.  TACL, 7:453–466, 2019.
  * Lin et al. (2020) B. Y. Lin, H. Sun, B. Dhingra, M. Zaheer, X. Ren, and W. W. Cohen.  Differentiable open-ended commonsense reasoning.  ArXiv, abs/2010.14439, 2020.
  * Lin et al. (2006) C.-Y. Lin, G. Cao, J. Gao, and J.-Y. Nie.  An information-theoretic approach to automatic evaluation of summaries.  In HLT-NAACL, 2006.
  * Lin et al. (2019) K. Lin, O. Tafjord, P. Clark, and M. Gardner.  Reasoning over paragraph effects in situations.  In Proc. MRQA Workshop (EMNLP’19), 2019.  also arXiv:1908.05852.
  * Mihaylov et al. (2018) T. Mihaylov, P. Clark, T. Khot, and A. Sabharwal.  Can a suit of armor conduct electricity? a new dataset for open book question answering.  In EMNLP, 2018.
  * Musa et al. (2019) R. Musa, X. Wang, A. Fokoue, N. Mattei, M. Chang, P. Kapanipathi, B. Makni, K. Talamadupula, and M. Witbrock.  Answering science exam questions using query reformulation with background knowledge.  In AKBC, 2019.
  * Ni et al. (2019) J. Ni, C. Zhu, W. Chen, and J. McAuley.  Learning to attend on essential terms: An enhanced retriever-reader model for open-domain question answering.  In NAACL-HLT, 2019.
  * Raffel et al. (2020) C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  J. Mach. Learn. Res., 21:140:1–140:67, 2020.
  * Rajpurkar et al. (2016) P. Rajpurkar, J. Zhang, K. Lopyrev, and P. Liang.  SQuAD: 100,000+ questions for machine comprehension of text.  In EMNLP, 2016.
  * Rashkin et al. (2018) H. Rashkin, A. Bosselut, M. Sap, K. Knight, and Y. Choi.  Modeling naive psychology of characters in simple commonsense stories.  In ACL, 2018.
  * Talmor et al. (2019) A. Talmor, J. Herzig, N. Lourie, and J. Berant.  CommonsenseQA: A question answering challenge targeting commonsense knowledge.  In NAACL-HLT, 2019.
  * Williams and Zipser (1989) R. J. Williams and D. Zipser.  A learning algorithm for continually running fully recurrent neural networks.  Neural Computation, 1:270–280, 1989.
  * Xie et al. (2020) Z. Xie, S. Thiem, J. Martin, E. Wainwright, S. Marmorstein, and P. A. Jansen.  WorldTree V2: A corpus of science-domain structured explanations and inference patterns supporting multi-hop inference.  In LREC, 2020.
  * Yang et al. (2018) Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. W. Cohen, R. Salakhutdinov, and C. D. Manning.  HotpotQA: A dataset for diverse, explainable multi-hop question answering.  In EMNLP, 2018.
  * Zellers et al. (2019) R. Zellers, Y. Bisk, A. Farhadi, and Y. Choi.  From recognition to cognition: Visual commonsense reasoning.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6713–6724, 2019.
  * Zhou et al. (2020) B. Zhou, K. Richardson, Q. Ning, T. Khot, A. Sabharwal, and D. Roth.  Temporal reasoning on implicit events from distant supervision.  ArXiv, abs/2010.12753, 2020.

Appendix A. Instructions to Crowdworkers Below are the instructions provided
to the (Amazon Mechanical Turk) crowdworkers for answering DA questions: