The Space-Time Cost of Purifying Quantum Computations
Innovations in Theoretical Computer Science(2024)
摘要
General quantum computation consists of unitary operations and also
measurements. It is well known that intermediate quantum measurements can be
deferred to the end of the computation, resulting in an equivalent purely
unitary computation. While time efficient, this transformation blows up the
space to linear in the running time, which could be super-polynomial for
low-space algorithms. Fefferman and Remscrim (STOC'21) and Girish, Raz and Zhan
(ICALP'21) show different transformations which are space efficient, but blow
up the running time by a factor that is exponential in the space. This leaves
the case of algorithms with small-but-super-logarithmic space as incurring a
large blowup in either time or space complexity. We show that such a blowup is
likely inherent, demonstrating that any "black-box" transformation which
removes intermediate measurements must significantly blow up either space or
time.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要