Improve ancilla detection in HighLevelSynthesis

[pdhoolia]

What should we add?

In #12911 we have added the ability to track the state of each qubit within the HighLevelSynthesis transpiler pass (i.e. whether the qubit is "clean" (in state | 0 ⟩ ) or "dirty" (in some other state)) and to automatically exploit clean/dirty ancilla qubits with the appropriate synthesis algorithms.

In the following snippet, a circuit with a single MCX-gate

qc = QuantumCircuit(10)
qc.mcx([3, 4, 5, 6, 7], 0)
basis_gates = ["u", "cx"]
tqc = HighLevelSynthesis(basis_gates=basis_gates)(qc)

is synthesized to a circuit with 24 CX-gates and 45 U-gates. Internally the MCX synthesis algorithm has access to 4 clean ancilla qubits (1, 2, 8, 9).

However, an arguably identical circuit in the following snippet,

inner = QuantumCircuit(6)
inner.mcx([0, 1, 2, 3, 4], 5)
custom_gate = inner.to_gate()
qc = QuantumCircuit(10)
qc.append(custom_gate, [3, 4, 5, 6, 7, 0])
basis_gates = ["u", "cx"]
tqc = HighLevelSynthesis(basis_gates=basis_gates)(qc)

is synthesized to a worse circuit with 84 CX-gates and 127 U-gates. This is due to how the recursion is treated with HighLevelSynthesis, with the synthesis of custom_gate having no access to ancilla qubits outside of its definition.

[pdhoolia]

To address the issue of inefficient synthesis when using custom gates in the HighLevelSynthesis transpiler pass, we need to ensure that the ancilla qubits outside of custom gate definitions are accessible during synthesis. The problem arises because the current implementation does not allow custom gates to utilize ancilla qubits that are not part of their definition, leading to suboptimal synthesis results.

Here's a plan to address this issue:

1. Modify the _synthesize_operation Method: We need to adjust how the synthesis is handled for custom gates. Specifically, when a custom gate is detected, we should allow it to access the ancilla qubits available in the broader circuit context.

2. Update the Qubit Tracker Logic: The QubitTracker should be capable of lending ancilla qubits to custom gate synthesis, even if these qubits are not part of the custom gate's initial definition.

3. Handle Custom Gates Differently: When encountering a custom gate, we should attempt to synthesize it with the available ancilla qubits, rather than treating it as a standalone entity with no access to external resources.

Here's a suggested modification to the high_level_synthesis.py file:

# In the HighLevelSynthesis class

def _synthesize_operation(
    self,
    operation: Operation,
    qubits: tuple[int],
    tracker: QubitTracker,
) -> tuple[QuantumCircuit | Operation | DAGCircuit | None, list[int] | None]:
    # Existing code...

    # Handle custom gate synthesis with external ancilla access
    if isinstance(operation, Instruction) and not operation.is_standard_gate():
        # Attempt to unroll the custom gate definition
        synthesized = self._unroll_custom_definition(operation, qubits)
        if synthesized is not None:
            aux_qubits = tracker.borrow(synthesized.num_qubits - len(qubits), qubits)
            used_qubits = qubits + tuple(aux_qubits)
            synthesized = circuit_to_dag(synthesized, copy_operations=False)

            # Map used qubits to subcircuit
            new_qubits = [synthesized.find_bit(q).index for q in synthesized.qubits]
            qubit_map = dict(zip(used_qubits, new_qubits))

            synthesized = self._run(synthesized, tracker.copy(qubit_map))
            if synthesized.num_qubits() != len(used_qubits):
                raise RuntimeError(
                    f"Mismatching number of qubits, using {synthesized.num_qubits()} "
                    f"but have {len(used_qubits)}."
                )
            return synthesized, used_qubits

    # Existing code...

    return synthesized, used_qubits

Explanation:

• Custom Gate Handling: We've added a check to identify custom gates that are not standard gates. For such gates, we attempt to unroll their definition and synthesize them using available ancilla qubits.
• Borrowing Ancilla Qubits: The tracker.borrow method is used to allocate additional ancilla qubits to the custom gate if needed, ensuring that the synthesis process can exploit available resources effectively.
• Recursive Synthesis: After obtaining the synthesized circuit from the custom gate, we recursively apply the synthesis logic to ensure that all parts of the circuit are optimized.

These changes should help in making the synthesis process more efficient by allowing custom gates to leverage external ancilla qubits, thereby addressing the issue described.