Update cirq simulators to work for cases where an operation allocates new qubits as part of it's decomposition.

[senecameeks]

This feature request is a child of Quantum Memory Management for Cirq issues/6040 . I'm splitting this subtask into its own issue for better tracking.

A POC was shown for the X Gate for state vector and density matrix simulators: #6040 (comment)

My task is to make this work generally for cirq simulators and all operations.

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 30 days

[tanujkhattar]

I've opened #6127 that does the following:

1. Refactors strat_act_on_from_apply_decompose to use cirq.decompose_once(flatten=False) instead of _try_decompose_into_operations_and_qubits. This is important so that we can pass a qubit manager to the decompose protocol and choose a smarter decomposition strategy as part of simulations. The only other two places where _try_decompose_into_operations_and_qubits is used non-trivially are apply_unitary and unitary and I claim that at these call-sites; the choice of a qubit manager is not required and therefore we don't need to add a context argument to _try_decompose_into_operations_and_qubits (cc @NoureldinYosri )

2. Update Density Matrix and State Vector Simulators to work when an operation allocates new qubits as part of its decomposition #6108 added support for add_qubits and remove_qubits to density matrix simulators and state vector simulator. I fixed a bunch of bugs that were introduced as part of this PR, for example cirq.final_density_matrix(val) first attempts to use a state vector simulator if all operations are unitary (which is the case in tests here). As part of the refactoring, I realized that simply adding the two add_qubits and remove_qubits method to DensityMatrixSimulationState is not sufficient and it results in errors because of some complicated interplay with SimulationProductState. I spent a few hours trying to debug what's happening and then gave up. As I've expressed multiple times, the highly complex type hierarchy within cirq Simulators make it very hard to follow the code flow and find bugs. So, keeping my rant aside, for now I've removed the support for add_qubits / remove_qubits from density matrix simulators and thus they would not support simulating operations allocating ancillas within decompose (except for the case when everything is unitary, in which case it falls back to cirq.apply_unitary). It'd be nice to debug what's going wrong and I would really appreciate some help here (cc @daxfohl @NoureldinYosri @senecameeks)

3. My primary motivation for the PR was to figure out a way to specify different qubit allocation strategies when decomposing operations as part of simulations. The choice of qubit allocation strategy can lead to very fast or very slow simulations since total number of system qubits to be simulated is directly affected by how aggressively the freed qubits are reused. This PR lays the foundations for this by changing the strat_act_on_from_apply_decompose to follow DFS based decomposition (instead of earlier BFS based) and accept an optional context as a parameter. The next remaining part is to figure out how to pass around context so it can be correctly supplied to strat_act_on_from_apply_decompose. This also looks like a daunting task; and I'm tempted to use a global context manager based approach but I could use help here if people have ideas for doing the refactoring and bandwidth to work on a refactoring PR. (again cc @daxfohl @NoureldinYosri)

Given the tight timeline, I would mark (3) as NOT a blocker for Cirq-FT launch given the fact that it's "only" an optimization problem; but it's definitely something very nice to have. The alternative for now is that we expect users to construct a circuit, use a custom qubit manager to decompose it to a point where they feel comfortable simulating it, and then pass it on to the simulator.

cc @senecameeks @daxfohl @NoureldinYosri @dstrain115

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 30 days

[github-actions]

Issue closed due to inactivity.

[sanuj]

I'm interested in working on this.

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 30 days

[github-actions]

This issue is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 30 days

[github-actions]

Issue closed due to inactivity.