Support for Projectors

[MichaelBroughton]

Is your feature request related to a use case or problem? Please describe.

This is related to expanding functionality in TFQ here ( tensorflow/quantum#357 )

Describe the solution you'd like

It would be nice to support projectors in cirq.PauliSum so that more complex (and still valid) expressions in cirq.PauliSum can be compressed to a reasonable length. Maybe something like:

# Normal functionality
a = 5.0 * cirq.Z(q0) - 2.0 * cirq.X(q0)

# New functionality
a = 5.0 * cirq.Z(q0) - 2.0 * cirq.X(q0) + cirq.OneProjector(q0) * cirq.ZeroProjector(q1)

Doing this right now in Cirq does not scale well:

def one_proj(q):
  return (1 - cirq.Z(q)) / 2

def zero_proj(q):
  return (1 + cirq.Z(q)) / 2

a = one_proj(q0) * one_proj(q1)
print(len(a._linear_dict.keys()))  # => 4

a = one_proj(q0) * one_proj(q1) * one_proj(q2)
print(len(a._linear_dict.keys()))  # => 8

a = one_proj(q0) * one_proj(q1) * one_proj(q2) * one_proj(q3)
print(len(a._linear_dict.keys()))  # => 16

.
.
.
# Anything past 20 is already 1 million elements and not all that usable anymore.

What is the urgency from your perspective for this issue? Is it blocking important work?

P1 - I need this no later than the next release (end of quarter)

[balopat]

Discussed on Cirq Cynq:

• this would be a valuable addition
• probably not in PauliSum but its own type - let's iterate on the design here and then create a PR

[MichaelBroughton]

Alrighty if we want to separate out this functionality, how do people like @viathor and @mpharrigan feel about something like this:

1st PR: Make a new module cirq/ops/projectors.py:

class StateProjector:
   """A projector onto a particular state and associated stuff.""""

2nd PR: In cirq/ops/linear_combinations.py we add:

class ProjectorPauliSum(cirq.PauliSum): # Anyone got a better name ?
  """Many similar features to PauliSum only now incorporating StateProjector support."""

[viathor]

Regarding 1st PR: drop the "State", just "Projector", it's cooler?

Regarding 2nd PR: Maybe we don't need that? Does LinearDict not fulfill your needs? If not, can we extend it so it does?

[MichaelBroughton]

Regarding 1st PR: drop the "State", just "Projector", it's cooler?

Can do.

Regarding 2nd PR: Maybe we don't need that? Does LinearDict not fulfill your needs? If not, can we extend it so it does?

I'm not sure I follow. Don't I still need some new code to enable things like:

a = cirq.Z(q) * cirq.X(q1) + cirq.Projector(..)

?

[viathor]

You should be able to use such expressions (not 100%, maybe some magic functions are missing, in which case we should just add them). Resulting LinearDict should be of reasonable size. The exponential growth of terms in your original comment was a consequence of the distributive law, but in

a = cirq.Z(q) * cirq.X(q1) + cirq.Projector(..)

you don't multiply a result of addition so no such growth should occur. Note however that some of the terms will not be Paulis - I assume this is fine.

[MichaelBroughton]

Note however that some of the terms will not be Paulis - I assume this is fine.

Totally fine :)

Couple concerns:

1. If I do :

type(a) # => LinearDict ?

It would be nice to have a more concrete type so in TFQ when input checking for various functions, I don't have to examine all the contents one by one any more than I have to.

2. If I do:

a *= cirq.Z(q)

If we stick with just a lineardict, would I still benefit from the luxuries of having the pauli expressions around my Projector being simplified ? (This would be a must have)

[tonybruguier]

I could be interested, if that's all right. Let me read up more and get back to you on this?

[balopat]

That would be awesome @tonybruguier, thank you!

[tonybruguier]

It seems this will be a challenge for me. I am happy to work through it, but I wouldn't want to take too much of your time during the reviews. I'd be OK if you decide someone else is better suited.

That said, I have this very draft commit:
tonybruguier@14bfbd6
Certainly not ready for review. Am I on the right track?

[balopat]

After the initial PR #3386 and chatting with both @MichaelBroughton and @viathor here is a rephrasing of requirements - comments, thoughts would be highly appreciated! Then when we have an agreed design, we can modify #3386 accordingly and prepare for the next PRs with a design in mind.

Today, one can calculate the expectation value of an observable for a given a state by defining the observable as a PauliSum. PauliSum would work perfectly for the TFQ use cases, however, there is a piece of inefficiency when it comes to projectors. Projectors are operators that could be expressed as a PauliSum in a sense as as for example Projector([[0,1]]) being the same (1-cirq.Z(q0))/2. However, for longer bitstrings, the number of terms get exponentially large, depsite the fact that it's just a single 1 on the diagonal of a 2**n x 2 **n matrix.

This change should keep the convenience of PauliSum arithmetics with a better representation of frequently used projectors.

For the first PR:

• the new class should be able to specify projectors to one or more vectors
• these vectors should be cirq.StateVectorLike and not just arrays
• it needs to be serializable
• we do not need this to be added in a circuit at all - as it is not a gate, nor a channel, it is an observable. As such it should not implement SupportsChannel and definitely shouldn't be the subclass of Gate
• it should have a matrix method that returns the matrix of the projector
• it should support expectation_value_from_state_vector and expectation_value_from_density_matrix

After the first PR:

• adding and multiplying with other projectors and PauliSumLike instances should result in an instance of a class that supports expectation_value_from_state_vector and expectation_value_from_density_matrix
  • this new class could be called Operator that could be an abstract class for BasisVectorProjector, PauliSum and even PauliString
  • the expectation value calculation on the Operator would work similarly to PauliSum: apply the matrix of each component (projectors, paulisums) to the state vector and then multiply with the bra state vector
  • suppose you have projectors P1, P2: then P1 + P2 is a projector iff P1 P2 = - P1 P2 - i.e when they anticommute - It would be worthwhile to implement this check as a special case of this is when P1 and P2 are orthogonal, i.e. when projecting to different basis vectors, this case P1 + P2 could be simply the concatenation of the arrays of vectors.

Other ideas:

• I have a design idea that I'd like @mpharrigan's thoughts on:
  • I think cirq.ProductState.projector() should return the instance of this Projector class.
  • in order to achieve this we could have .projector() defined on cirq.StateVectorMixin which should be the parent for ProductState
• we could / should have aqis.projector(STATE_VECTOR_LIKE) which could return this too
• by @viathor: we could consider "simplification by projectors" from PauliSums as an automated process later on

[mpharrigan]

If we change cirq.ProductState.projector(), I'll need some way to get the matrix form somehow

Projector operators could very easily SupportChannels and maybe even in pure state simulation. https://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22H%22%5D%2C%5B%22%E2%80%A2%22%2C%22X%22%5D%2C%5B1%2C%22%7C0%E2%9F%A9%E2%9F%A80%7C%22%5D%5D%7D

[balopat]

If we change cirq.ProductState.projector(), I'll need some way to get the matrix form somehow

The .matrix() method should work, similar to the PauliSum

Projector operators could very easily SupportChannels and maybe even in pure state simulation.

Oh, I might have misunderstood something - I thought channels should be trace-preserving - i.e. for Kraus operators A_i, \sum_i A_i A_i^{\dagger} should be the identity. For a projector like P=|0><0|, you just get P^2 = P, which is not I. In my understanding that is a quantum operator but not a channel.

[tonybruguier]

Hi,
I updated PR #3386 as a try to reflect what is being discussed. It's not a push toward one direction, I'm happy to revise it further (especially because I understand the design is not completely settled).

[viathor]

Recording an idea from a discussion in cirq sync:

The core of the original issue is that at present cirq only implements Pauli basis representation of operators (via PauliSum class) and this basis is unsuitable for certain applications since it leads to very large expressions (see first comment above). It seems a little awkward to fix this problem by providing an expansion in terms of projectors, because projectors do no form a basis (as can be readily seen by a simple counting argument). However, there is a natural basis that includes projectors: the basis of "butterfly" operators |i><k|. These incorporate computational basis projectors when i==k. In addition to being more elegant and complete this approach is likely to serve other uses, e.g. Kraus operators for some interesting channels (such as the amplitude dumping channel) take the form of these "butterfly" operators.

Two additional tools would make working with these easier:

1. Since we now have a way to represent kets, we probably want to allow users to create "butterfly" operators from them.
2. A simple factory function taking a binary string and making a projector on the corresponding subspace.

@balopat @dabacon @tonybruguier

[tonybruguier]

Thanks! So do we have consensus on going to butterfly or is it something for later?

The current approach might be faster to commit, but I'm ok with doing the butterfly approach too.

Just let me know, so that I don't accidently wait for you when you are waiting for me.

Thanks a lot for all the guidance!

[viathor]

I was a little unclear whether we reached a consensus on this idea. Let's hear from a few more people.

Regarding doing projectors first and then extending to butterfly operators: It seems to me that an implementation that targets butterfly operators directly (and obtains projectors as a special case when i==k, see above) is likely to be simpler and cleaner. I'm sorry I haven't thought of this earlier.

[balopat]

I'm pro 🦋 and scratching the current direction.
A mini conclusion I would like to draw for the future: we should design first and then implement in PRs for larger features.
So to apply this conclusion here - Tony, do you mind drawing up a design doc for this? We have an RFC template that you can use tinyurl.com/cirq-rfc-template.

Key questions:

• how would the interface look like for butterfly operators? Do we create cirq.BRA_* operators for the cirq.KET_* operators? Have a bra(psi) @ ket(psi) functions that help?
• how would they interact with PauliSum?
• how would they be a better representation for projectors - and as such solve the use case here for @MichaelBroughton?

[tonybruguier]

Here's a draft RFC:
https://docs.google.com/document/d/10MVpeUBegxHwfPzSSgP2p-yh4D6kQsMUN1TpquF3jks/edit#
Also available at:
https://tinyurl.com/cirq-proj

[tonybruguier]

Thanks for the feedback, new version (and new URL) of the RFC at: https://tinyurl.com/ketbra

[tonybruguier]

@MichaelBroughton
With #4331 and #4364 merged, is there anything left to do? If so, happy to help of course, but otherwise, maybe this issue can be closed?