A basic question when defining a formal model of quantum computation is
whether or not to allow the model to perform quantum measurements
throughout its computation. In the time-bounded setting, it is well-known that
restricting a quantum computer to perform a single measurement only at the
end of its computation does not decrease its computational power. However,
in the space-bounded setting, it has remained an open question whether
allowing intermediate measurements affects the power of a quantum
computer.
In this talk, I will present a recent joint work with Bill Fefferman, in which we
have shown that eliminating intermediate measurements does not affect the
power of space-bounded quantum computation. I will also discuss a recent
paper in which I exhibited the first known problem that may be solved by a
deterministic Turing machine in logarithmic-space and polynomial-time, but
cannot be solved by a quantum Turing machine in sublogarithmic-space and
polynomial-time. Lastly, I will present matching upper and lower bounds on
the amount of space needed for a quantum computer to solve certain group
word problems.
---------------
Zack Remscrim is a Postdoctoral Associate in the math department at MIT. He received his PhD from MIT, where he was advised by Professor Michael Sipser. His research interests include quantum complexity theory, pseudorandomness, and circuit complexity.
============
For the zoom link, email Diana Morgan (morgandf@anl.gov), Kelly Foster (foster5@illinois.edu), or Becky McDuffee (mcduffbe@illinois.edu) .
