Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Add DAGCircuit method to get mapping of Qubit and Clbit to positional index #9389

Closed
mtreinish opened this issue Jan 18, 2023 · 4 comments · Fixed by #10128
Closed

Add DAGCircuit method to get mapping of Qubit and Clbit to positional index #9389

mtreinish opened this issue Jan 18, 2023 · 4 comments · Fixed by #10128
Assignees
@zain2864
Labels
good first issue Good for newcomers type: feature request New feature or request

Comments

@mtreinish
Copy link
Member

What should we add?

Right now a very common thing that transpiler passes need is the positional index of a bit object. The instructions arguments are expressed in terms of the objects, but most hardware aware passes need the qubit number to be able to look up the properties of the target backend. According I checked and as of opening this there are 26 instances of passes internally doing something:

qubit_map = {qubit: i for i, qubit in enumerate(dag.qubits)}

(and at least 3 open PRs I know of adding more instances of this to passes)

Instead of doing this dict comprehension everywhere we should have a method on the dagcircuit to look this up efficiently. It should do this in constant time instead of needed to traverse DAGCircuit.qubits which likely means creating adding an attribute on the dag that tracks these positions so it's quick to look up when needed.
@mtreinish mtreinish added good first issue Good for newcomers type: feature request New feature or request labels Jan 18, 2023
@mtreinish mtreinish mentioned this issue Jan 18, 2023
Closed
@github-project-automation github-project-automation bot moved this to Tagged but unassigned in Contributor Monitoring Jan 19, 2023
@zain2864
Copy link
Contributor

Hi, can I try this issue?

@jakelishman
Copy link
Member

Hi @zain2864: sure, thanks! If you need a start, you might want to look at how QuantumCircuit does this as it does something similar. To solve the issue, we'll want to add the new attribute to DAGCircuit, and replace all the times in transpiler passes where this happens with your new attribute.

@jakelishman jakelishman moved this from Tagged but unassigned to Assigned in Contributor Monitoring Jan 25, 2023
mtreinish added a commit to mtreinish/qiskit-core that referenced this issue Feb 10, 2023
@mtreinish
Fix potential non-determinism in DAGOpNode sort key
f702d0b 
This commit fixes potential source of non-determinism when topologically
sorting a DAGCircuit object. The lexicographical_topological_sort()
function we're using from rustworkx takes a sort key callback that
returns a string which is used for tie breaking in the topological sort.
The string used for op nodes was previously `str(qargs)`, but this is
potentially problematic for standalone Qubit objects. The repr for a
qubit without a register set will include the memory address of the bit
object. This could result in the topological sort differing between
executions of the same program which could lead to unexpected results.
This commit fixes this by changing the sort key to be a string of the
qubit indices in the dag instead of the qubit objects in qargs.

This commit will likely introduce a small performance regression because
we're adding overhead on every DAGOpNode creation. This regression can
be addressed when Qiskit#9389 is implemented because we can just pass the data
structure mapping bit objects to indices to the constructor instead of
having to build that mapping on each op node.

Additionally, some test cases were fixed as part of this commit, because
several DAGCircuit test cases were incorrectly calling
apply_operation_back() and setting clbits as qargs which will now fail
because of the index lookup on qubits.
This was referenced Feb 10, 2023
Merged
Merged
@enavarro51
Copy link
Contributor

Hi, @zain2864. Are you still working on this? Thanks.

@zain2864
Copy link
Contributor

Hi, @enavarro51 , I am still working on this, I was just having some trouble, but I am looking into it more now.

@zain2864 zain2864 mentioned this issue May 18, 2023
Merged
@mtreinish mtreinish mentioned this issue Jul 12, 2023
Closed
@github-project-automation github-project-automation bot moved this from Assigned to Done in Contributor Monitoring Jul 20, 2023
github-merge-queue bot pushed a commit that referenced this issue Aug 3, 2023
@mtreinish @jakelishman
Fix potential non-determinism in DAGOpNode sort key (#9569)
a44185d 
* Fix potential non-determinism in DAGOpNode sort key

This commit fixes potential source of non-determinism when topologically
sorting a DAGCircuit object. The lexicographical_topological_sort()
function we're using from rustworkx takes a sort key callback that
returns a string which is used for tie breaking in the topological sort.
The string used for op nodes was previously `str(qargs)`, but this is
potentially problematic for standalone Qubit objects. The repr for a
qubit without a register set will include the memory address of the bit
object. This could result in the topological sort differing between
executions of the same program which could lead to unexpected results.
This commit fixes this by changing the sort key to be a string of the
qubit indices in the dag instead of the qubit objects in qargs.

This commit will likely introduce a small performance regression because
we're adding overhead on every DAGOpNode creation. This regression can
be addressed when #9389 is implemented because we can just pass the data
structure mapping bit objects to indices to the constructor instead of
having to build that mapping on each op node.

Additionally, some test cases were fixed as part of this commit, because
several DAGCircuit test cases were incorrectly calling
apply_operation_back() and setting clbits as qargs which will now fail
because of the index lookup on qubits.

* Update sort_key creation to use DAGCircuit.find_bit

* 0 pad integer indices and include cargs in sort key

This commit updates the sort key construction to do two things, first it
updates the integer indices used in the sort key to be 0 padded so that
the sort order is more intuitive. At the same time the sort key is not
including the cargs for an operation to ensure that's being factored
into the sort order.

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>

---------

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>
SamD-1998 pushed a commit to SamD-1998/qiskit-terra that referenced this issue Sep 7, 2023
@mtreinish @jakelishman @SamD-1998
Fix potential non-determinism in DAGOpNode sort key (Qiskit#9569)
6a5956a 
* Fix potential non-determinism in DAGOpNode sort key

This commit fixes potential source of non-determinism when topologically
sorting a DAGCircuit object. The lexicographical_topological_sort()
function we're using from rustworkx takes a sort key callback that
returns a string which is used for tie breaking in the topological sort.
The string used for op nodes was previously `str(qargs)`, but this is
potentially problematic for standalone Qubit objects. The repr for a
qubit without a register set will include the memory address of the bit
object. This could result in the topological sort differing between
executions of the same program which could lead to unexpected results.
This commit fixes this by changing the sort key to be a string of the
qubit indices in the dag instead of the qubit objects in qargs.

This commit will likely introduce a small performance regression because
we're adding overhead on every DAGOpNode creation. This regression can
be addressed when Qiskit#9389 is implemented because we can just pass the data
structure mapping bit objects to indices to the constructor instead of
having to build that mapping on each op node.

Additionally, some test cases were fixed as part of this commit, because
several DAGCircuit test cases were incorrectly calling
apply_operation_back() and setting clbits as qargs which will now fail
because of the index lookup on qubits.

* Update sort_key creation to use DAGCircuit.find_bit

* 0 pad integer indices and include cargs in sort key

This commit updates the sort key construction to do two things, first it
updates the integer indices used in the sort key to be 0 padded so that
the sort order is more intuitive. At the same time the sort key is not
including the cargs for an operation to ensure that's being factored
into the sort order.

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>

---------

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@zain2864 zain2864

Labels
good first issue Good for newcomers type: feature request New feature or request
Projects
Contributor Monitoring
Status: Done
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Add find_bit method to DAGCircuit to get mapping of bits to positional index zain2864/qiskit-terra
4 participants
@mtreinish @jakelishman @enavarro51 @zain2864