---
tags: design doc, cirq, optimizer
---
# PointOptimizer rework

## The current algorithm

### High level summary

The PointOptimizer takes a look at the `optimization` that defines:
- the qubits to be cleared at the given moment
- the number of moments to be cleared at the given moment
- the new operations to be inserted into the space created

If there is not enough "space" for the new operations to be inserted even after the specified operations have been cleared, the PointOptimizer creates new moments.

### Optimization

The optimization is defined by the `optimization_at` method of the optimizer, that is the child class of the `cirq.PointOptimizer` class.

class RemoveMeasurements(cirq.PointOptimizer):
    def optimization_at(self, circuit: cirq.Circuit, index: int, op: cirq.Operation):
      if isinstance(op.gate, cirq.MeasurementGate):
        return cirq.PointOptimizationSummary(clear_span=1,
                                             new_operations=[],
                                             clear_qubits=op.qubits)
      else:
        return None
        

The optimization can be **expansive**: when new operations arise that need more space.


Optimization can be **reductive** when the amount of operations and/or qubits in use by a given operation is reduced. A reductive optimization can result in completely empty moments.

### Frontier

The algortihm works with the concept of `frontier`, that for each qubit delineates the last modified moment by the optimizer. It starts at 0 for each qubit. If the replacement requires new operations, the new operations will push the frontier forward on the affected qubits.

For example:


The frontier ensures that the optimizer never goes into an infinite recursion by replacing already replaced operations.

### Inject moments to make space

Sometimes there are other operations right after the operation that is to be replaced. If there is not enough space, the algorithm inserts new moments. The calculation is as follows:

* get next occupied moments: see the next moments that have operations on the impacted qubits or give back the last moment in the circuit
* simulate injecting the new operations in place - push the frontier forward
* the max difference between the frontier and the next occupied moments is going to give the number of new moments to be inserted
* the insertion point is at the leftmost of the next occupied moments


An additional property that this algorithm does is that when the frontier on _qubits of previously inserted operations_ (unaffected qubits) is further than the insertion point, that gets pushed as well. This ensures that the frontier does not get out of sync with the actual moments. Note that we don't have to do that with the impacted qubits, as that frontier is pushed by the insertion of the current replacement operations.

### Insert operations

Now that we have the space created, just insert the operations.


## Issues

### Unclear properties

The best I can think of by looking at a circuit now is "it will do the replacements with some holes here and there".

We guarantee some properties sometimes, but it's undocumented and inconsistent.

- Do the replacements stay "together" or not? (see holes anomaly)
- Do we pack the replacements tightly or not?

**Recommendation**:
- the structure of replacements should be respected (no holes) - in fact we can make it stronger by allowing for moment based structure to be passed in (https://github.com/quantumlib/Cirq/issues/2406)
- the algorithm would try to pack the replacements as densely as possible, including overlapping with other replacements and non affected operations

### Anomaly: "holes" are created in overlapping expansive compilations

The problem arises when the replacement operations are overlapping

Raised by @mpharrigan in https://github.com/quantumlib/Cirq/issues/2553.

### Allows for other qubits to be involved

This has been tackled by Tanuj's work and is not allowed anymore: https://github.com/quantumlib/Cirq/pull/3016/files

### Questionable cases

#### Preserving the moment structure on the right side

For a replacer:

d: ───@───   ───@───X───X─
      │    =>   │
e: ───@───   ───@───X───X─

Input:

a: ───@───────H───
      │
b: ───@───────H───
c: ───────Y───────
d: ───@───────────
      │
e: ───@───Z───────

Current answer:

a: ───@───────────X───X───H───
      │
b: ───@───────────X───X───H───
c: ───────────────Y───────────
d: ───@───X───X───────────────
      │
e: ───@───X───X───Z───────────

Option 1: keep rest of the circuit's moment structure intact

a: ───@───X───X─────H───
      │
b: ───@───X───X─────H───
c: ──────────────Y──────
d: ───@───X───X────────
      │
e: ───@───X───X──Z──────

Option 2: allow for first replacement to disrupt the rest of the circuit

a: ───@───X───X───H───
      │
b: ───@───X───X───H───
c: ───────Y───────────
d: ───@───X───X───────────────
      │
e: ───@───X───X───Z───────────

This is harder to reason about in my opinion - but it has some rationale - the

#### Preserving the moment structure in between replaced operations

A replacer:

d: ───@───      ───@───X───X──────────
      │    =>      │                  
e: ───@───      ───@───X───X───X───X──

With input:

a: ───────Y───────
b: ───@───────────
      │
c: ───@───────────
d: ───────Y───H───
e: ───────@───────
          │
f: ───────@───Y───
g: ───────Y───────

Results currently:

a: ───────Y───────────────────────────────
b: ───@───X───────────────────X───────────
      │
c: ───@───X───────────────────X───X───X───
d: ───────Y───────────────────H───────────
e: ───────@───X───X───────────────────────
          │
f: ───────@───X───X───X───X───Y───────────
g: ───────Y───────────────────────────────

Option 1: pushing every operation

a: ───────Y──────────────────────────
b: ───@───X───X───────────────────────
      │
c: ───@───X───X───X───X───────────────
d: ───────Y─────────────────────H───
e: ───────@───X───X───────────────────
          │
f: ───────@───X───X───X───X─────Y───
g: ───────Y──────────────────────────

Option 2: allow for moment disruption for operations that share the moment with the replaced operations

a: ───────Y─────────────────────
b: ───@───X───X─────────────────
      │
c: ───@───X───X───X───X─────────
d: ───────Y───────────────────H─
e: ───────@───X───X─────────────
          │
f: ───────@───X───X───X───X───Y─
g: ───────Y─────────────────────

Yi's algo:

a: ──────────────────Y───────────────────────────────
b: ───@──X──X────────────────────────────────────────
      │
c: ───@──X──X──X──X──────────────────────────────────
d: ──────────────────Y───────────────────H───────────
e: ──────────────────@───X───X───────────────────────
                     │
f: ──────────────────@───X───X───X───X───Y───────────
g: ──────────────────Y───────────────────────────────