Research Articles:

**Single-quadrature continuous-variable quantum key
distribution** (pp1081-1095)

Tobias Gehring,
Christian S. Jacobsen, and Ulrik L. Andersen

Most continuous-variable quantum key distribution schemes are based on
the Gaussian modulation of coherent states followed by continuous
quadrature detection using homodyne detectors. In all previous schemes,
the Gaussian modulation has been carried out in conjugate quadratures
thus requiring two independent modulators for their implementations.
Here, we propose and experimentally test a largely simplified scheme in
which the Gaussian modulation is performed in a single quadrature. The
scheme is shown to be asymptotically secure against collective attacks,
and considers a specific attack using asymmetric preparation and excess
noise. We find that this protocol is considerably more sensitive to
noise than other CVQKD schemes, as a consequence of the simplified
implementation. A single-quadrature modulation approach renders the need
for a costly amplitude modulator unnecessary, and thus facilitates
commercialization of continuous-variable quantum key distribution,
provided that the low noise requirement can be achieved.

**Optimal and asymptotically optimal NCT reversible
circuits by the gate types** (pp1096-1112)

Dmitri Maslov

We report optimal and asymptotically optimal reversible circuits
composed of NOT, CNOT, and Toffoli (NCT) gates, keeping the count by the
subsets of the gate types used. This study fine tunes the circuit
complexity figures for the realization of reversible functions via
reversible NCT circuits. An important consequence is a result on the
limitation of the use of the $T$-count quantum circuit metric popular in
applications.

**Quantum circuits for qubit fusion** (pp1113-1124)

Jonathan Edward
Moussa

We consider four-dimensional qudits as qubit pairs and their qudit Pauli
operators as qubit Clifford operators. This introduces a nesting, $C_1^2
\subset C_2^4 \subset C_3^2$, where $C_n^m$ is the $n$th level of the
$m$-dimensional qudit Clifford hierarchy. If we can convert between
logical qubits and qudits, then qudit Clifford operators are qubit
non-Clifford operators. Conversion is achieved by qubit fusion and qudit
fission using stabilizer circuits that consume a resource state. This
resource is a fused qubit stabilizer state with a fault-tolerant state
preparation using stabilizer circuits.

**Quantum simulations of one dimensional quantum
systems** (pp1125-1168)

Rolando Diego
Somma

We present quantum algorithms for the simulation of quantum systems in
one spatial dimension, which result in quantum speedups that range from
superpolynomial to polynomial. We first describe a method to simulate
the evolution of the quantum harmonic oscillator (QHO) based on a
refined analysis of the Trotter-Suzuki formula that exploits the Lie
algebra structure. For total evolution time $t$ and precision
$\epsilon>0$, the complexity of our method is $ O(\exp(\gamma \sqrt{ \log(N/\epsilon)}))$,
where $\gamma>0$ is a constant and $N$ is the quantum number associated
with an ``energy cutoff'' of the initial state. Remarkably, this
complexity is subpolynomial in $N/\epsilon$. We also provide a method to
prepare

discrete versions of the eigenstates of the QHO of complexity polynomial
in $\log(N)/\epsilon$, where $N$ is the dimension or number of points in
the discretization. Next, we consider a system with a quartic potential.
Our numerical simulations suggest a method for simulating the evolution
of sublinear complexity $\tilde O(N^{1/3+o(1)})$, for constant $t$ and
$\epsilon$. We also analyze complex one-dimensional systems and prove a
complexity bound $\tilde O(N)$, under fairly general assumptions. Our
quantum algorithms may find applications in other problems. As an
example, we discuss a generalization of the Fourier transform that is
useful for signal analysis and can be formulated in terms of the
evolution of the QHO.

**The quantum complexity of approximating the
frequency moments** (pp1169-1190)

Ashley Montanaro

The k'th frequency moment of a sequence of integers is defined as $F_k =
\sum_j n_j^k$, where $n_j$ is the number of times that $j$ occurs in the
sequence. Here we study the quantum complexity of approximately
computing the frequency moments in two settings. In the query complexity
setting, we wish to minimise the number of queries to the input used to
approximate $F_k$ up to relative error $\epsilon$. We give quantum
algorithms which outperform the best possible classical algorithms up to
quadratically. In the multiple-pass streaming setting, we see the
elements of the input one at a time, and seek to minimise the amount of
storage space, or passes over the data, used to approximate $F_k$. We
describe quantum algorithms for $F_0$, $F_2$ and $F_\infty$ in this
model which substantially outperform the best possible classical
algorithms in certain parameter regimes.

**The structure of nearly-optimal quantum strategies
for the non-local XOR games** (pp1191-1211)

Dimiter Ostrev

We consider the infinite family of non-local games CHSH$(n)$. We
consider nearly-optimal strategies for CHSH$(n)$. We introduce a notion
of approximate homomorphism for strategies and show that any
nearly-optimal strategy for
non-local XOR is
approximately homomorphic to the canonical optimal
non-local XOR strategy.
This demonstrates that any nearly-optimal
non-local XOR strategy must
approximately contain the algebraic structure of the canonical optimal
strategy.

**A quantum version of Schoning's algorithm applied
to quantum 2-SAT** (pp1212-1227)

Edward Farhi,
Shelby Kimmel, and Kristan Temme

We study a quantum algorithm that consists of a simple quantum Markov
process, and we analyze its behavior on restricted versions of Quantum
2-SAT. We prove that the algorithm solves these decision problems with
high probability for $n$ qubits, $L$ clauses, and promise gap $c$ in
time ${\cal O}(n^2 L^2 c^{-2})$. If the Hamiltonian is additionally
polynomially gapped, our algorithm efficiently produces a state that has
high overlap with the satisfying subspace. The Markov process we study
is a quantum analogue of Sch\"oning's probabilistic algorithm for
$k$-SAT.

**Random MERA states and the tightness of the Brandao-Horodecki
entropy bound** (pp1228-1252)

Matthew Hastings

We construct a random MERA state with a bond dimension that varies with
the level of the MERA. This causes the state to exhibit a very different
entanglement structure from that usually seen in MERA, with neighboring
intervals of length $l$ exhibiting a mutual information proportional to
$\epsilon l$ for some constant $\epsilon$, up to a length scale
exponentially large in $\epsilon$. We express the entropy of a random
MERA in terms of sums over cuts through the MERA network, with the
entropy in this case controlled by the cut minimizing bond dimensions
cut through. One motivation for this construction is to investigate the
tightness of the Brandao-Horodecki\cite{bh} entropy bound relating
entanglement to correlation decay. Using the random MERA, we show that
at least part of the proof is tight: there do exist states with the
required property of having linear mutual information between
neighboring intervals at all length scales. We conjecture that this
state has exponential correlation decay and that it demonstrates that
the Brandao-Horodecki bound is tight (at least up to constant factors),
and we provide some numerical evidence for this as well as a sketch of
how a proof of correlation decay might proceed.