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
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.
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.
References for the talk
All the papers below are available at
http://www.ee.technion.ac.il/Sites/People/YoninaEldar/.
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:
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.
The lecture slides
quant-ph/0212165
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.
Refrences for this talk are the following papers:
quant-ph/0211185
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.
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.
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.
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.
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.
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.