Vol.5 No.2
March 3,
2005
Research and
Review Articles:
New construction of
mutually unbiased bases in square dimensions
(pp093101)
P. Wocjan and T.
Beth
We show that k=w+2 mutually unbiased bases
can be constructed in any square dimension d=s^2 provided that
there are w mutually orthogonal Latin squares of order s.
The construction combines the designtheoretic objects (s,k)nets
(which can be constructed from w mutually orthogonal Latin
squares of order s and vice versa) and generalized Hadamard
matrices of size s. Using known lower bounds on the asymptotic growth of
the number of mutually orthogonal Latin squares (based on number
theoretic sieving techniques), we obtain that the number of mutually
unbiased bases in dimensions d=s^2 is greater than s^{1/14.8}
for all s but finitely many exceptions. Furthermore, our
construction gives more mutually unbiased bases in many nonprimepower
dimensions than the construction that reduces the problem to prime power
dimensions.
Quantum
computing and polynomial equations over Z_2
(pp102112)
C.M. Dawson, H.L.
Haselgrove, A.P. Hines, D. Mortimer, M.A. Nielsen and T.J. Osborne
What is the computational power of a quantum
computer? We show that determining the output of a quantum computation
is equivalent to counting the number of solutions to an easily computed
set of polynomials defined over the finite field Z_2. This
connection allows simple proofs to be given for two known relationships
between quantum and classical complexity classes, namely BQP/P/\#P
and BQP/PP.
Graphbased simulation of quantum computation in the density matrix
representation
(pp113130)
G. F. Viamontes, I. L.
Markov, and J. P. Hayes
Quantummechanical phenomena are playing an
increasing role in information processing, as transistor sizes approach
the nanometer level, and quantum circuits and data encoding methods
appear in the securest forms of communication. Simulating such phenomena
efficiently is exceedingly difficult because of the vast size of the
quantum state space involved. A major complication is caused by errors
(noise) due to unwanted interactions between the quantum states and the
environment. Consequently, simulating quantum circuits and their
associated errors using the density matrix representation is potentially
significant in many applications, but is well beyond the computational
abilities of most classical simulation techniques in both time and
memory resources. The size of a density matrix grows exponentially with
the number of qubits simulated, rendering arraybased simulation
techniques that explicitly store the density matrix intractable. In this
work, we propose a new technique aimed at efficiently simulating quantum
circuits that are subject to errors. In particular, we describe new
graphbased algorithms implemented in the simulator QuIDDPro/D. While
previously reported graphbased simulators operate in terms of the
statevector representation, these new algorithms use the density matrix
representation. To gauge the improvements offered by QuIDDPro/D, we
compare its simulation performance with an optimized arraybased
simulator called QCSim. Empirical results, generated by both simulators
on a set of quantum circuit benchmarks involving error correction,
reversible logic, communication, and quantum search, show that the
graphbased approach far outperforms the arraybased approach for these
circuits.
Broken
promises and quantum algorithms
(pp131145)
A. Brazier and M.B.
Plenio
Entanglement tensor
for a general pure multipartite quantum state
(pp146155)
H. Heydari and G.
Bjork
In the blackbox model, problems constrained by a
`promise' are the only ones that admit a quantum exponential speedup
over the best classical algorithm in terms of query complexity. The most
prominent example of this is the DeutschJozsa algorithm. More recently,
Wim van Dam put forward an algorithm for unstructured problems (i.e.,
those without a promise). We consider the DeutschJozsa algorithm with a
less restrictive (or `broken') promise and study the transition to an
unstructured problem. We compare this to the success of van Dam's
algorithm. These are both compared with a standard classical sampling
algorithm. The DeutschJozsa algorithm remains good as the problem
initially becomes less structured, but the van Dam algorithm can be
adapted so as to become superior to the DeutschJozsa algorithm as the
promise is weakened.
Correcting quantum channels by measuring the environment
(pp156160)
P. Hayden and C.
King
We propose an entanglement tensor to
quantitatively compute the entanglement of a general pure multipartite
quantum state. We compare the ensuing tensor with the concurrence for
bipartite state and apply the tensor measure to some interesting
examples of entangled threequbit and fourqubit states. It is shown
that in defining the degree of entanglement of a multipartite state,
one needs to make assumptions about the willingness of the parties to
cooperate. For such states our tensor becomes a measure of generalized
entanglement of assistance. We also discuss the degree of entanglement
and the concurrence of assistance of two generic multiqubit states.
Comments
and Reply:
Can quantum cryptography
imply quantum mechanics?
(pp161169)
J.A.
Smolin
It has been suggested that the
ability of quantum mechanics to allow
secure distribution of secret key
together with its inability to
allow bit commitment or communicate
superluminally might be
sufficient to imply the rest of quantum
mechanics. I argue using a
toy theory as a counterexample that this
is not the case. I
further discuss whether an additional axiom (key storage)
brings back
the quantum nature of the theory.
Can
quantum cryptography imply quantum mechanics?  reply to Smolin
(pp170175)
H. Halvorson and J.
Bub
Clifton, Bub, and Halvorson (CBH) have argued that
quantum mechanics can be derived from three cryptographic, or broadly
informationtheoretic, axioms. But Smolin disagrees, and he has given a
toy theory that he claims is a counterexample. Here we show that
Smolin's toy theory violates an independence condition for spacelike
separated systems that was assumed in the CBH argument. We then argue
that any acceptable physical theory should satisfy this independence
condition.
Erratum:
Quantum lower bound for
recursive Fourier sampling
(pp176177)
S.
Aaronson
Book
Review:
On “Principles of Quantum
Computation and Information Volume 1: Basic Concepts”
(pp178180)
D. Bacon
back to QIC online Front page
