Vol.11
No.3&4 March 1, 2011
Research Articles:
Quantum adiabatic
algorithms, small gaps, and different paths
(pp0181-0214)
Edward
Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer,
and Peter Shor
We construct a set of instances of 3SAT which are not solved efficiently
using the simplest quantum adiabatic algorithm. These instances are
obtained by picking random clauses all consistent with two disparate
planted solutions and then penalizing one of them with a single
additional clause. We argue that by randomly modifying the beginning
Hamiltonian, one obtains (with substantial probability) an adiabatic
path that removes this difficulty. This suggests that the quantum
adiabatic algorithm should in general be run on each instance with many
different random paths leading to the problem Hamiltonian. We do not
know whether this trick will help for a random instance of 3SAT (as
opposed to an instance from the particular set we consider), especially
if the instance has an exponential number of disparate assignments that
violate few clauses. We use a continuous imaginary time Quantum Monte
Carlo algorithm in a novel way to numerically investigate the ground
state as well as the first excited state of our system. Our arguments
are supplemented by Quantum Monte Carlo data from simulations with up to
150 spins.
Uniform
approximation by (quantum) polynomials
(pp0215-0225)
Andrew Drucker and
Ronald de Wolf
We show that quantum algorithms can be used to re-prove a classical
theorem in approximation theory, Jackson's Theorem, which gives a
nearly-optimal quantitative version of Weierstrass's Theorem on uniform
approximation of continuous functions by polynomials. We provide two
proofs, based respectively on quantum counting and on quantum phase
estimation.
Information
reconciliation for QKD
(pp0226-0238)
David
Elkouss, Jesus Martinez-Mateo, and Vicente Martin
Quantum key distribution (QKD) relies on quantum and classical
procedures in order to achieve the growing of a secret random string
---the key--- known only to the two parties executing the protocol.
Limited intrinsic efficiency of the protocol, imperfect devices and
eavesdropping produce errors and information leakage from which the set
of measured signals ---the raw key--- must be stripped in order to
distill a final, information theoretically secure, key. The key
distillation process is a classical one in which basis reconciliation,
error correction and privacy amplification protocols are applied to the
raw key. This cleaning process is known as information reconciliation
and must be done in a fast and efficient way to avoid cramping the
performance of the QKD system. Brassard and Salvail proposed a very
simple and elegant protocol to reconcile keys in the secret-key
agreement context, known as \textit{Cascade}, that has become the
de-facto standard for all QKD practical implementations. However, it is
highly interactive, requiring many communications between the legitimate
parties and its efficiency is not optimal, imposing an early limit to
the maximum tolerable error rate. In this paper we describe a
low-density parity-check reconciliation protocol that improves
significantly on these problems. The protocol exhibits better efficiency
and limits the number of uses of the communications channel. It is also
able to adapt to different error rates while remaining efficient, thus
reaching longer distances or higher secure key rate for a given QKD
system.
New families of
asymmetric quantum BCH codes
(pp0239-0252)
Giuliano G. La
Guardia
Several families of nonbinary asymmetric quantum Bose-Chaudhuri-Hocquenghem
(BCH) codes are presented in this paper. These quantum codes have
parameters better than the ones available in the literature.
Additionally, such codes can be applied in quantum systems where the
asymmetry between qudit-flip and phase-shift errors is large.
Localization of
quantum walks on a deterministic recursive tree
(pp0253-0261)
Xin-Ping Xu
Localization of quantum walks can be characterized by the return
probability, i.e., the probability for the walker returning to its
original site. In this paper, we consider localization of
continuous-time quantum walks in terms of return probability on a
deterministic recursive tree, which is generated by adding one node and
connecting it to each node of the existing tree recursively. We obtain
an approximate form for the return probability using the complete
eigenvalues and eigenstates of Laplace matrix of the structure. It is
found that the return probability depends on the initial node of the
excitation. When the walk starts at the central nodes, the return
probability converges to a constant value even in the limit of infinite
system, in contrast to an exponential decay of the return probability if
the walk starts at the outlying nodes. We also observe a bipartite
structure for the distribution of return probability, and provide
theoretical interpretation for all our findings. Our results suggest
that quantum walks display significant localization and well-bedded
structure of return probability on heterogeneous trees.
Block-based
quantum-logic synthesis 262
(pp0262-0277)
Mehdi Saeedi, Mona
Arabzadeh, Morteza Saheb Zamani, and Mehdi Sedighi
In this paper, the problem of constructing an efficient quantum circuit
for the implementation of an arbitrary quantum computation is addressed.
To this end, a basic block based on the cosine-sine decomposition method
is suggested which contains $l$ qubits. In addition, a previously
proposed quantum-logic synthesis method based on quantum Shannon
decomposition is recursively applied to reach unitary gates over $l$
qubits. Then, the basic block is used and some optimizations are applied
to remove redundant gates. It is shown that the exact value of $l$
affects the number of one-qubit and CNOT gates in the proposed method.
In comparison to the previous synthesis methods, the value of $l$ is
examined consequently to improve either the number of CNOT gates or the
total number of gates.
The proposed approach is further analyzed by considering the nearest
neighbor limitation. According to our evaluation, the number of CNOT
gates is increased by at most a factor of $\frac{5}{3}$ if the nearest
neighbor interaction is applied.
Entanglement in
massive coupled oscillators 278
(pp0278-0299)
Nathan L. Harshman
and William F. Flynn
This article investigates entanglement of the motional states of massive
coupled oscillators. The specific realization of an idealized diatomic
molecule in one-dimension is considered, but the techniques developed
apply to any massive particles with two degrees of freedom and a
quadratic Hamiltonian. We present two methods, one analytic and one
approximate, to calculate the interatomic entanglement for Gaussian and
non-Gaussian pure states as measured by the purity of the reduced
density matrix. The cases of free and trapped molecules and hetero- and
homonuclear molecules are treated. In general, when the trap frequency
and the molecular frequency are very different, and when the atomic
masses are equal, the atoms are highly-entangled for molecular coherent
states and number states. Surprisingly, while the interatomic
entanglement can be quite large even for molecular coherent states, the
covariance of atomic position and momentum observables can be entirely
explained by a classical model with appropriately chosen statistical
uncertainty.
Universal quantum computing in
linear nearest neighbor architectures
(pp0300-0312)
Preethika Kumar
and Steven R. Skinner
We introduce a scheme for realizing universal
quantum computing in a linear nearest neighbor architecture with fixed
couplings. We first show how to realize a controlled-NOT gate operation
between two adjacent qubits without having to isolate the two qubits
from qubits adjacent to them. The gate operation is implemented by
applying two consecutive pulses of equal duration, but varying
amplitudes, on the target qubit. Since only a single control parameter
is required in implementing our scheme, it is very efficient. We next
show how our scheme can be used to realize single qubit rotations and
two-qubit controlled-unitary operations. As most proposals for solid
state implementations of a quantum computer use a one-dimensional line
of qubits, the schemes presented here will be extremely useful.
Efficient photon
sorter in a high-dimensional state space 313
(pp0313-0325)
Warner A. Miller
An increase in the dimension of state space for quantum key distribution
(QKD) can decrease its fidelity requirements while also increasing its
bandwidth. A significant obstacle for QKD with qu$d$its ($d\geq 3$) has
been an efficient and practical quantum state sorter for photons whose
complex fields are modulated in both amplitude and phase. We propose
such a sorter based on a multiplexed thick hologram, constructed e.g.
from photo-thermal refractive (PTR) glass. We validate this approach
using coupled-mode theory with parameters consistent with PTR glass to
simulate a holographic sorter. The model assumes a three-dimensional
state space spanned by three tilted planewaves. The utility of such a
sorter for broader quantum information processing applications can be
substantial.
Global geometric
entanglement in transverse-field XY spin chains: finite and infinite
systems 326
(pp0326-0354)
Tzu-Chieh Wei,
Smitha Vishveshwara, and Paul M. Goldbart
The entanglement in quantum XY spin chains of arbitrary
length is investigated via the geometric measure of entanglement. The
emergence of entanglement is explained intuitively from the perspective
of perturbations. The model is solved exactly and the energy spectrum is
determined and analyzed in particular for the lowest two levels for both
finite and infinite systems. The overlaps for these two levels are
calculated analytically for arbitrary number of spins. The entanglement
is hence obtained by maximizing over a single parameter. The
corresponding ground-state
entanglement surface is then determined over the entire phase diagram,
and its behavior can be used to delineate the boundaries in the phase
diagram. For example, the field-derivative of the entanglement becomes
singular along the critical line. The form of the divergence is derived
analytically and it turns out to be dictated by the universality class
controlling the quantum phase transition. The behavior of the
entanglement near criticality can be understood via a scaling
hypothesis, analogous to that for free energies. The entanglement
density vanishes along the so-called disorder line in the phase diagram,
the ground space is doubly degenerate and spanned by two product states.
The entanglement for the superposition of the lowest two states is also
calculated. The exact value of the entanglement depends on the specific
form of superposition. However, in the thermodynamic limit the
entanglement density turns out to be independent of the superposition.
This proves that the entanglement density is insensitive to whether the
ground state is chosen to be the spontaneously $Z_2$ symmetry broken one
or not. The finite-size scaling of entanglement at critical points is
also investigated from two different view points. First, the maximum in
the field-derivative of the entanglement density is computed and fitted
to a logarithmic dependence of the system size, thereby deducing the
correlation length exponent for the Ising class using only the behavior
of entanglement. Second, the entanglement density itself is shown to
possess a correction term inversely proportional to the system size,
with the coefficient being universal (but with different values for the
ground state and the first excited state, respectively).
back to QIC online Front page
|