Representing quantum channels

[viathor]

At the moment the channel protocol returns a sequence of Kraus operators. This representation of quantum channels is cumbersome. For example, naively composing k channels leads to growth in the number of operators that is exponential in k (to arrest the growth of the number of operators one needs to re-express them in an operator basis manually after composition). Another drawback of the representation is that it is ambiguous (different sets of Kraus operators may describe the same channel). This makes it tricky to compare channels.

It seems that a more practical representation arises from the Choi–Jamiołkowski isomorphism (aka state-channel duality). For a start, its mypy type is simpler: np.ndarray rather than Sequence[np.ndarray]. Also, it makes composition and comparisons easier. Finally, it simplifies tasks such as the computation of process fidelity(*).

One way to deal with the issue is to switch to the state representation of channels. Another, would be to encapsulate channels in a type that hides the representation and provides methods for tasks such as the application of the channel to a state, the computation of process fidelity, etc.

Filing for discussion.

Context: #3226.

---

(*) Process fidelity can be computed from the process matrix (in computational basis) with one matrix-vector product and one dot product (and in the Pauli basis with a single lookup).

[maffoo]

Another, would be to encapsulate channels in a type that hides the representation and provides methods for tasks such as the application of the channel to a state, the computation of process fidelity, etc.

I like this idea, though there are details to be worked out. I was thinking about this in the context of https://github.com/quantumlib/Cirq/pull/3249 where in some cases we might want to have a decomposed representation of the channel, even if the operation can't be decomposed. For example, the measurement channel as currently implemented requires a number of Krauss operators that is exponentially large in the number of measured qudits. This channel can be straightforwardly decomposed into a phase damping channel on each qudit, but we don't want to implement _decompose_ on the MeasurementGate itself because that would split it into multiple measurements with the same key.

[dabacon]

A couple of comments: 1) There are many different representations that one could consider even beyond what is described, including the process matrix representation and the pauli transfer representation (https://arxiv.org/pdf/1509.02921.pdf is a good intro). Each of these has its plusses and minuses. Definitely we should support calculating these. 2) While different representations give the same channel, this is not true if one is interpreting the channels as measurements (i.e when the index of the Krauss operator corresponds to a measurement outcome), so in some cases using the unitary degree of freedom in the representation can be a bit dangerous.

As for the Choi–Jamiołkowski isomorphism, I think it does suffer from some drawbacks: one is that it maps CPT maps to unnormalized states, and one has to do work to understand if you really have a CPT map (theorists often ignore this, but likely this is because the CJ isomorphism is a bit off, the right one is actually an isomorphism between a bi partite quantum state and a channel plus an initial state. See https://mattleifer.info/2011/08/01/the-choi-jamiolkowski-isomorphism-youre-doing-it-wrong/ ). Definitely being able to calculate a Choi matrix for a channel is something we want, but I think the Krauss operator sum representation is very much a standard.

Per maffoo@s comment, I don't think there is a way around the exponential number of operations in the n qubit measurement gate. There are 2^n outcomes. I think the exponential @viathor is discussing is from composition where you should always be able to keep the number of Krauss operators below 4^n, though if you want to interpret any of them as measurement outcomes this is no longer true. For example, imagine composing measurement, unitary, measurement, unitary, etc on n qubits, you can model this as a channel, forgetting the measurement outcomes, using 4^n Krauss operators, but you will lose the mapping to the measurement outcomes. For the n qubit measurement, however, the acton_on should be able to efficiently apply the measurement. But maybe what maffoo@ is saying here is that if we had an efficient tensor representation this would not be 2^n 2^n x 2^n matrices, but 2^n tensor products of n 2x2 matrices?

[maffoo]

@dabacon, isn't it true that an n-qubit measurement is equivalent to n 1-qubit measurements? In that case instead of 2^n channel elements of size 2^n x 2^n we can represent this as n channels, each with 2 elements of size 2x2. You still get 2^n possible outcomes because each of the n single-qubit measurements has two possible outcomes.

[dabacon]

@dabacon, isn't it true that an n-qubit measurement is equivalent to n 1-qubit measurements? In that case instead of 2^n channel elements of size 2^n x 2^n we can represent this as n channels, each with 2 elements of size 2x2. You still get 2^n possible outcomes because each of the n single-qubit measurements has two possible outcomes.

Yeah I think this was what I was trying to say in the last part of my paragraph. Just like X^{\otimes n} is really a 2^n by 2^n unitary, there is a more efficient representation as n 2x2 matrices. This requires some notion of the tensor product of the space, which we haven't really codified in Cirq afaik.

[maffoo]

I just noticed that in the density matrix simulator we actually do this decomposition for the measurement channel, at least in the case where we are ignoring measurement results (see https://github.com/quantumlib/Cirq/blob/master/cirq/sim/density_matrix_simulator.py#L305, which applies a phase damp channel on each qubit in the measurement). But if you ask the MeasurementGate itself what its channel is, there is currently no way to say that it decomposes in this way, so other simulators would have to implement this optimization as a special case like the density matrix sim does. I think this sort of decomposed channel representation could be defined fairly straightforwardly.

[mpharrigan]

Regarding the first post, I don't think we should "switch" the representation to channels. This sounds like an ideal place for "protocols" where an operation can give its choi matrix "by hand" or it can be automatically computed from the kraus operators

[daxfohl]

@mpharrigan So you're suggesting here we leave channel alone and instead create a new protocols.choi that looks something like the following?

def choi(op):
    f = getattr(op, '_choi_')
    if f is NotImplemented:
         kraus = protocols.channel(op)
         return kraus_to_choi(kraus)  # todo
    else:
        return f(op)

(and perhaps update the channel protocol to fall back to a choi_to_kraus?)

Is this something that would be immediately useful?

Would we want to return the raw matrix, or wrap it in a ChoiMatrix class that has some useful functions?

[daxfohl]

Would we want to return the raw matrix, or wrap it in a ChoiMatrix class that has some useful functions?

FWIW I'd vote for the latter, even if the only initial function is get_matrix(). That would allow us eventually to have some class hierarchy with e.g. Channel as a base class, like @maffoo is suggesting.

[daxfohl]

(Higher-level, should Cirq have a more robust QIS class hierarchy? Right now, all the protocols emit raw numpy arrays, or sequences thereof, without anything other than documentation saying what those arrays are and what you can do with them. Seems like a level of naming and abstraction would be useful.

i.e. should protocols.channel return a Kraus type, and protocols.choi return a Choi type, each of which implements a QisChannel interface, which itself extends QisOperation, or something like that? Or do we prefer working directly with the numpy types and this would just get in the way?

If this does seem useful, is it possible to change our protocol return types without breaking compatibility?

Also mentioned this in #3641)

[mpharrigan]

Yes, your sketch of the choi protocol is how I'd imagine it.

re: wrappers around numpy arrays. See #3419 and related PRs for some steps towards this. I think it's important not to add too much cruft on top of numpy arrays to not scare folks off.

[daxfohl]

It seems most QIS libraries reference the following https://arxiv.org/abs/1111.6950 [edit: updated to correct link], and provide some object model with Channel as the interface and Kraus, Choi, Chi, and Superoperator as implementations of that interface, basically thin wrappers around the corresponding tensor formats and some utility methods and applicable measures, with various conversions to and from each. I think that's pretty clean, simple, and usable and is the direction I'd propose. I don't see a strong reason to stray from the beaten path here.

First I'll focus on Choi and then bring in the others. Thoughts?

[mpharrigan]

That's the reference I learned it from! It's also in Wood's thesis (which is technically actually where I learned it)

see, e.g. https://github.com/quantumlib/Cirq/issues/2763#issuecomment-670207531 and https://github.com/quantumlib/Cirq/pull/3198#issuecomment-671492015 where I pointed it out :) :)