Qubit 2003, Opening Speech

Noga Alon, Tel Aviv University

Quantum Information Theory and Quantum Computing form a challenging interdisciplinary scientific area which, besides its spectacular potential applications, is a source of fascinating problems. After some very brief comments on the area, I will illustrate this fact by a short description of a joint work with Laci Lovasz on unextentible product bases. This work was motivated by a problem in quantum information theory, and combines combinatorial and algebraic tools with number theoretic techniques.

The relevant paper can be found at: N. Alon and L. Lovasz, Unextendible product bases, J. Combinatorial Theory, Ser. A 95 (2001), 169-179, or at: http://www.math.tau.ac.il/~nogaa/PDFS/publications.html

What is actually teleported?

Asher Peres, Department of Physics, Technion

There are no ``unknown quantum states.'' It's a contradiction in terms. Moreover, Alice and Bob are only inanimate objects. They know nothing. What is teleported instantaneously from one system (Alice) to another system (Bob) is the preparer's knowledge of the state of a particular qubit in these systems. The operation necessitates dual classical and quantum channels. Other examples of dual transmission, including ``unspeakable information,'' will be presented and discussed. This article also includes a narrative of how I remember that quantum teleportation was conceived.

Quantum Detection: A Semidefinite Proramming Approach

Yonina C. Eldar, Technion

We consider the problem of designing an optimal quantum detector to minimize the probability of a detection error when distinguishing between a collection of quantum states, represented by a set of density operators. We show that the design of the optimal detector can be formulated as a semidefinite programming problem. Based on this formulation, we derive a set of necessary and sufficient conditions for an optimal quantum measurement. We then show that the optimal measurement can be found by solving a standard (convex) semidefinite program. By exploiting the many well-known algorithms for solving semidefinite programs, which are guaranteed to converge to the global optimum, the optimal measurement can be computed very efficiently in polynomial time within any desired accuracy.

Using the semidefinite programming formulation, we develop several properties of the optimal measurement. In particular, we show that the rank of each optimal measurement operator is no larger than the rank of the corresponding density operator. We also show that for linearly independent mixed states, the optimal measurement is a von Neumann measurement and not a more general POVM.

We then develop a sufficient condition for the least-squares measurement to minimize the probability of a detection error when distinguishing between a collection of mixed quantum states. Using this condition we derive an the optimal measurement for state sets with a broad class of symmetries.

References for the talk

All the papers below are available at
http://www.ee.technion.ac.il/Sites/People/YoninaEldar/.
  1. Y. C. Eldar and G. D. Forney, Jr., ``On Quantum Detection and the Square-Root Measurement,'' IEEE Trans. Inform. Theory, vol. 47, pp. 858-872, Mar. 2001.
  2. Y. C. Eldar, A. Megretski, and G. C. Verghese, ``Designing Optimal Quantum Detectors Via Semidefinite Programming,'' IEEE Trans. Inform. Theory, vol. 49, pp. 1017-1012, Apr. 2003.
  3. Y. C. Eldar, A. Megretski, and G. C. Verghese, ``Optimal Detection of Symmetric Mixed Quantum States,'' quant-ph/0211111.
  4. Y. C. Eldar, "Von Neumann Measurement is Optimal for Detecting Linearly Independent Mixed Quantum States," quant-ph/0304077.
  5. Y. C. Eldar, ``A Semidefinite Programming Approach to Optimal Unambiguous Discrimination of Quantum States," IEEE Trans. Inform. Theory, vol. 49, pp. 446-456, Feb. 2003.
  6. Y. C. Eldar, ``Mixed Quantum State Detection with Inconclusive Results,'' Phys. Rev. A., vol. 67, pp. 042309:1-042309:14, Apr. 2003.
  7. Y. C. Eldar and H. Bolcskei,``Geometrically Uniform Frames,'' IEEE Trans. Inform. Theory, vol. 49, pp. 993-1006, Apr. 2003.

Quantum Computation without Entanglement

Dan Kenigsberg, the Technion

It is generally believed that entanglement is essential for quantum computing. We present here a few simple examples in which quantum computing without entanglement is better than anything classically achievable, in terms of the reliability of the outcome after a fixed number of oracle calls.

Using a separable (that is, unentangled) n-qubit state, we show that the Deutsch-Jozsa problem and the Simon problem can be solved more reliably by a quantum computer than by the best possible classical algorithm, even probabilistic.

We conclude that:

  1. entanglement is not essential for quantum computing; and
  2. the advantage of the quantum algorithm over classical algorithms exists even when the quantum state contains an arbitrarily small amount of information --- that is, even when the state is arbitrarily close to being totally mixed.
Here are the
slides for the lecture.

Some Insights of Computational Complexity Theory

Avi Wigderson; IAS, Princeton & Hebrew University, Jerusalem

Computational complexity theory has been one of the most exciting fields of scientific research over the last few decades. This research studies the power of feasible computation, and is guided by a few clear and focused questions, deeply motivated on scientific, practical and philosophical grounds, like the P vs NP problem, and the questions on the power of randomized and quantum computation.

While these problems are far from resolved, Complexity Theory was able to offer fresh rigorous definitions to some central notions which naturally (or less so) arise from these questions, and unveil many rich and beautiful connections between them.

In this general survey, I would like to probe some of the unique features and insights of the complexity theory viewpoint. This will be done by considering how (and why) notions which intrigued people for centuries or even millenia (like Knowledge, Randomness, Cryptography, Learning, Proof, and naturally, Computation), revealnew dimensions, and are suprisingly linked together, when viewed from our special Computational Complexity glasses.

Quntum property testing

Ilan Newman, University of Haifa

A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x is in L and x has large Hamming distance from all y in L. We define a similar notion of quantum property testing and show that there exist languages with quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.

The lecture slides

Asymptotic Bounds on Parameters of Quantum Codes

Simon Litsyn, Tel Aviv University

We discuss upper and lower bounds on parameters of quantum codes. Upper bounds are based on analysis of Shor-Laflamme enumerators and linear programming (we will describe results of Gottesman, Rains and Ashikhmin-Litsyn). For lower bounds we explain the Calderbank-Shor non-constructive bound and, a worse, but constructive bound due to Ashikhmin-Litsyn-Tsfasman, based on algebraic geometrical ideas.

Quantum Error Correction in the Zeno regime

Noam Erez, Tel Aviv University

We describe an error correction protocol which encodes n logical qubits in n+6 physical qubits and works in the Zeno regime (very frequent measurements/corrections). It displays properties intermediate between error correction codes and dynamical error correction. It also has a simple interpretation in terms of pre- and post-selection on the extra physical qubits.

Qubit versus Bit for Measuring an Integral of a Classical Field

Lev Vaidman, Tel Aviv University

Methods for measuring an integral of a classical field via local interaction of classical bits or local interaction of qubits passing through the field one at a time are analyzed. It is argued that an exponentially better precision can be achieved with qubits instead of bits.

quant-ph/0212165

Elliptic Rydberg States as Direction Indicators

Netanel H. Lindner, The Technion

The orientation in space of a Cartesian coordinate system can be indicated by the two vectorial constants of motion of a classical Keplerian orbit: the angular momentum and the Laplace-Runge-Lenz vector. In the quantum domain, the states of a hydrogen atom that mimic classical elliptic orbits are the coherent states of the SO(4) rotation group. They have minimal dispersions of these vectors and can be used as direction indicators.

Does Public Key Cryptography Exist?

Oleg Izmerly, the Technion

We discuss the existence of secure public key encryption (PKE). Such type of encryption has critical role in modern cryptography.

Ajtai-Dwork and Regev public key cryptosystems potentially are the best candidates for public key encryption secure even in a quantum environment. In our work we present a ciphertext attack (CCA) on these cryptosystems, and show that they are dramatically weak against such type of attack.

Also the possibility of resisting PKE against CCA is discussed.

Here are the slides for the lecture.

Facing the challenges of solid state implementation of quantum computation

Ehoud Pazy, Ben Gurion University

Solid-state implementation of quantum computation promises scalability to a large number of qubits (two level systems) and benefits from recent advances in fabrication and characterization of quantum dots. Quantum dots due to their discrete density of states are often refereed to as "artificial atoms". It therefore seems natural to try to incorporate into quantum dot implementation schemes, some of the schemes devised in the field of quantum optics, in which admirable theoretical and experimental progress has been made. As opposed to atoms and ions in the quantum optics schemes, quantum dots are embedded into an underlaying bulk material, which induces fundamental quantum mechanical limitations on the solid state system. These limitations will be discussed and ways to circumvent their effect shall be described.

Refrences for this talk are the following papers:

  1. Title: Spin-based optical quantum gates via Pauli blocking in semiconductor quantum dots Europhys. Lett. 62 2003 p:175 also cond-mat/0109337
  2. Title: Spin-based all-optical quantum computation with quantum dots: understanding and suppressing decoherence quant-ph/0304044

Quantum Gates on Hybrid Qudits

Jamil Daboul, Ben Gurion University

We introduce quantum hybrid gates that act on qudits of different dimensions. In particular, we develop two representative two-qudit hybrid gates (SUM and SWAP) and many-qudit hybrid Toffoli and Fredkin gates. We apply the hybrid SUM gate to generating entanglement, and find that operator entanglement of the SUM gate is equal to the entanglement generated by it for certain initial states. We also show that the hybrid SUM gate acts as an automorphism on the Pauli group for two qudits of different dimensions under certain conditions. Finally, we describe a physical realization of these hybrid gates for spin systems.

quant-ph/0211185

Quantum Search of Spatial Regions

S. Aaronson and A. Ambainis, University of California, Berkeley

Can Grover's quantum search algorithm speed up search of a physical region - for example a 2-D grid of size sqrt(n) by sqrt(n)? The problem is that sqrt(n) time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time O(sqrt(n)) for d at least 3, or O(sqrt(n)polylog(n)) for d=2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fun damental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks; a generalized algorithm th at works for any graph with good expansion properties, not just hypercubes; and relationships among several notions of `locality' for unitary matrices acting on graphs. As an application of our results, we give an O(sqrt(n))-qubit communication protocol for the disjointness problem, which improves an upper bound of Høyer and de Wolf and matches a lower bound of Razborov.