Return to Program or QIP2002 homepage

Poster Session 1

(we supply a 48x32 inch foam-core backing for each poster)

Monday January 14 2002: 16:15
Mezzanine

Jiangfeng Du: University of Science and Technology of China, djf@ustc.edu.cn
Experimental realization of the entanglement enhanced quantum games

Many previous works on quantum games are based on maximally entangled state. In this letter, we investigate the role of entanglement in quantum games. For the particular case of the quantum Prisoners' Dilemma, the property of the game changes fascinatingly with the variation of the measure of the game's entanglement. Furthermore this quantum game is experimentally realized on our nuclear magnetic resonance quantum computer.

Pawel Hawrylak: Institute for Microstructural Sciences, pawel.hawrylak@nrc.ca, web site
Readout of a single electron spin based quantum bit by current detection

We present theoretical and experimental results demonstrating the read-out of a single and coupled spin based quantum bits by current detection. The quantum bits were built by isolating a single or coupled spin complexes in single and coupled lateral dots with a tunable number of electrons. The spin state of these dots was read from the current amplitude resulting from the injection of spin polarized electrons. The current amplitude showed a systematic dependence on the spin state of the dots controlled by the number of electrons.

Marats Golovkins: Institute of Mathematics and Computer Science, marats@latnet.lv
Quantum Automata and Probabilistic Reversible Automata

This is joint work together with Maksim Kravtsev. To study relationship between quantum automata and probabilistic automata, we introduce definition of probabilistic reversible automata (PRA). These automata use doubly stochastic matrices for their transition function. We prove, that similarly to quantum case, these automata cannot recognize language (a,b)*a. In general, PRA cannot recognize languages violating partial order condition. We also prove that PRA can recognize such languages as a*b* with probability 1-e. An immediate consequence is that quantum automata with mixed states (model of Nayak) recognize a*b* with probability 1-e.

Leonid Fedichkin: Institute of Physics and Technology RAS, lef@zmail.ru, web site
Decoherence of spatial electron states in qubits based on semiconductor quantum dots

Decoherence rates of spatial electron states in semiconductor quantum dots due to interaction of electrons with deformational acoustical and piezoacoustical phonons were obtained. It is shown that such structures based on GaAs substrate can be coherent enough to perform fault tolerant computations.

Viv Kendon: Imperial College, web site
Entanglement in quantum computation

We investigate numerically and anlytically the entanglement in pure states of N qubits both generally and in specific states during the operation of Shor's algorithm on a quantum computer. We find that in typical pure states of N qubits, subsets obtained by partial tracing have positive partial transpose (separable or no free entanglement) if they are smaller than N/3 qubits. This result holds generally for states of N qudits (d-dimensional particles). In Shor's algorithm we find numerically that, while entanglement is present in the states generated during computation, the amount (measured as the entropy of subsystems in bipartite splits) is only very weakly correlated with the success or failure of the result (Shor s algorithm is probabilistic). We discuss the implications these results may have for the role of entanglement in the speed up of quantum computation over classical.

Andrew Landahl: Institute for Quantum Information, Caltech, Pasadena, CA, web site
Continuous quantum error correction via quantum feedback control

We describe a protocol for continuously protecting unknown quantum states from decoherence that incorporates design principles from both quantum error correction and quantum feedback control. Our protocol uses continuous measurements and Hamiltonian operations, which are weaker control tools than are typically assumed for quantum error correction. We develop a cost function appropriate for unknown quantum states and use it to optimize our state-estimate feedback. Using Monte Carlo simulations, we study our protocol for the three-qubit bit-flip code in detail and demonstrate that it can improve the fidelity of quantum states beyond what is achievable using quantum error correction when the time between quantum error correction cycles is limited.

Jiri Vala: Department of Chemistry, University of California at Berkeley
Universal Quantum Computing Operations with Asymmetric Anisotropic Exchange Interaction

The asymmetric anisotropic exchange interaction is explored to generate universal unitary operations on suitably encoded quantum information. The algebraic approach, recently developed and applied for isotropic and symmetric anisotropic exchange, is employed to construct a complete set of encodings of a logical qubit from three physical qubits. Then, the exchange interaction Hamiltonian suffices to generate the complete su(2) algebra over a single logical qubit. The non-trivial two-qubit gates are constructed using suitably timed conjugating operations. The total number of operations needed to implement the controlled-Z gate up to local transformations is five. An appropriate scalable architecture is proposed.

Pawel Wocjan: University of Karlsruhe, wocjan@ira.uka.de
Simulating Hamiltonians in Quantum Networks: Efficient Schemes and Complexity Bounds

We address the problem of simulating pair-interaction Hamiltonians in n node quantum networks where the subsystems have arbitrary, possibly different, dimensions. We show that any pair-interaction can be used to simulate any other by applying sequences of appropriate local control sequences. Efficient schemes for decoupling and time reversal can be constructed from orthogonal arrays. Conditions on time optimal simulation are formulated in terms of spectral majorization of matrices characterizing the coupling parameters. Moreover, we consider a specific system of n harmonic oscillatorswith bilinear interaction. In this case, decoupling can efficiently be achieved using the combinatorial concept of difference schemes. For this type of interactions we present optimal schemes for inversion.

Frank Verstraete: Ghent University, frank.verstraete@kuleuven.ac.be
A comparaison between the violation of Bell inequalities and the entanglement of formation for mixed states of two qubits

We identify all mixed states of two qubits with maximal and minimal violation of the Bell inequalities for given entanglement of formation. It is shown that a whole class of entangled mixed states does not violate any CHSH inequality, even if SLOCC (filtering) operations are allowed before the measurments.

Michael Hamrick: The MITRE Corporation, mhamrick@mitre.org
Quantum Communications Security (QCOMSEC)

We describe a universal framework for analyzing the end-to-end security of communications systems that rely on quantum key distribution to achieve secrecy. This framework is an extension of the standard framework used to analyze the security of classical cryptosystems.

Xiang-Bin Wang: ERATO, Japan Sci. & Tech. Corp., wang@qci.jst.go.jp
On the role of coherent attack in a type of strategic problem wit quantum key destribution

Since Bennett and Brassard suggested their quantum ke distribution protocol(BB84 protocol) in 1984,the subject has been extensively studied both theoretically and experimentlly. The protocol allows two remote parties Alice and Bob to create and share a secrect key using a quantum channel and public authenticated communications. The quantum key created in this way is generally believed to be secure in principle because eavesdroppers have no way to tap the quantum channel without disturbing it. In particular, BB84 protocol has been proven to be unconditionally secure after the error correction and privicy amplification recently. Besides the BB84 protocol, a number of other protocols have been proposed recently. In the security evaluation, evesdropper$'$s strategy to obtain the maxium information given the disturbance to the qubits is often studied. For this strategy, the optimized individual attack have been extensively constructed under various conditions. However, it seems a difficult task in the case of coherent attack, i.e., Eve may treat a number of intercepted qubits collectively, including the collective unitary transformations and the measurements. In this paper we give a general conclusion on the role of coherent attacks for the strategy of maxmizing the information given the disturbance. Suppose in a quantum key distribution(QKD) protocol, all the transmitted bits from Alice are independent and only the individual disturbances to each qubits are examined by Alice and Bob. For this type of protocols( so far almost all QKD protocols belong to this type), in principle no coherent attack is more powerful than the product of optimized individual attack to each individual qubits. All coherent attacks to the above QKD protocols can be disregarded for the strategy above.

Pim Tuyls: Philips Research, pim.tuyls@philips.com
An algebraic approach to quantum cryptography and quantum communication

We present an algebraic approach for describing the impact of a measurement process on the state of a quantum system. It is inspired by the theory of quantum statistical mechanics and quantum dynamical systems. The central notion is that of partition of unity which models the measurement apparatus. This leads to a quantum statistical description of the state of the system after measurement. The uncertainty about this state can then be expressed in terms of quantum entropy. We apply our construction to quantum cryptography and show that natural results are obtained and that noise can easily and in a natural way be embedded. We also derive an upper bound on the average amount of information that can be transmitted through a quantum channel per unit of time.

Gerald Gilbert: The MITRE Corporation, ggilbert@mitre.org
Quantum Key Distribution in Networks

The prospects and requirements for quantum key distribution in network communications architectures are analyzed.

Keith Kastella: Veridian Systems, Keith.Kastella@Veridian.com
Structured quantum search using the density of states

In the multitarget Grover algorithm, we are given an unstructured N-element list of objects S_i containing a T-element subset tau and function f, called an oracle, such that f(S_i)=1 if S_i is in tau, otherwise f(S_i) = 0. By using quantum parallelism, an element of tau can be retrieved in O(sqrt(N/T)) steps, compared to O(N/T) for any classical algorithm. It is shown here that in combinatorial optimization problems with N=4^M, the density of states can be used in conjunction with the multitarget Grover algorithm to construct a sequence of oracles that structure the search so that the optimum state is obtained with certainty in O(log(N)) steps.

Rusins Freivalds: University of Latvia, Rusins.Freivalds@mii.lu.lv, web site
Quantum finite state transducers

We introduce quantum finite state transducers (qfst), and study the class of relations which they compute. It turns out that they share many features with probabilistic finite state transducers, especially regarding undecidability of emptiness (at least for low probability of success). However, like their `little brothers', the quantum finite automata, the power of qfst is incomparable to that of their probabilistic counterpart. This we show by discussing a number of characteristic examples.

Samuel Lomonaco: University of Maryland Baltimore County, lomonaco@umbc.edu
Quantum Hidden Subgroup Algorithms

We discuss quantum hidden subgroup algorithms from the mathematical perspective with the objective of developing new quantum algorithms.

Poster Session 2

(we supply a 48x32 inch foam-core backing for each poster)

Tuesday January 15 2002: 15:30
Mezzanine

Patrick Hayden: Caltech, patrick@cs.caltech.edu
Distributed Compression of Quantum Information

We consider the task of communicating correlated quantum information from two or more senders to a single receiver. This problem incorporates and generalizes many basic scenarios in quantum information theory, from cloning and quantum error correction to the recently-discovered phenomenon of nonlocality without entanglement. We determine the achievable rate region for some important special cases, give bounds in others, and shake our heads at some curious representatives of the general case. (Joint work with Andrew Doherty.)

Miroljub Dugic: department of physics, faculty of science dugic@knez.uis.kg.ac.yu, web site
energy consumption in quantum information processing

We point out and discuss non-necessity of energy consumption in quantum information processing. With this, we believe, we point out a "border line" between the classical and quantum information processing.

Andrew Childs: MIT Center for Theoretical Physics, amchilds@mit.edu, web site
Secure assisted quantum computation

Suppose Alice wants to perform some computation that could be done quickly on a quantum computer, but she cannot do universal quantum computation. Bob can do universal quantum computation and claims he is willing to help, but Alice wants to be sure that Bob cannot learn her input, the result of her calculation, or even the function she is trying to compute. We describe an efficient protocol by which Bob can help Alice perform the computation, but there is no way for him to learn anything about it. Furthermore, we show how Alice can efficiently detect whether Bob is honestly helping her or if he is introducing errors.

Andre Methot: Universite de Montreal, methotan@iro.umontreal.ca, web site
Interaction-Free Measurement Applied To QuantumComputation: A New ``cnot'' Gate.

In this paper, we propose a new direction of research for the realization of the quantum controlled-not gate based on a technique called ``interaction-free measurement'', where qubits are two-level atoms (or ions) and information is mediated from one qubit to another by lasers in superpositions of $\pi$ and $2\pi$ pulses. We investigate the advantages and limitations of such a gate and discuss possible applicability.

Vwani Roychowdhury: UCLA, vwani@ee.ucla.edu
Recovery, Super-Catalysis, and classification of entanglement in Bi-Partite Pure-state Transformations

We present a comprehensive set of results pertaining to properties of bipartite and pure-state entanglement transformations in the finite-copy regime. For example, we show for the first time that the entanglement lost in transformations of comparable bipartite pure states can be almost always recovered by performing a joint transformation with an auxiliary entangled state of dimension 2X2. Similarly, we show that transformations between incomparable states, can be not only enabled by using auxiliary states (catalysis), but that lost entanglement can be simultaneously recovered (leading to supercatalysis). A final set of results show how the notions of comparability and incomparability of states can be generalized and extended to the case where a finite number of copies of states are available. (Joint work with Somshubhro Bandyopadhyay)

John Langford: Carnegie Mellon, jcl@cs.cmu.edu, web site
Generic Quantum Block Compression

I will show how any (optimal) classical block compression algorithm can be compiled into an (optimal) quantum block compression algorithm.

Ujjwal Sen: Institute for Scientific Interchange (ISI) Foundation, ujjwal@isiosf.isi.it, ujjwalsen@yahoo.co.in
Is it possible to clone using an arbitrary blank state?

Quantum information cannot be cloned. But although exact cloning is not possible, one can approximately clone an arbitrary input state. In this scheme a fixed state is taken as the blank state depending on which, the cloning machine is constructed. Now the quality of the clones could be badly affected if the blank state gets changed to an unknown state, say by some environment-induced decoherence. We show that by suitably constraining the unitary operator, it is possible to keep the clones intact, even in this changed scenario where one has an arbitrary blank state. We show that this effect holds for both deterministic as well as probalilistic exact cloning. We hope that this work would help in a possible experimental implementation of quantum cloning.

Ashwin Nayak: Computer Science Department, and Institute for Quantum Information California Institute of Technology
On communication over an entanglement-assisted quantum channel

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as ``quantum teleportation'' and ``superdense coding.'' The problem of characterising the power of prior entanglement has puzzled many researchers. We revisit the problem of transmitting classical bits over a noiseless entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. This gives an alternative proof of optimality of the superdense coding scheme of Bennett and Wiesner, and improves over the previous lower bound due to Cleve, van Dam, Nielsen, and Tapp. All known lower bounds in this setting are based on sophisticated information-theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique. (Joint work with Julia Salzman, Mathematics Department, Princeton University)

Arnolds Kikusts: Institute of Mathematics and Computer Science, sd70053@lanet.lv
On the class of languages recognizable by quantum automata

It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a conditions which are necessary and sufficient. For arbitrary regular language, we only know that these conditions are necessary but do not know if all languages satisfying them can be recognized by a QFA. We also determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recohnized by a QFA with probability at most 0.7726.. .

Stéphane Beauregard: Université de Montréal, beaurest@iro.umontreal.ca
How few qubits do we need?

While it is known that Shor's algorithm requires polynomial time, the minimal number of qubits it needs is not known. By putting together several tricks, we provide circuits for factorization on a quantum computer using few qubits. So far, to factor an n-bit number, the best circuits we have are one with 2n+3 qubits and O(n3 log n) elementary quantum gates, and one with 3n+2 qubits and O(n3) gates.

Maxim Kravtsev
Probabilistic reversible and quantum automata

Joint work with Marats Golovkins (University of Latvia) We offer new notion of probabilistic automata namely probabilistic reversible automata (PRA). We prove that this model is stronger than the deterministic reversible automaton model, and show that it preserves similar restrictions as quantum automata in one-way case but acts differently in one-and-half and two-way case. Basic results about PRA are the following. Forbidden construction for one-way PRA is shown. Recognition of languages' conjunction and disjunction is shown. Language (a|b)*a is considered and proved impossible to be recognized by one-way PRA, but possible by one-and-half PRA.

Robert Raussendorf
Computational model underlying the one-way quantum computer

Authors: R. Raussendorf and H. J. Briegel
We demonstrated in [1] that a class of highly entangled multi-particle states, the cluster states [2], can serve as one-way quantum computers. The one-way quantum computer is a scheme of universal quantum computation that consists only of one-qubit measurements on the resource quantum state. The one-way quantum computer has the property that any quantum logic network can be simulated on it. Conversely, not all ways of information processing that are possible with the one-way quantum computer can be explained within the network model. For example, all circuits in the Clifford group -- which contains for example many coding circuits -- can be performed in a single time-step. On the other hand, the network realization requires a number of time steps logarithmic in the number of logical qubits. Thus, the description of the one-way quantum computer in network terms is not adequate in every respect. A computational model [3] underlying the one-way quantum computer is presented. [1] R. Raussendorf and H. J. Briegel, A one-way quantum computer. Phys. Rev. Lett. 86, 5188 (2001). [2] H. J. Briegel and R. Raussendorf, Persistent Entanglement in arrays of interacting particles. Phys. Rev. Lett. 86, 910 (2001). [3] R. Raussendorf and H. J. Briegel, Computational model underlying the one-way quantum computer. quant-ph/0108067 (2001).

Aija Berzina
Ambainis-Freivalds' Algorithm for Measure-Once Automata

An algorithm given by Ambainis and Freivalds constructs a quantum finite automaton (QFA) with O(log p) states recognizing the language L_p={a^i|i is divisible by p} with probability 1-epsilon, for any epsilon > 0 and arbitrary prime p. However, the Ambainis-Freivalds algoritm is tailored to constructing a measure-many QFA, which cannot be implemented on existing quantum computers. In this paper we modify the algorithm to construct a measure-once QFA and give examples of parameters for this automaton. We show for the language L_p that a measure-once QFA can be twice as space efficient as measure-many QFA's.

Mary Beth Ruskai
Entnaglement Breaking Channels

Three classes of stochastic maps, or channels, are considered, (1) those of the so-called Holevo form $\Phi(\rho) = \sum_k R_k ~ \tr \, F_k \rho$ where each $R_k$ is a denisty matrix and the $\{F_k\}$ form a POVM, (2) those for which $(I \ot \Phi)(\Gamma)$ is always separable, and (3) those which satisfy a certain sign change condition which,in the case of qubits, is equivalent to the condition that composition with the transpose is also completely positive. We show that, in the case of qubits, these three classes of channels coincide and that any channel of this form can be written as a convex combination of CQ and point channels. In particular, we prove that any qubit channel whose image lies within a plane is in this class and, hence, entanglement breaking. The relations between these classes of maps is discussed for general d-bit channels.

Igor Bargatin
Information-theoretic Approach to Adaptive Dyne Measurements

We propose a new approach to adaptive "dyne" measurements of quantum optical fields, which is based on maximization of the mutual information between the photocurrent record and the measured variable. Depending on the nature of the measured ensemble of field states, the scheme is shown to selectively perform phase, quadrature, amplitude or other, more general measurements. In the case of phase measurements, the scheme apparently always extract more or as much information about the phase as Wiseman�s scheme [Phys. Rev. A 56 944 (1997)].
Return to Program or QIP2002 homepage