Add a classical simulator to Cirq

[tanujkhattar]

The feature request is to add a classical simulator which can simulate X / CNOT and multi-controlled X gates, similar to ToffoliSimulator in Q#

See https://docs.microsoft.com/en-us/azure/quantum/machines/toffoli-simulator

cc @mpharrigan to add more context

P2 - we should do it in the next couple of quarters

cc @augustehirth This would need documentation once we get this done.

[vtomole]

xref: #3079

[daxfohl]

Note we've got a very basic implementation already in the test case for custom_simulator: https://github.com/quantumlib/Cirq/blob/master/cirq-core/cirq/contrib/custom_simulators/custom_state_simulator_test.py

I recommend starting there, copying it to its own non-test file, and then fleshing out the _act_on_fallback_ with @cduck's code https://github.com/cduck/cirqtools/blob/master/cirqtools/classical_simulator.py#L118-L149 linked in #3079.

[dstrain115]

I have a student who can do this project.

[mpharrigan]

@daxfohl the example custom simulator doesn't support things like e.g. CNOT. Do we have to switch on the gate type in _act_on_fallback_? It's probably necessary for gates themselves to declare how to operate on computational basis states like how gates know how to act on a state vector

[daxfohl]

Correct, @cduck's implementation has the proper state transition logic. My example shows how to integrate into the custom simulator infrastructure so that you get subcircuit traversal, classical control, etc. for free. So the actual implementation needs to combine these two things.

[mpharrigan]

How though? Is _act_on_fallback_ supposed to interrogate the gate to see if it has a magic method that knows how to act on a classical state?

[daxfohl]

Using protocols, like https://github.com/cduck/cirqtools/blob/master/cirqtools/classical_simulator.py#L118-L149.

[mpharrigan]

I was imagining having methods on classical gates that could express their classical action on a bitstring without tensoring up a unitary

[daxfohl]

I see, yeah you could make a new protocol like apply_to_bitstring(bitstring) -> bitstring and supplement cduck's method like

        if cirq.has_application_to_bitstring(op):
           state = cirq.apply_to_bitstring(op, state, indices)
        elif cirq.has_unitary(op):
            self._simulate_unitary(op, state, indices)
        else:
            self._simulate_mixture(op, state, indices)

or something along those lines. That way you get the apply_to_bitstring shortcut plus the ability to fall back to unitary if that protocol was not implemented on the gate.

[verult]

From Cirq sync: reverting back to accepted. @viathor let us know if there's anything you'd like to discuss

[viathor]

Oh, I think I added triage/discuss by accident (probably missed that the issue already had a triage/* label).

[tanujkhattar]

@mpharrigan As discussed offline, can you write a brief comment / code piece describing how the simulator using the protocol to act on a numpy array and falling back to the unitary application would look like? And potential advantages and challenges in using the protocol to act on 2D numpy arrays for sampling multiple classical input states in a vectorized fashion?

@dstrain115 How's the progress on this with the student? Are there any roadblocks in the initial exploration?

[navaro1]

Hello, I'd like to take a stab at this issue. I was not involved before. Will read through current implementation and comment history and then provide a comment with my understanding and strategy for the implementation.

[tanujkhattar]

@navaro1 Thanks! I've assigned the issue to you. Looking forward to your follow up summary comment.

[navaro1]

Here are some key points from the discussion and potential strategy:

1. A basic implementation already exists in the test case for custom_simulator, and it's recommended to start from there.
2. Implement _act_on_fallback_ similar to the code in @cduck classical_simulator
3. A new protocol like apply_to_bitstring(bitstring) -> bitstring could be created, which then could be leveraged to improve the implementation.

Questions (cc: @tanujkhattar):

1. Should the simulator code be put in cirq-core/cirq/sim or in the other directory?

[navaro1]

I can see that there is PR for classical simulator already - #6124. I think it would make sense to reassign this issue to author of that PR for now. I am still interested in helping, but do not want to duplicate the work.

[dstrain115]

This has been completed.