On exact counting and quasi-quantum complexity
arXiv:1509.07789
Abstract
We present characterisations of "exact" gap-definable classes, in terms of indeterministic models of computation which slightly modify the standard model of quantum computation. This follows on work of Aaronson [arXiv:quant-ph/0412187], who shows that the counting class PP can be characterised in terms of bounded-error "quantum" algorithms which use invertible (and possibly non-unitary) transformations, or postselections on events of non-zero probability. Our work considers similar modifications of the quantum computational model, but in the setting of exact algorithms, and algorithms with zero error and constant success probability. We show that the gap-definable counting classes [J. Comput. Syst. Sci. 48 (1994), p.116] which bound exact and zero-error quantum algorithms can be characterised in terms of "quantum-like" algorithms involving nonunitary gates, and that postselection and nonunitarity have equivalent power for exact quantum computation only if these classes collapse.
22 pages, 6 figures. Revised draft of a submission to TQC 2015
References in corpus (9)
- Improving zero-error classical communication with entanglement
- No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems
- Entanglement-assisted zero-error capacity is upper bounded by the Lovasz theta function
- Ground states of unfrustrated spin Hamiltonians satisfy an area law
- The Need for Structure in Quantum Speedups
- Exact quantum query complexity of EXACT and THRESHOLD
- On computation with 'probabilities' modulo k
- Exact quantum Fourier transforms and discrete logarithm algorithms
- Quantum Zero-error Capacity