<p>Circuits made out of general linear operators are $PP$-complete. See the <a href="http://arxiv.org/abs/quant-ph/0412187">PostBQP paper</a> by Scott Aaronson  or <a href="http://arxiv.org/abs/quant-ph/0611050">Schuch's paper</a> on the computational power of PEPS and tensor network contraction.</p>

CC BY-SA 3.0
2011-07-28T15:11:28.217Z
2011-07-28T17:18:28.097Z
2011-07-28T17:18:28.097Z
Martin Schwarz
<p>In a pure mathematical sense, you could in principle create models of computation using any sort of recursively composable structure, so long as you can describe how it represents a transformation of suitably represented input data to output data. But in an applied mathematical sense &mdash; or more accurately, in an actual <em>scientific</em> sense &mdash; there is a question of whether such models of computation correspond to (<em>i.e.</em>&nbsp;models well) anything which is observed in practise (<em>e.g.</em>&nbsp;perhaps because we observe it in machines constructed to do the computations). We're confident that permutation matrices and stochastic matrices, composed by products on local systems, represents a feasible model of computation for transforming probability distributions. It is also accepted in principle that unitary transformations on unit-2-norm wave functions (composed in a similar way) is not unreasonable as a model of computation; showing that it is actually feasible is widely accepted as a (very challenging!) engineering problem.</p>

<p>Both of these models of computation can be subsumed into the formalism of CPTP super-operators (which map linear operators to other linear operators, in a way which preserves the trace, and <strong>robustly</strong> maps positive-semidefinite operators to other such operators), which in certain respects is a better way of describing quantum computation than by unitary transformations or projectors alone.</p>

<p>Whether there are strictly more general (in the sense of more powerful, and using the same sort of representation of the input and output data) models of computation than unitary transformations or CPTP superoperators is in essence a question of theoretical physics.</p>

<p>So the answer is "maybe &mdash; but we don't know yet, and don't have convincing reasons to believe in any particular one". </p>

CC BY-SA 3.0
2011-07-28T15:31:37.800Z
2011-07-28T17:09:45.733Z
2011-07-28T17:09:45.733Z
Niel de Beaudrap
<p>Just out of curiosity, if the classical computation is about permutation matrices and quantum computing is about unitary matrices (of which the permutation matrices are a subgroup), then will there be any computation paradigm beyond unitary matrices?</p>

CC BY-SA 3.0
2011-07-28T22:36:40.323Z
similar question: http://cstheory.stackexchange.com/q/861/135
Marcos Villagra
<quantum-computing><philosophy>
Computation beyond unitary matrices
huyichen
# Computation beyond unitary matrices

(Asked by: username_0 on 2011-07-28)

Just out of curiosity, if the classical computation is about permutation matrices and quantum computing is about unitary matrices (of which the permutation matrices are a subgroup), then will there be any computation paradigm beyond unitary matrices?

**Tags:** quantum-computing, philosophy

> **Comments:**
> **username_1**: similar question: http://cstheory.stackexchange.com/q/861/135  

---

## 2 answers

### Answer by username_2 on 2011-07-28. Score: 17

Circuits made out of general linear operators are $PP$-complete. See the [PostBQP paper](http://arxiv.org/abs/quant-ph/0412187) by Scott Aaronson or [Schuch's paper](http://arxiv.org/abs/quant-ph/0611050) on the computational power of PEPS and tensor network contraction.


---

### Answer by username_3 on 2011-07-28. Score: 16

In a pure mathematical sense, you could in principle create models of computation using any sort of recursively composable structure, so long as you can describe how it represents a transformation of suitably represented input data to output data. But in an applied mathematical sense — or more accurately, in an actual *scientific* sense — there is a question of whether such models of computation correspond to (*i.e.* models well) anything which is observed in practise (*e.g.* perhaps because we observe it in machines constructed to do the computations). We're confident that permutation matrices and stochastic matrices, composed by products on local systems, represents a feasible model of computation for transforming probability distributions. It is also accepted in principle that unitary transformations on unit-2-norm wave functions (composed in a similar way) is not unreasonable as a model of computation; showing that it is actually feasible is widely accepted as a (very challenging!) engineering problem.

Both of these models of computation can be subsumed into the formalism of CPTP super-operators (which map linear operators to other linear operators, in a way which preserves the trace, and **robustly** maps positive-semidefinite operators to other such operators), which in certain respects is a better way of describing quantum computation than by unitary transformations or projectors alone.

Whether there are strictly more general (in the sense of more powerful, and using the same sort of representation of the input and output data) models of computation than unitary transformations or CPTP superoperators is in essence a question of theoretical physics.

So the answer is "maybe — but we don't know yet, and don't have convincing reasons to believe in any particular one".


---

