Research Articles:
Quantum lower bound for inverting a permutation
with advice
(pp0901-0913)
Aran
Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Given a random permutation $f: [N] \to [N]$ as a black box and $y \in
[N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we
are given classical advice in the form of a pre-computed data structure;
this advice can depend on the permutation but \emph{not} on the input
$y$. Classically, there is a data structure of size $\tilde{O}(S)$ and
an algorithm that with the help of the data structure, given $f(x)$, can
invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$,
$T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot
S = \tilde{\Omega}(\eps N)$ for quantum algorithms that invert a random
permutation $f$ on an $\eps$ fraction of inputs, where $T$ is the number
of queries to $f$ and $S$ is the amount of advice. This answers an open
question of De et al. We also give a $\Omega(\sqrt{N/m})$ quantum lower
bound for the simpler but related Yao's box problem, which is the
problem of recovering a bit $x_j$, given the ability to query an $N$-bit
string $x$ at any index except the $j$-th, and also given $m$ bits of
classical advice that depend on $x$ but not on $j$.
Quantum circuits for asymmetric 1 to n quantum
cloning
(pp0914-0922)
Xi-Jun Ren and
Heng Fan
In this paper, we considered asymmetric $1\rightarrow n$ cloning
circuits generalized from the asymmetric $1\rightarrow 2$ cloning
circuit proposed by Bu\v{z}ek \textit{et al.} [Phys. Rev. A 56, 3446
(1997)]. The generalization is based on an information flux insight of
the original cloning circuit. Specifically, the circuit separately and
sequentially transfers the Z-type information and X-type information of
the input state to the output copies with controlled-not gates. The
initial input state of the clones defines the asymmetry among all output
clones. Although the generalized circuits do not perform universally,
the averaged fidelities over a uniform distribution of all possible
input cloning states saturate the optimal fidelity tradeoff relations of
universal asymmetric cloning.
Entanglement and swap of quantum states in two
qubits
(pp0923-0931)
Takaya
Ikuto and Satoshi Ishizaka
Suppose that two distant parties Alice and Bob share an entangled state
$\rho_{AB}$, and they want to exchange the subsystems of $\rho_{AB}$ by
local operations and classical communication (LOCC). In general, this
LOCC task (i.e. the LOCC transformation of $\rho_{AB} \to V\rho_{AB} V$
with $V$ being a swap operator) is impossible deterministically, but
becomes possible probabilistically. In this paper, we study how the
optimal probability is related to the amount of entanglement in the
framework of positive partial transposed (PPT) operations, and
numerically show a remarkable class of states whose probability is the
smallest among every state in two quantum bits.
Optimal ancilla-free Clifford+V approximation of
z-rotations
(pp0932-0950)
Neil J. Ross
We describe a new efficient algorithm to approximate $z$-rotations by
ancilla-free Clifford+$V$ circuits, up to a given precision $\epsilon$.
Our algorithm is optimal in the presence of an oracle for integer
factoring: it outputs the shortest Clifford+$V$ circuit solving the
given problem instance. In the absence of such an oracle, our algorithm
is still near-optimal, producing circuits of $V$\!-count $m +
O(\log(\log(1/\epsilon)))$, where $m$ is the $V$\!-count of the
third-to-optimal solution. A restricted version of the algorithm
approximates $z$-rotations in the Pauli+$V$ gate set. Our method is
based on previous work by the author and Selinger on the optimal ancilla-free
approximation of $z$-rotations using Clifford+$T$ gates and on previous
work by Bocharov, Gurevich, and Svore on the asymptotically optimal
ancilla-free approximation of $z$-rotations using Clifford+$V$ gates.
Geometric phase carried by the observables and its
application to quantum computation
(pp0951-0961)
Zisheng Wang and
Hui Pan
We investigate geometric phases in terms of Heisenberg equation. We find
that, equivalently to Schr\"odinger picture with a memory of its motion
in terms of the geometric phase factor contained in the wave function,
the observales carry with the geometric message under their evolutions
in the Heisenberg picture. Such an intrinsic geometric feature may be
particularly useful to implement the multi-time correlation geometric
quantum gate in terms of the observables, which leads to a possible
reduction in experimental errors as well as gate timing. An application
is discussed for nuclear-magnetic-resonance system, where the geometric
quantum gate is proposed.
Reduced space-time and time costs Ising
dislocation codes and arbitrary ancillas
(pp0962-0986)
Matthew B.
Hastings and A. Geller
We propose two distinct methods of improving quantum computing protocols
based on surface codes. First, we analyze the use of dislocations
instead of holes to produce logical qubits, potentially reducing
spacetime volume required. Dislocations\cite{dis2,dis} induce defects
which, in many respects, behave like Majorana quasi-particles. We
construct circuits to implement these codes and present fault-tolerant
measurement methods for these and other defects which may reduce spatial
overhead. One advantage of these codes is that Hadamard gates take
exactly $0$ time to implement. We numerically study the performance of
these codes using a minimum weight and a greedy decoder using
finite-size scaling. Second, we consider state injection of arbitrary
ancillas to produce arbitrary rotations. This avoids the logarithmic (in
precision) overhead in online cost required if $T$ gates are used to
synthesize arbitrary rotations. While this has been considered before\cite{ancilla},
we consider also the parallel performance of this protocol. Arbitrary
ancilla injection leads to a probabilistic protocol in which there is a
constant chance of success on each round; we use an amortized analysis
to show that even in a parallel setting this leads to only a constant
factor slowdown as opposed to the logarithmic slowdown that might be
expected naively.
A constructive quantum Lovasz local lemma for
commuting projectors
(pp0987-0996)
Or Sattath and
Itai Arad
The Quantum Satisfiability problem generalizes the Boolean
satisfiability problem to the quantum setting by replacing classical
clauses with local projectors. The Quantum Lov\'asz Local Lemma gives a
sufficient condition for a Quantum Satisfiability problem to be
satisfiable~\cite{ambainis2012quantum}, by generalizing the classical
Lov\'asz Local Lemma. The next natural question that arises is: can a
satisfying quantum state be \emph{efficiently} found, when these
conditions hold? In this work we present such an algorithm, with the
additional requirement that all the projectors commute. The proof
follows the information theoretic proof given by Moser's breakthrough
result in the classical setting~\cite{moser2009constructiveSTOC}.
Similar results were independently published
in~\cite{cubitt2011constructive, cubitt2013quantum}.
Leakage suppression in the toric code
(pp0997-1016)
Martin Suchara,
Andrew W. Cross, Jay M. Gambetta
Quantum codes excel at correcting local noise but fail to correct
leakage faults that excite qubits to states outside the computational
space. Aliferis and Terhal \cite{aliferis07} have shown that an accuracy
threshold exists for leakage faults using gadgets called leakage
reduction units (LRUs). However, these gadgets reduce the accuracy
threshold and increase overhead and experimental complexity, and these
costs have not been thoroughly understood. We explore a variety of
techniques for leakage-resilient, fault-tolerant error correction in
topological codes. Our contributions are threefold. First, we develop a
leakage model that is physically motivated and efficient to simulate.
Second, we use Monte-Carlo simulations to survey several syndrome
extraction circuits. Third, given the capability to perform 3-outcome
measurements, we present a dramatically improved syndrome processing
algorithm. Our simulations show that simple circuits with one extra CNOT
per check operator and no additional ancillas reduce the accuracy
threshold by less than a factor of $4$ when leakage and depolarizing
noise rates are comparable. This becomes a factor of $2$ when the
decoder uses 3-outcome measurements. Finally, when the physical error
rate is less than $2\times 10^{-4}$, placing LRUs after every gate may
achieve the lowest logical error rates of all of the circuits we
considered. We anticipate that the closely related planar codes might
exhibit the same accuracy thresholds and that the ideas may generalize
naturally to other topological codes.
Modular quantum memories using passive linear
optics and coherent feedback
(pp1017-1040)
Hendra I. Nurdin
and John E. Gough
In this paper, we show that quantum memory for qudit states encoded in a
single photon pulsed optical field has a conceptually simple modular
realization using only passive linear optics and coherent feedback. We
exploit the idea that two decaying optical cavities can be coupled in a
coherent feedback configuration to create an internal mode of the
coupled system which is isolated and decoherence-free for the purpose of
qubit storage. The qubit memory can then be switched between
writing/read-out mode and storage mode simply by varying the routing of
certain freely propagating optical fields in the network. It is then
shown that the qubit memories can be interconnected with one another to
form a qudit quantum memory. We explain each of the phase of writing,
storage, and read-out for this modular quantum memory scheme. The
results point a way towards modular architectures for complex compound
quantum memories.
Quantum information splitting using a pair of GHZ
states
(pp1041-1047)
Kaushik Nandi and
Goutam Paul
We describe a protocol for quantum information splitting (QIS) of a
restricted class of three-qubit states among three parties Alice, Bob
and Charlie, using a pair of GHZ states as the quantum channel. There
are two different forms of this three-qubit state that is used for QIS
depending on the distribution of the particles among the three parties.
There is also a special type of four-qubit state that can be used for
QIS using the above channel. We explicitly construct the quantum
channel, Alice's measurement basis and the analytic form of the unitary
operations required by the receiver for such a purpose.
An almost sudden jump in quantum complexity
(pp1048-1059)
Or Sattath
The Quantum Satisfiability problem ($\qsat$) is the generalization of
the canonical $\NPC$ problem - Boolean Satisfiability. $\ksqsat$ is the
following variant of the problem: given a set of projectors of rank $1$,
acting non-trivially on $k$ qubits out of $n$ qubits, such that each
qubit appears in at most $s$ projectors, decide whether there exists a
quantum state in the null space of all the projectors. Let $\qf(k)$ be
the maximal integer $s$ such that every $\ksqsat$ instance is
satisfiable. Deciding $\ksqsat[\qf(k)]$ is computationally easy: by
definition the answer is ``satisfiable''. But, by relaxing the
conditions slightly, we show that $\ksqsat[\qf(k)+2]$ is $\QMAoH$, for
$k \geq 15$. This is a quantum analogue of a classical result by
Kratochv{\'\i}l et al.~\cite{kratochvil1993one}. We use the term ``an \emph{almost}
sudden jump'' to stress that the complexity of $\ksqsat[\qf(k)+1]$ is
open, where the jump in the classical complexity is known to be sudden.
We present an implication of this finding to the quantum PCP conjecture,
arguably one of the most important open problems in the field of
Hamiltonian complexity. Our implication imposes some constraints on one
possible way to refute the quantum PCP.
The non-uniform stationary measure for
discrete-time quantum walks in one dimension
(pp1060-1075)
Norio Konno and
Masato Takei
We consider stationary measures of the one-dimensional
discrete-time quantum walks (QWs) with two chiralities, which is defined
by a 2 $\times$ 2 unitary matrix $U$. In our previous paper
\cite{Konno2014}, we proved that any uniform measure becomes the
stationary measure of the QW by solving the corresponding eigenvalue
problem. This paper reports that non-uniform measures are also
stationary measures of the QW except when $U$ is diagonal. For diagonal
matrices, we show that any stationary measure is uniform. Moreover, we
prove that any uniform measure becomes a stationary measure for more
general QWs not by solving the eigenvalue problem but by a simple
argument.