__
Revision #1 to TR16-147 | 24th September 2016 20:41
__
#### The weakness of CTC qubits and the power of approximate counting

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

__
TR16-147 | 19th September 2016 19:06
__

#### The weakness of CTC qubits and the power of approximate counting

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