Prof. Amnon Ta-Shma

Phone: 054-2322706

School for Computer Science, Faculty of Exact Science


I am interested in computational complexity in general and quantum computation in particular. Among the results I have obtained in quantum complexity I would mention:

  1. Random access codes, (together with Ambainis, Nayak and Vazirani) where we defined  and studied the extent to which one can (or cannot) compactly encode classical information in quantum messages in a way that allows answering local queries.
  2. The first provable quantum coin tossing protocol (with Aharonov, Vazirani and Yao)
  3. Proving that QED is QSZK-complete (together with Ben-Aroya)
  4. Showing that Trevisan's extractor is quantum proof. This was the first proof for a short seed quantum extractor and it was later improved and simplified.
  5. Showing a BQL algorithm (approximately) inverting Hermitian matrices. This is the first problem that seems to be in BQL but not in BPL.


In general, I am interested in

  • the power of quantum classes (recently, I looked at the power of QIP(2)),
  • in quantum-proof extractors, and,
  • in the power of BQL, the space bounded quantum class.
Tel Aviv University makes every effort to respect copyright. If you own copyright to the content contained
here and / or the use of such content is in your opinion infringing, Contact us as soon as possible >>