Skip to content

Conversation

raynelfss
Copy link
Contributor

@raynelfss raynelfss commented Oct 16, 2024

Summary

Adds a new struct DAGCircuitBuilder (name has changed 😄) that enables chained addition of instructions both valid and invalid into the DAGCircuit. Also, adapts existing structures to those new changes.

Details and comments

  • Add struct that allows continuous addition of instructions into the back of the DAGCircuit by performing edge modifications in the output nodes at the end of the additions.
  • The new struct includes the following new methods:
    • push_back which pushes a valid PackedInstruction into the back of the DAGCircuit. It behaves very similarly to push_back.
    • apply_operation_back which inserts a new operation into the back of the DAGCircuit. It has two variants which depend on the ownership of the bit indices (Qubit, Clbit).
    • pack_instruction: creates a valid instance of PackedInstruction based on other provided attributes.
  • Modified DAGCircuit::extend to use this new API, without any considerable losses.

What about front additions?

This struct currently does not support adding instructions continuously to the front of the DAGCircuit because the methodology for that is a little different. It requires doing much more shifting than adding to the back, therefore I suggest studying the commonality of the use case and checking if it could be done in a follow-up.

Questions and comments?

Feel free to add these below as a review or comment 😸

- Add struct that allows continuous addition of instructions into the back of the `DAGCircuit` by performing edge modifications in the output nodes at the end of the additions.
- The new struct includes the following new methods:
    - `push_operation_back` which pushes a valid `PackedInstruction` into the back of the `DAGCircuit`. It behaves very similarly to `push_back`.
    - `apply_operation_back` which inserts a new operation into the back of the `DAGCircuit`. It has two variants which depend on the ownership of the bit indices (`Qubit`, `Clbit`).
    - `pack_instruction`: private method that basically does just that, it creates a valid instance of `PackedInstruction` based on other provided atributes.
- Modified `DAGCircuit::extend` to use this new API, without any considerable losses.
@raynelfss raynelfss added Changelog: None Do not include in changelog Rust This PR or issue is related to Rust code in the repository labels Oct 16, 2024
@raynelfss raynelfss added this to the 1.3.0 milestone Oct 16, 2024
@raynelfss raynelfss requested a review from a team as a code owner October 16, 2024 16:40
@qiskit-bot
Copy link
Collaborator

One or more of the following people are relevant to this code:

  • @Qiskit/terra-core

@raynelfss raynelfss changed the title [DAGCircuit improvements] Add new API for inserting multiple operations in Rust. Add new API for inserting multiple operations into the DAGCircuit in Rust. Oct 16, 2024
@coveralls
Copy link

coveralls commented Oct 16, 2024

Pull Request Test Coverage Report for Build 14517820673

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

Details

  • 281 of 283 (99.29%) changed or added relevant lines in 3 files are covered.
  • 49 unchanged lines in 8 files lost coverage.
  • Overall coverage increased (+0.007%) to 88.247%

Changes Missing Coverage Covered Lines Changed/Added Lines %
crates/circuit/src/dag_circuit.rs 222 224 99.11%
Files with Coverage Reduction New Missed Lines %
crates/accelerate/src/unitary_synthesis.rs 1 94.81%
crates/qasm2/src/expr.rs 1 94.23%
crates/accelerate/src/basis/basis_translator/mod.rs 2 89.48%
crates/qasm2/src/lex.rs 3 92.23%
qiskit/transpiler/passes/layout/vf2_utils.py 9 93.2%
qiskit/transpiler/passes/layout/vf2_layout.py 10 91.94%
crates/accelerate/src/vf2_layout.rs 11 83.43%
crates/qasm2/src/parse.rs 12 96.68%
Totals Coverage Status
Change from base Build 14467365414: 0.007%
Covered Lines: 73817
Relevant Lines: 83648

💛 - Coveralls

@raynelfss raynelfss modified the milestones: 1.3.0, 1.4.0 Oct 18, 2024
@raynelfss raynelfss mentioned this pull request Oct 18, 2024
4 tasks
- Add struct that allows usage of both slice or owned collections of bit indices.
- Leverage use of `as_concat()` in `circuit_to_dag`.
- Leverage usage of new methods in `UnitarySynthesis` after Qiskit#13141 merged.
@ElePT ElePT self-assigned this Oct 21, 2024
@raynelfss
Copy link
Contributor Author

raynelfss commented Oct 31, 2024

After rewriting the logic of the BasisTranslator pass to use this new API, there was some minor speedup within the pass:

Change Before [f3bac5a] After [c91d45b] Ratio Benchmark (Parameter)
- 17.0±0.1ms 15.3±0.2ms 0.9 passes.MultipleBasisPassBenchmarks.time_basis_translator(5, 1024, ['rz', 'x', 'sx', 'cx', 'id'])
- 15.1±0.3ms 13.0±0.2ms 0.86 passes.MultipleBasisPassBenchmarks.time_basis_translator(5, 1024, ['u', 'cx', 'id'])
- 42.8±0.8ms 36.4±0.4ms 0.85 passes.MultipleBasisPassBenchmarks.time_basis_translator(14, 1024, ['rz', 'x', 'sx', 'cx', 'id'])
- 36.7±0.3ms 30.9±0.2ms 0.84 passes.MultipleBasisPassBenchmarks.time_basis_translator(14, 1024, ['u', 'cx', 'id'])
- 51.1±0.4ms 42.9±0.3ms 0.84 passes.MultipleBasisPassBenchmarks.time_basis_translator(20, 1024, ['u', 'cx', 'id'])
- 21.6±0.1ms 17.7±0.1ms 0.82 passes.MultipleBasisPassBenchmarks.time_basis_translator(5, 1024, ['rx', 'ry', 'rz', 'r', 'rxx', 'id'])
- 59.3±0.9ms 48.0±0.2ms 0.81 passes.MultipleBasisPassBenchmarks.time_basis_translator(20, 1024, ['rz', 'x', 'sx', 'cx', 'id'])
- 81.3±0.3ms 64.0±1ms 0.79 passes.MultipleBasisPassBenchmarks.time_basis_translator(20, 1024, ['rx', 'ry', 'rz', 'r', 'rxx', 'id'])
- 59.2±1ms 45.8±0.6ms 0.77 passes.MultipleBasisPassBenchmarks.time_basis_translator(14, 1024, ['rx', 'ry', 'rz', 'r', 'rxx', 'id'])

@raynelfss raynelfss modified the milestones: 1.4.0, 2.0.0 Nov 1, 2024
@raynelfss raynelfss requested a review from ElePT January 23, 2025 20:27
Copy link
Member

@jakelishman jakelishman left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is a very neat idea, and something I've been interested in in the past. Aside from the inline comments, I have one main consideration (as two chained questions):

  1. Is there any way we can get by with just extend as is? UnitarySynthesis was doing that, so can BasisTranslator be re-organised to do it too? There are ways around the set-up overhead of the method.
  2. Failing that: I mentioned in one of the comments that there's a big unsafety here in that if you forget to call DAGCircuitConcat::end but just let the concatenator go out of scope, the DAG is now irreparably broken (from the caller's perspective). We definitely need to make that harder to do, ideally impossible. Making end the destructor makes it harder to make the mistake, but not impossible. I note that the only places we call extend (or the concatenator) are in situations where we're doing a full DAG rebuild, so we could actually take ownership of the DAGCircuit. In that situation, now you can have DAGCircuitConcat take ownership, and end return the ownership, so the caller can't ever observe the DAGCircuit in a broken state.

Comment on lines 6938 to 6959
/// Applies a new operation to the back of the circuit. This variant works with non-owned bit indices.
pub fn apply_operation_back(
&mut self,
py: Python,
op: PackedOperation,
qubits: Option<OwnedOrSlice<Qubit>>,
clbits: Option<OwnedOrSlice<Clbit>>,
params: Option<SmallVec<[Param; 3]>>,
extra_attrs: ExtraInstructionAttributes,
#[cfg(feature = "cache_pygates")] py_op: Option<PyObject>,
) -> NodeIndex {
let instruction = self.pack_instruction(
op,
qubits,
clbits,
params,
extra_attrs,
#[cfg(feature = "cache_pygates")]
py_op,
);
self.push_operation_back(py, instruction)
}
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm not sure this offers much over making pack_instruction public and only exposing push_operation_back - the output of pack_instruction is already effectively public because you can retrieve the PackedInstruction by indexing the DAG, so I'm not sure we're gaining anything by making it private.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hmm... sounds good, but I did want to keep an effectively similar method to DAGCircuit::apply_operation_back. I think that both exposing the pack_instruction method and keeping the apply_operation_back would be a viable option.

Comment on lines 6961 to 6964
/// Pushes a valid [PackedInstruction] to the back ot the circuit.
pub fn push_operation_back(&mut self, py: Python<'_>, inst: PackedInstruction) -> NodeIndex {
let op_name = inst.op.name();
let (all_cbits, vars): (Vec<Clbit>, Option<Vec<Var>>) = {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

There are allocation inefficiencies in this function that we can definitely improve on with this new struct, but better to leave them for a follow-up, I think.

Comment on lines 114 to 115
let mut out_dag_concat = out_dag.as_concat();
for out_node in synth_dag.topological_op_nodes()? {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This function (apply_synth_dag) doesn't feel like it's high enough in the call tree, because we're allocating and de-allocating the concatenator for each synthesised unitary matrix, whereas in an ideal world we'd do that only once. Perhaps we should be passing the concatenator through the function calls?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The call to out_dag.as_concat() was moved higher up in the stack in bf26f56.

- Allow `DAGCircuitConcat` to take ownership of the original `DAGCircuit` it is being called from, and allow `DAGCircuitConcat::end` to return the original `DAGCircuit`.
- Bypass taking ownership of the `DAGCircuit` during `DAGCircuit::extend` calls by swapping with a temporary replacement.
- A previous commit added some inefficient code into the `apply_synth_dag` function in `UnitarySynthesis`. The newer code should be much simpler to use.
- Rename interner views in `DAGCircuitConcat` to match their `DAGCircuit` counterparts.
@raynelfss raynelfss requested a review from jakelishman March 20, 2025 18:08
@kevinhartman kevinhartman self-assigned this Apr 3, 2025
Copy link
Contributor

@kevinhartman kevinhartman left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks good overall.

A few comments. I think we should probably move away from having the interners pub in a future PR, in favor of some way of accessing them that doesn't allow the user to replace them (i.e. make sure their semantics are append-only).

Comment on lines 6538 to 6546
let mut new_nodes = Vec::new();
// TODO: Find a less hacky way of doing this
let mut replacement_dag = DAGCircuit::new()?;
std::mem::swap(self, &mut replacement_dag);
let mut dag_concat = replacement_dag.into_concat();
for inst in iter {
new_nodes.push(dag_concat.push_instruction_back(py, inst?));
}
std::mem::swap(self, &mut dag_concat.end());
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this is the only way to do this. If we implement Default for DAGCircuit, then you could use mem::take instead and then *self = dag_concat.end() at the end. But it'd be doing the same thing, it'd just look less noticeable that a dummy value is in play here.

@@ -197,9 +198,9 @@ pub struct DAGCircuit {
cregs: RegisterData<ClassicalRegister>,

/// The cache used to intern instruction qargs.
pub qargs_interner: Interner<[Qubit]>,
qargs_interner: Interner<[Qubit]>,
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I agree that these should not be mutable, the reason being that it makes it possible to modify a DAGCircuit into an invalid state, e.g. we could std::mem::swap an empty Interner over this one, which opens us up to crashes and unpredictable behavior.

The pub was originally needed for #13141, which makes the valid point that they're useful when building PackedInstruction instances. You are still exposing them mutably from DAGCircuitConcat, which is moving the problem.

It may be beyond the scope of this PR to address this.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice, it looks like you were able to encapsulate this again. We'll see if it stays that way, but glad to see this!

}

/// Returns a mutable view to the qubit interner
pub fn qargs_interner_mut(&mut self) -> &mut Interner<[Qubit]> {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As mentioned higher up, these still leak a mutable Interner from the DAGCircuit (probably something we should address separately).

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For now, I can change the mutable views into just insert_cargs and insert_qargs, since it is the only way they're used.

raynelfss and others added 3 commits April 7, 2025 10:20
Co-authored-by: Kevin Hartman <kevin@hart.mn>
- Create `_push_back` method to perform initial additions and parsing before pushing an instruction into the circuit. This will be used by both the `DAGCircuit` and the `DAGCircuitBuilder`.
- Fix `DAGCircuitBuilder::end` docstring.
- Remove `qarg/carg_interner_mut`, replaced by `insert_qargs/cargs`.
@raynelfss raynelfss requested a review from kevinhartman April 7, 2025 17:00
Copy link
Contributor

@kevinhartman kevinhartman left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looking good, just a few more minor comments. Thanks for the changes!

@@ -197,9 +198,9 @@ pub struct DAGCircuit {
cregs: RegisterData<ClassicalRegister>,

/// The cache used to intern instruction qargs.
pub qargs_interner: Interner<[Qubit]>,
qargs_interner: Interner<[Qubit]>,
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Nice, it looks like you were able to encapsulate this again. We'll see if it stays that way, but glad to see this!

Comment on lines +7361 to +7368
pub fn qargs_interner(&self) -> &Interner<[Qubit]> {
&self.dag.qargs_interner
}

/// Returns an immutable view to the clbit interner
pub fn cargs_interner(&self) -> &Interner<[Clbit]> {
&self.dag.cargs_interner
}
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I recognize we have these very same methods on DAGCircuit which expose a non-mutable ref to the Interners, but it feels a bit odd to me that we use wrapper methods for the mutable stuff (e.g. insert_qargs) but expose the interners directly for read-only stuff. It'd be nice if everything was at the same level, i.e. either wrapper methods get_qargs and insert_qargs, or expose the interners directly (which of course has the mutability issue).

What you've got is probably fine for now, but IMO the InternerViewMut stuff you mentioned offline might be a nice way to unify things in a future PR.

raynelfss and others added 2 commits April 9, 2025 10:31
Co-authored-by: Kevin Hartman <kevin@hart.mn>
- Rename `_push_back` to `get_classical_resources`.
- Rename variables to keep the naming scheme.
- Remove `increment_op` step from `get_classical_resources`.
@raynelfss raynelfss requested a review from kevinhartman April 9, 2025 16:17
@raynelfss raynelfss requested a review from kevinhartman April 16, 2025 13:17
Copy link
Contributor

@kevinhartman kevinhartman left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Almost there, just a few minor comments, mostly just correcting old variable names.

raynelfss and others added 2 commits April 17, 2025 10:07
Co-authored-by: Kevin Hartman <kevin@hart.mn>
- Remove mutably borrowing the `DAGCircuit` in `get_classical_resources`.
@raynelfss raynelfss requested a review from kevinhartman April 17, 2025 14:22
Copy link
Contributor

@kevinhartman kevinhartman left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good to me!

Thanks for doing this, and for the changes. This is a neat tool.

@kevinhartman kevinhartman added this pull request to the merge queue Apr 17, 2025
Merged via the queue into Qiskit:main with commit ba4dd7a Apr 17, 2025
24 checks passed
raynelfss added a commit to raynelfss/qiskit that referenced this pull request Apr 21, 2025
…n Rust. (Qiskit#13335)

* Initial: Add `DAGCircuitConcat` struct and new insertion API.
- Add struct that allows continuous addition of instructions into the back of the `DAGCircuit` by performing edge modifications in the output nodes at the end of the additions.
- The new struct includes the following new methods:
    - `push_operation_back` which pushes a valid `PackedInstruction` into the back of the `DAGCircuit`. It behaves very similarly to `push_back`.
    - `apply_operation_back` which inserts a new operation into the back of the `DAGCircuit`. It has two variants which depend on the ownership of the bit indices (`Qubit`, `Clbit`).
    - `pack_instruction`: private method that basically does just that, it creates a valid instance of `PackedInstruction` based on other provided atributes.
- Modified `DAGCircuit::extend` to use this new API, without any considerable losses.

* Add: `OwnedOrSlice<T>`
- Add struct that allows usage of both slice or owned collections of bit indices.
- Leverage use of `as_concat()` in `circuit_to_dag`.

* Add: Optional qargs/cargs in `apply_operation_back`
- Leverage usage of new methods in `UnitarySynthesis` after Qiskit#13141 merged.

* Fix: Leverage usage in `BasisTranslator`

* Fix: Replace `OnceCell` with `OnceLock`

* Fix: Remove `SliceOrOwned` in favor of `Cow`

* Fix: Expose the interners via references within `DAGCircuitConcat`.

* Refactor: `DAGCircuit::as_concat` to `DAGCircuit::into_concat`.
- Allow `DAGCircuitConcat` to take ownership of the original `DAGCircuit` it is being called from, and allow `DAGCircuitConcat::end` to return the original `DAGCircuit`.
- Bypass taking ownership of the `DAGCircuit` during `DAGCircuit::extend` calls by swapping with a temporary replacement.

* Fix: Remove inefficient code from `UnitarySynthesis`
- A previous commit added some inefficient code into the `apply_synth_dag` function in `UnitarySynthesis`. The newer code should be much simpler to use.
- Rename interner views in `DAGCircuitConcat` to match their `DAGCircuit` counterparts.

* Fix: Remove obsolete pytoken.

* Update crates/circuit/src/dag_circuit.rs

Co-authored-by: Kevin Hartman <kevin@hart.mn>

* Fix: Address comments from code review
- Create `_push_back` method to perform initial additions and parsing before pushing an instruction into the circuit. This will be used by both the `DAGCircuit` and the `DAGCircuitBuilder`.
- Fix `DAGCircuitBuilder::end` docstring.
- Remove `qarg/carg_interner_mut`, replaced by `insert_qargs/cargs`.

* Apply suggestions from code review

Co-authored-by: Kevin Hartman <kevin@hart.mn>

* Fix: Address review comments
- Rename `_push_back` to `get_classical_resources`.
- Rename variables to keep the naming scheme.
- Remove `increment_op` step from `get_classical_resources`.

* Fix: Limit `get_classical_resources` to only `Clbits` and `Vars`.
- Remove `DAGNodeInfo`.

* Fix: Missing `py` token added after modification to `DAGCircuit::num_vars()`

* Apply suggestions from code review

Co-authored-by: Kevin Hartman <kevin@hart.mn>

* Fix: Remove usage of `end`.
- Remove mutably borrowing the `DAGCircuit` in `get_classical_resources`.

---------

Co-authored-by: Kevin Hartman <kevin@hart.mn>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Changelog: None Do not include in changelog Rust This PR or issue is related to Rust code in the repository
Projects
None yet
Development

Successfully merging this pull request may close these issues.

7 participants