Vol.10
No.1&2
January 1, 2010
Research Articles:
Random quantum
satisfiability
(pp0001-0015)
C.R.
Laumann, R. Moessner, A. Scarddichio, and S.L. Sondhi
Alongside the effort underway to build quantum computers, it is
important to better understand which classes of problems they will find
easy and which others even they will find intractable. We study random
ensembles of the QMA$_1$-complete quantum satisfiability (QSAT) problem
introduced by Bravyi \cite{Bravyi:2006p4315}. QSAT appropriately
generalizes the NP-complete classical satisfiability (SAT) problem. We
show that, as the density of clauses/projectors is varied, the ensembles
exhibit quantum phase transitions between phases that are satisfiable
and unsatisfiable. Remarkably, almost all instances of QSAT for \emph{any}
hypergraph exhibit the same dimension of the satisfying manifold. This
establishes the QSAT decision problem as equivalent to a, potentially
new, graph theoretic problem and that the hardest typical instances are
likely to be localized in a bounded range of clause density.
Efficient universal quantum
circuits
(pp0016-0027)
D.
Bera, S. Fenner, F. Green, and S. Homer
Universal circuits can be viewed as general-purpose simulators for
central classes of circuits and can be used to capture the computational
power of the circuit class being simulated. We define and construct
quantum universal circuits which are efficient and has very little
overhead in simulation. For depth we construct universal circuits whose
depth is the same order as the circuits being simulated. For size, there
is a log factor blow-up in the universal circuits constructed here which
is nearly optimal.
Single qubit quantum secret
sharing with improved security
(pp0028-0040)
G.P. He and Z.D. Wang
Analyzing carefully an experimentally feasible non-entangled single
qubit quantum secret sharing protocol and its modified version [Phys.
Rev. Lett. 95, 230505 (2005); \textit{ibid}. 98, 028902 (2007)], it is
found that both versions are insecure against coherent attacks though
the original idea is so remarkable. To overcome this fatal flaw, here we
propose a protocol with a distinct security checking strategy, which
still involves single qubit operations only, making it possible to
achieve better security of quantum secret sharing with current
technology.
C_3, semi-Clifford and
genralized semi-Clifford operations
(pp0041-0059)
S.
Beigi and P.W. Shor
Fault-tolerant quantum computation is a basic problem in quantum
computation, and teleportation is one of the main techniques in this
theory. Using teleportation on stabilizer codes, the most well-known
quantum codes, Pauli gates and Clifford operators can be applied
fault-tolerantly. Indeed, this technique can be generalized for an
extended set of gates, the so called ${\mathcal{C}}_k$ hierarchy gates,
introduced by Gottesman and Chuang (Nature, 402, 390-392). ${\mathcal{C}}_k$
gates are a generalization of Clifford operators, but our knowledge of
these sets is not as rich as our knowledge of Clifford gates. Zeng et
al. in (Phys. Rev. A 77, 042313) raise the question of the relation
between ${\mathcal{C}}_k$ hierarchy and the set of semi-Clifford and
generalized semi-Clifford operators. They conjecture that any ${\mathcal{C}}_k$
gate is a generalized semi-Clifford operator. In this paper, we prove
this conjecture for $k=3$. Using the techniques that we develop, we
obtain more insight on how to characterize ${\mathcal{C}}_3$ gates.
Indeed, the more we understand ${\mathcal{C}}_3$, the more intuition we
have on ${\mathcal{C}}_k$, $k\geq 4$, and then we have a way of
attacking the conjecture for larger $k$.
Security of quantum key
distribution with bit and basis dependent detector flaws
(pp0060-0076)
L.
Lydersen and J. Skaar
We consider the security of the Bennett-Brassard 1984 (BB84) protocol
for Quantum Key Distribution (QKD), in the presence of bit and basis
dependent detector flaws. We suggest a powerful attack that can be used
in systems with detector efficiency mismatch, even if the detector
assignments are chosen randomly by Bob. A security proof is provided,
valid for any basis dependent, possibly lossy, linear optical
imperfections in the channel/receiver/detectors. The proof does not
assume the so-called squashing detector model.
On the complexity of
approximating the diamond norm
(pp0077-0086)
A.
Ben-Aroya and A. Ta-Shma
The diamond norm is a norm defined over the space of quantum
transformations. This norm has a natural operational interpretation: it
measures how well one can distinguish between two transformations by
applying them to a state of arbitrarily large dimension. This
interpretation makes this norm useful in the study of quantum
interactive proof systems. In this note we exhibit an efficient
algorithm for computing this norm using convex programming.
Independently of us, Watrous recently showed a different algorithm to
compute this norm. An immediate corollary of this algorithm is a slight
simplification of the argument of Kitaev and Watrous that QIP \subseteq
\EXP.
Quantum universality by state
distillationIndirect quantum control for finite-dimensional coupled
systems
(pp0087-0096)
J.
Nie, H.C. Fu, and X.X. Yi
We present a new analysis on the quantum control for a quantum system
coupled to a quantum probe. This analysis is based on the coherent
control for the quantum system and a hypothesis that the probe can be
prepared in specified initial states. The results show that a quantum
system can be manipulated by probe state-dependent coherent control. In
this sense, the present analysis provides a new control scheme which
combines the coherent control and state preparation technology.
The LU-LC conjecture is false
(pp0097-0108)
Z.-F.
Ji, J.-X. Chen, Z.-H. Wei, and M.-S. :Ying
The LU-LC conjecture is an important open problem concerning the
structure of entanglement of states described in the stabilizer
formalism. It states that two local unitary equivalent stabilizer states
are also local Clifford equivalent. If this conjecture were true, the
local equivalence of stabilizer states would be extremely easy to
characterize. Unfortunately, however, based on the recent progress made
by Gross and Van den Nest, we find that the conjecture is false.
The role of symmetries in
adiabatic quantum algorithms
(pp0109-0140)
G.
Schaller and R. Schutzhold
Exploiting the similarity between adiabatic quantum algorithms and
quantum phase transitions, we argue that second-order transitions --
typically associated with broken or restored symmetries -- should be
advantageous in comparison to first-order transitions.
Guided by simple examples we construct an alternative adiabatic
algorithm for the NP-complete problem {\em Exact Cover 3}. We show
numerically that its average performance (for the considered cases up to
$\ord\{20\}$ qubits) is better than that of the conventional scheme. The
run-time of adiabatic algorithms is not just determined by the minimum
value of the fundamental energy gap (between the ground state and the
exited states), but also by its curvature at the critical point. The
proposed symmetry-restoring adiabatic quantum algorithm only contains
contributions linear and quadratic in the Pauli matrices and can be
generalized to other problem Hamiltonians which are decomposed of terms
involving one and two qubits. We show how the factoring problem can be
cast into such a quadratic form. These findings suggest that adiabatic
quantum algorithms can solve a large class of NP problems much faster
than the Grover search routine (which corresponds to a first-order
transition and yields a quadratic enhancement only).
NP vs QMA_\log(2)
(pp0141-0151)
S.
Beigi
Although it is believed unlikely that $\NP$-hard problems admit
efficient quantum algorithms, it has been shown that a quantum verifier
can solve NP-complete problems given a "short" quantum proof;
more precisely, NP\subseteq QMA_{\log}(2) where QMA_{\log}(2)
denotes the class of quantum Merlin-Arthur games in which there are two
unentangled provers who send two logarithmic size quantum witnesses to
the verifier. The inclusion NP\subseteq QMA_{\log}(2) has
been proved by Blier and Tapp by stating a quantum Merlin-Arthur
protocol for 3-coloring with perfect completeness and gap 1/24n^6.
Moreover, Aaronson et al. have shown the above inclusion with a
constant gap by considering $\widetilde{O}(\sqrt{n})$ witnesses of
logarithmic size. However, we still do not know if QMA_{\log}(2)
with a constant gap contains NP. In this paper, we show that
3-SAT admits a QMA_{\log}(2) protocol with the gap
1/n^{3+\epsilon}} for every constant \epsilon>0.
A non-distillability criterion
for secret correlations
(pp0152-0159)
L.
Masanes and A. Winter
Within entanglement theory there are criteria which certify that some
quantum states cannot be distilled into pure entanglement. An example is
the positive partial transposition criterion. Here we present, for the
first time, the analogous thing for secret correlations. We introduce a
computable criterion which certifies that a probability distribution
between two honest parties and an eavesdropper cannot be
(asymptotically) distilled into a secret key. The existence of
non-distillable correlations with positive secrecy cost, also known as
bound information, is an open question. This criterion may be the key
for finding bound information. However, if it turns out that this
criterion does not detect bound information, then, a very interesting
consequence follows: any distribution with positive secrecy cost can
increase the secrecy content of another distribution. In other words,
all correlations with positive secrecy cost constitute a useful
resource.
Ancilla-assisted
discrimination of quantum gates
(pp160-0177)
J.-X.
Chen and M.-S. Ying
The intrinsic idea of superdense coding is to find as many gates as
possible such that they can be perfectly discriminated. In this paper,
we consider a basic scheme of discrimination of quantum gates, called
ancilla-assisted discrimination, in which a set of quantum gates on a
d-dimensional system are perfectly discriminated with assistance
from an r-dimensional ancilla system. The main contribution of
the present paper is two-fold: (1) The number of quantum gates that can
be discriminated in this scheme is evaluated. We prove that any rd+1
quantum gates cannot be perfectly discriminated with assistance from
the ancilla, and there exist rd quantum gates which can be
perfectly discriminated with assistance from the ancilla. (2) The
dimensionality of the minimal ancilla system is estimated. We prove that
there exists a constant positive number c such that for any k\leq
cr quantum gates, if they are d-assisted discriminable, then
they are also r-assisted discriminable, and there are c^{\prime}rc^{\prime}>c
different quantum gates which can be discriminated with a d-dimensional
ancilla, but they cannot be discriminated if the ancilla is reduced to
an r-dimensional system. Thus, the order O(r) of the
number of quantum gates that can be discriminated with assistance from
an r-dimensional ancilla is optimal. The results reported in this
paper represent a preliminary step toward understanding the role ancilla
system plays in discrimination of quantum gates as well as the power and
limit of superdense coding.
back to QIC online Front page
|