Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-147 | 24th September 2016 20:41

The weakness of CTC qubits and the power of approximate counting

RSS-Feed




Revision #1
Authors: Ryan O'Donnell, A. C. Cem Say
Accepted on: 24th September 2016 20:41
Downloads: 156
Keywords: 


Abstract:

We 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.



Changes to previous version:

Slightly updated bibliographic discussion of postselection.


Paper:

TR16-147 | 19th September 2016 19:06

The weakness of CTC qubits and the power of approximate counting





TR16-147
Authors: Ryan O'Donnell, A. C. Cem Say
Publication: 19th September 2016 19:06
Downloads: 223
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint