Assistant Professor
Joined School 2008
BS (Stanford),
PhD (Berkeley)
| breic@uwaterloo.ca | |
| Web | http://www.cs.uwaterloo.ca/~breic/ |
| Voice | 519-888-4567 x38616 |
| Fax | 519-885-1208 |
|
| Ben R.W. Reichardt
Assistant Professor Joined School 2008 BS (Stanford),
|
While quantum computers do not yet exist, polynomial-time quantum computation is the best answer we have to the fundamental question of what can possibly be computed using polynomial physical resources. Professor Reichardt is interested in using ideas from computer science and physics to improve our understanding of quantum control and fault tolerance, and of quantum algorithms.
The major difficulty in building a quantum computer is overcoming noise. Fault-tolerance schemes allow for computing reliably in the presence of noise, but are not yet practical. Professor Reichardt has improved the tolerable noise rate of quantum fault-tolerance schemes and has developed new methods for proving that such schemes can work well.
Professor Reichardt, together with Robert Spalek, found a new technique for developing quantum algorithms based on the classical linear algebraic model of computation known as “span programs”. Span-program-based algorithms have been particularly useful for evaluating read-once formulas, and in fact the quantum complexity of this problem is better understood now than the classical complexity.
B. W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. Proc. 50th IEEE Foundations of Computer Science (FOCS), 2009, pages 544-551.
B. W. Reichardt and R. Spalek. Span-program-based quantum algorithm for evaluating formulas. Proceedings of the 40th ACM Symposium on Theory of Computing, pp. 103-112, 2008.
B. W. Reichardt. Proof of the Double Bubble Conjecture in Rn. Journal of Geometric Analysis, 18(1):172-191, 2008.
A. Ambainis, A. M. Childs, B. W. Reichardt, R. Spalek, and S. Zhang. Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer. Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pp. 363-372, 2007.
B. W. Reichardt. Postselection threshold against biased noise. Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, pp. 420-428, 2006.
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-webmaster@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Monday, 20-Dec-2010 14:29:41 EST
