ECCC-Report TR16-147https://eccc.weizmann.ac.il/report/2016/147Comments and Revisions published for TR16-147en-usSat, 24 Sep 2016 20:41:25 +0300
Revision 1
| The weakness of CTC qubits and the power of approximate counting |
Ryan O'Donnell,
A. C. Cem Say
https://eccc.weizmann.ac.il/report/2016/147#revision1We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of problems that
can be efficiently solved with a nonadaptive oracle for the Approximate Counting problem. Our
second result is concerned with the computational power conferred by CTCs; or equivalently,
the computational complexity of finding stationary distributions for quantum channels. We
show that any poly(n)-time quantum computation using a CTC of O(log n) qubits may as well
just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find
a stationary distribution for a poly(n)-dimensional quantum channel in PP.
Sat, 24 Sep 2016 20:41:25 +0300https://eccc.weizmann.ac.il/report/2016/147#revision1
Paper TR16-147
| The weakness of CTC qubits and the power of approximate counting |
Ryan O'Donnell,
A. C. Cem Say
https://eccc.weizmann.ac.il/report/2016/147We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of problems that
can be efficiently solved with a nonadaptive oracle for the Approximate Counting problem. Our
second result is concerned with the computational power conferred by CTCs; or equivalently,
the computational complexity of finding stationary distributions for quantum channels. We
show that any poly(n)-time quantum computation using a CTC of O(log n) qubits may as well
just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find
a stationary distribution for a poly(n)-dimensional quantum channel in PP.
Mon, 19 Sep 2016 19:06:46 +0300https://eccc.weizmann.ac.il/report/2016/147