Vol.5 No.2 March 3, 2005
Research and Review Articles:
New construction of mutually unbiased bases in square dimensions (pp093-101)
         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 design-theoretic 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 non-prime-power dimensions than the construction that reduces the problem to prime power dimensions.

Quantum computing and polynomial equations over Z_2 (pp102-112)
         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.

Graph-based simulation of quantum computation in the density matrix representation (pp113-130)
         G. F. Viamontes, I. L. Markov, and J. P. Hayes
Quantum-mechanical 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 array-based 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 graph-based algorithms implemented in the simulator QuIDDPro/D. While previously reported graph-based simulators operate in terms of the state-vector 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 array-based 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 graph-based approach far outperforms the array-based approach for these circuits.

Broken promises and quantum algorithms (pp131-145)
         A. Brazier and M.B. Plenio
Entanglement tensor for a general pure multipartite quantum state (pp146-155)
         H. Heydari and G. Bjork
In the black-box 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 Deutsch-Jozsa algorithm. More recently, Wim van Dam put forward an algorithm for unstructured problems (i.e., those without a promise). We consider the Deutsch-Jozsa 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 Deutsch-Jozsa 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 Deutsch-Jozsa algorithm as the promise is weakened.

Correcting quantum channels by measuring the environment (pp156-160)
         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 three-qubit and four-qubit states. It is shown that in defining the degree of entanglement of a multi-partite 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 multi-qubit states.

Comments and Reply:
Can quantum cryptography imply quantum mechanics? (pp161-169)
         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 (pp170-175)
         H. Halvorson and J. Bub
Clifton, Bub, and Halvorson (CBH) have argued that quantum mechanics can be derived from three cryptographic, or broadly information-theoretic, 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 (pp176-177)
         S. Aaronson
Book Review:
On “Principles of Quantum Computation and Information Volume 1: Basic Concepts” (pp178-180)
         D. Bacon

back to QIC online Front page