<p><em>I complete here Peter’s answer with a characterization of physical maps as CPTP maps.</em> </p>

<p>As you know, if the system is isolated, the only operations you can implement are the unitary operations. But, as you noticed, if you use an ancillary subsystem and throw a subsystem away, you can implement some other operations. 
The set of physical operations are the <a href="https://en.wikipedia.org/wiki/Completely_positive_map" rel="noreferrer">completely positive</a> trace preserving maps. (Following most of the literature, I’ll call them CPTP maps), and <a href="https://en.wikipedia.org/wiki/Stinespring_factorization_theorem" rel="noreferrer">Stinespring’s dilation theorem</a> indeed ensures that any CPTP map can be written as the partial trace of a unitary acting on a larger Hilbert space.</p>

<p>Since we are looking at non isolated subsystem, its quantum state has to be described by a density matrix $ρ$. In full generality, a density matrix has to be positive ($ρ≥0$) and having a unit trace ($\mathrm{Tr}ρ=1$). Let suppose we have a generic physical map $\mathcal{E}:ρ↦\mathcal{E}(ρ)$. To be physical $\mathcal{E}(ρ)$ needs to be a physical state for any input state $ρ$, that is, we should have $∀ρ:ρ≥0$, $\mathcal{E}(ρ)≥0$ and $\mathrm{Tr}\mathcal{E}(ρ)=\mathrm{Tr}ρ$. In other words, $\mathcal{E}$ has to be positive and trace preserving.</p>

<p>However, it is not enough. For example, the transpose $\mathcal{T}$, is a positive trace preserving map, which is unphysical. The idea is the one behind the <a href="https://en.wikipedia.org/wiki/Peres%E2%80%93Horodecki_criterion" rel="noreferrer">Peres-Hordecki criterion</a>: suppose you have a channel performing $\mathcal{T}$ on the thystem $A$. You can add another system $B$ of the same dimension, where you perform the identity $\mathcal{I}$ <em>i.e.</em> wher you don’t do anything. The global map on $AB$ is then $\mathcal{T}_A⊗\mathcal{I}_B$, which is not positive any more: some linear algebra shows $\mathcal{T}_A⊗\mathcal{I}_B(Φ_{AB})$ has $d(d-1)/2$ negative eignevalues, where $Φ_{AB}$ is a maximally entangled state. </p>

<p>For a map $\mathcal E$ to be physical, any extension of the form $\mathcal E⊗\mathcal I$ has therefore to be positive. This is the definition of complete positivity. The Stinespring dilation theorem then shows that this necessary condition is sufficient, since it gives a recipe to implement any CPTP map with an ancillary subsystem and and a unitary.</p>

CC BY-SA 3.0
2016-07-04T15:47:22.377Z
Thanks, that is very informative! I've been struggling to find an intuitive explanation of this. Is there some literature from which you draw the counter-example for the requirement of the map to be completely positive?
Tim Atkinson
CC BY-SA 3.0
2016-07-04T15:51:41.537Z
Another interesting question is whether it is impossible for *some* map to not be a CPTP (and therefore not fall under Stinespring's dilation theorem) but still be physically realizable using an ancillary subsystem?
Tim Atkinson
CC BY-SA 3.0
2016-07-04T17:14:06.083Z
I found this example through my own struggle with the concept of CPTP maps and partial transpose years ago . The counter example directly comes from the Peres-Horodecki criterion.
Frédéric Grosshans
CC BY-SA 3.0
2016-07-04T17:19:42.503Z
If a map is positive but not CP, one can construct an entangled state which would transform into a nonpositive  (hence non physical) state. Therefore this map is not physically realisable.  Such maps are used as entanglement witnesses and are useful for theoreticians, but there really is no hope to create them experimentally.
Frédéric Grosshans
CC BY-SA 3.0
2016-07-05T08:30:14.493Z
That makes sense. Thank you for your help! Is it the case that a map that is not trace-preserving has no equivalent quantum circuit using ancillary either?
Tim Atkinson
CC BY-SA 3.0
2016-07-05T12:20:29.763Z
“Trace preserving” is the technical term for “probability preserving”. You cannot have trace increasing maps, otherwise you could have result happening with probability greater than 100%, which makes no sense. Trace decreasing maps are used sometimes to describe “part of maps” or maps which have a finite probability of uninteresting events (often failures),similarly to the use of subnormal density matrices e.g. $\mathrm{Tr}\mathcal E(ρ)=.83$  means that the map has a probability to fail of 17%. It can also be described by a TP map, where the fail event is included in the output Hilbert space
Frédéric Grosshans
CC BY-SA 3.0
2016-07-05T15:37:03.277Z
This rabbit hole just goes deeper and deeper aha! If I had some CP *trace-reducing* map, is it implicit that I can describe this by a *CP*TP map ?

Sorry for all of the questions, each answer you give just raises more!
Tim Atkinson
CC BY-SA 3.0
2016-07-06T09:41:14.570Z
Yes. If $\mathcal E$ is a CP trace decreasing map, it can be described by the CPTP map $\mathcal E'$ defined as follows (among many possibilityes). Let $p≝\mathrm{Tr}\mathcal E(ρ)$. With probabililty $p$, $\mathcal E'(ρ)=0⊗\mathcal E(ρ)/p$ , with probability $1-p$, $\mathcal E'(ρ)=1⊗σ$, where $σ$ is an arbitrary state. The first bit '0' or '1' can be seen as a flag telling the success or failure of this protocol.
Frédéric Grosshans
CC BY-SA 3.0
2016-07-06T10:07:42.507Z
Thankyou, you have provided a very in-depth description of the space I was looking to understand. It feels weird to choose someone else's answer over Peter Shor's but in this case it seems appropriate (not that his is in any way lacking) :)
Tim Atkinson
CC BY-SA 3.0
2016-07-22T19:08:36.850Z
I agree. Frédéric clearly put more effort into his answer, and it's more detailed, so it deserves the checkmark.
Peter Shor 
CC BY-SA 3.0
2016-07-04T13:34:45.423Z
2016-07-04T13:34:45.423Z
Frédéric Grosshans
<p>Look at <a href="http://www.theory.caltech.edu/%7Epreskill/ph219/index.html#lecture">John Preskill's Lecture Notes</a>; particularly Section 3.2.</p>

<p>As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, so you no longer necessarily have a pure state of your system.</p>

<p>For non-unitary quantum operations, if you assume that the environment doesn't remember anything, then the most general thing you can do is a unitary operation followed by throwing away some part of the system. </p>

<p>If you assume that the environment has memory, things get much more complicated. But note that here, your operations aren't consistent because the outcome of an operation will depend on what the input was the last time you performed the operation. I don't know if you want to include this class of operations. While they are important in physics, they aren't very useful for quantum computation. </p>

CC BY-SA 3.0
2016-07-01T09:06:42.077Z
Thanks! :) The lecture notes are very helpful. Is there a general method/algorithm for constructing a unitary operation from a non-unitary operation?
Tim Atkinson
CC BY-SA 3.0
2016-07-01T11:22:00.420Z
What you're asking for is an algorithm version of the Stinespring dilation theorem. I believe most proofs of this theorem can be turned into algorithms; however, offhand I don't know a good reference for this.
Peter Shor 
CC BY-SA 3.0
2016-07-01T11:49:46.667Z
Great, that's more than enough to give me a direction. Thank you for the help!
Tim Atkinson
CC BY-SA 3.0
2016-06-30T16:37:31.357Z
2016-06-30T17:24:08.997Z
2016-06-30T17:24:08.997Z
Peter Shor 
<p>Suppose we construct a non-unitary quantum system &alpha; in hilbert space. It entails that this system would have no direct parallel in quantum circuitry as it is a requirement that all quantum gates are unitary and therefore the function constructed from them is also unitary. But does this mean that we cannot practically implement &alpha;?</p>

<p>A potential parallel is found in the simulation of classical computations on a quantum computer, achieved by simulating an information-destroying NAND gate using an information-preserving Toffoli gate. If a non-unitary quantum system was such because it implemented a 'quantum NAND gate', it would be possible to redesign it as a unitary system using a Toffoli gate. It is not clear to me (and I cannot immediately find literature on this) if there are clearly defined bounds on what non-unitary operations can be simulated using unitary equivalents. </p>

<p>Is there a clearly defined subset of non-unitary quantum systems where &alpha; is practically implementable? Is it, perhaps, universal?</p>

CC BY-SA 3.0
2016-07-06T10:20:50.653Z
To conclude from Peter and Frederics' answers, any map that is completely positive and inclusively trace reducing (e.g. tr(E(p)) <= tr(p)) is physically realizable. If it is not completely positive it fails by counter example, if it is trace increasing then it is not a legitimate probabilistic circuit.
Tim Atkinson
<quantum-computing><quantum-information>
When is a non-unitary quantum system only theoretical?
Tim Atkinson
# When is a non-unitary quantum system only theoretical?

(Asked by: username_0 on 2016-06-30)

Suppose we construct a non-unitary quantum system α in hilbert space. It entails that this system would have no direct parallel in quantum circuitry as it is a requirement that all quantum gates are unitary and therefore the function constructed from them is also unitary. But does this mean that we cannot practically implement α?

A potential parallel is found in the simulation of classical computations on a quantum computer, achieved by simulating an information-destroying NAND gate using an information-preserving Toffoli gate. If a non-unitary quantum system was such because it implemented a 'quantum NAND gate', it would be possible to redesign it as a unitary system using a Toffoli gate. It is not clear to me (and I cannot immediately find literature on this) if there are clearly defined bounds on what non-unitary operations can be simulated using unitary equivalents.

Is there a clearly defined subset of non-unitary quantum systems where α is practically implementable? Is it, perhaps, universal?

**Tags:** quantum-computing, quantum-information
> **Comments:**
> **username_0**: To conclude from Peter and Frederics' answers, any map that is completely positive and inclusively trace reducing (e.g. tr(E(p)) <= tr(p)) is physically realizable. If it is not completely positive it fails by counter example, if it is trace increasing then it is not a legitimate probabilistic circuit.  

---

## 2 answers

### Answer by username_1 on 2016-07-04. Score: 5 | Accepted answer

*I complete here Peter’s answer with a characterization of physical maps as CPTP maps.*

As you know, if the system is isolated, the only operations you can implement are the unitary operations. But, as you noticed, if you use an ancillary subsystem and throw a subsystem away, you can implement some other operations.
The set of physical operations are the [completely positive](https://en.wikipedia.org/wiki/Completely_positive_map) trace preserving maps. (Following most of the literature, I’ll call them CPTP maps), and [Stinespring’s dilation theorem](https://en.wikipedia.org/wiki/Stinespring_factorization_theorem) indeed ensures that any CPTP map can be written as the partial trace of a unitary acting on a larger Hilbert space.

Since we are looking at non isolated subsystem, its quantum state has to be described by a density matrix $ρ$. In full generality, a density matrix has to be positive ($ρ≥0$) and having a unit trace ($\mathrm{Tr}ρ=1$). Let suppose we have a generic physical map $\mathcal{E}:ρ↦\mathcal{E}(ρ)$. To be physical $\mathcal{E}(ρ)$ needs to be a physical state for any input state $ρ$, that is, we should have $∀ρ:ρ≥0$, $\mathcal{E}(ρ)≥0$ and $\mathrm{Tr}\mathcal{E}(ρ)=\mathrm{Tr}ρ$. In other words, $\mathcal{E}$ has to be positive and trace preserving.

However, it is not enough. For example, the transpose $\mathcal{T}$, is a positive trace preserving map, which is unphysical. The idea is the one behind the [Peres-Hordecki criterion](https://en.wikipedia.org/wiki/Peres%E2%80%93Horodecki_criterion): suppose you have a channel performing $\mathcal{T}$ on the thystem $A$. You can add another system $B$ of the same dimension, where you perform the identity $\mathcal{I}$ *i.e.* wher you don’t do anything. The global map on $AB$ is then $\mathcal{T}\_A⊗\mathcal{I}\_B$, which is not positive any more: some linear algebra shows $\mathcal{T}\_A⊗\mathcal{I}\_B(Φ\_{AB})$ has $d(d-1)/2$ negative eignevalues, where $Φ\_{AB}$ is a maximally entangled state.

For a map $\mathcal E$ to be physical, any extension of the form $\mathcal E⊗\mathcal I$ has therefore to be positive. This is the definition of complete positivity. The Stinespring dilation theorem then shows that this necessary condition is sufficient, since it gives a recipe to implement any CPTP map with an ancillary subsystem and and a unitary.

> **Comments:**
> **username_0**: Thanks, that is very informative! I've been struggling to find an intuitive explanation of this. Is there some literature from which you draw the counter-example for the requirement of the map to be completely positive?  
> **username_0**: Another interesting question is whether it is impossible for *some* map to not be a CPTP (and therefore not fall under Stinespring's dilation theorem) but still be physically realizable using an ancillary subsystem?  
> **username_1**: I found this example through my own struggle with the concept of CPTP maps and partial transpose years ago . The counter example directly comes from the Peres-Horodecki criterion.  
> **username_1**: If a map is positive but not CP, one can construct an entangled state which would transform into a nonpositive  (hence non physical) state. Therefore this map is not physically realisable.  Such maps are used as entanglement witnesses and are useful for theoreticians, but there really is no hope to create them experimentally.  
> **username_0**: That makes sense. Thank you for your help! Is it the case that a map that is not trace-preserving has no equivalent quantum circuit using ancillary either?  
> **username_1**: “Trace preserving” is the technical term for “probability preserving”. You cannot have trace increasing maps, otherwise you could have result happening with probability greater than 100%, which makes no sense. Trace decreasing maps are used sometimes to describe “part of maps” or maps which have a finite probability of uninteresting events (often failures),similarly to the use of subnormal density matrices e.g. $\mathrm{Tr}\mathcal E(ρ)=.83$  means that the map has a probability to fail of 17%. It can also be described by a TP map, where the fail event is included in the output Hilbert space  
> **username_0**: This rabbit hole just goes deeper and deeper aha! If I had some CP *trace-reducing* map, is it implicit that I can describe this by a *CP*TP map ?  Sorry for all of the questions, each answer you give just raises more!  
> **username_1**: Yes. If $\mathcal E$ is a CP trace decreasing map, it can be described by the CPTP map $\mathcal E'$ defined as follows (among many possibilityes). Let $p≝\mathrm{Tr}\mathcal E(ρ)$. With probabililty $p$, $\mathcal E'(ρ)=0⊗\mathcal E(ρ)/p$ , with probability $1-p$, $\mathcal E'(ρ)=1⊗σ$, where $σ$ is an arbitrary state. The first bit '0' or '1' can be seen as a flag telling the success or failure of this protocol.  
> **username_0**: Thankyou, you have provided a very in-depth description of the space I was looking to understand. It feels weird to choose someone else's answer over Peter Shor's but in this case it seems appropriate (not that his is in any way lacking) :)  
> **username_2**: I agree. Frédéric clearly put more effort into his answer, and it's more detailed, so it deserves the checkmark.  

---

### Answer by username_2 on 2016-06-30. Score: 6

Look at [John Preskill's Lecture Notes](http://www.theory.caltech.edu/%7Epreskill/ph219/index.html#lecture); particularly Section 3.2.

As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, so you no longer necessarily have a pure state of your system.

For non-unitary quantum operations, if you assume that the environment doesn't remember anything, then the most general thing you can do is a unitary operation followed by throwing away some part of the system.

If you assume that the environment has memory, things get much more complicated. But note that here, your operations aren't consistent because the outcome of an operation will depend on what the input was the last time you performed the operation. I don't know if you want to include this class of operations. While they are important in physics, they aren't very useful for quantum computation.

> **Comments:**
> **username_0**: Thanks! :) The lecture notes are very helpful. Is there a general method/algorithm for constructing a unitary operation from a non-unitary operation?  
> **username_2**: What you're asking for is an algorithm version of the Stinespring dilation theorem. I believe most proofs of this theorem can be turned into algorithms; however, offhand I don't know a good reference for this.  
> **username_0**: Great, that's more than enough to give me a direction. Thank you for the help!  

---

