8000 Fix incorrect error estimation in VF2 fallback by jakelishman · Pull Request #14218 · Qiskit/qiskit · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Fix incorrect error estimation in VF2 fallback #14218

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
Merged
merged 1 commit into from
May 7, 2025
Merged

Fix incorrect error estimation in VF2 fallback #14218

merged 1 commit into from
May 7, 2025

Conversation

jakelishman
Copy link
Member

Summary

The VF2 passes include a fall-back error heuristic if the Target specifies no error rates: a number proportional to the node degree is used. This was a proxy metric, used historically becasue IBM bowtie devices (amongst others) were unreliable at reporting error rates but had significantly degraded performance on higher-degree nodes.

The calculation of the node degree, however, could double count qubits in a directional backend, and since the scaling factor is the total number of qubits, this could cause error rates greater than one, which then cause unpredictable behaviour on the scoring.

Details and comments

@jakelishman
Fix incorrect error estimation in VF2 fallback
477aab9 
The VF2 passes include a fall-back error heuristic if the `Target`
specifies no error rates: a number proportional to the node degree is
used.  This was a proxy metric, used historically becasue IBM bowtie
devices (amongst others) were unreliable at reporting error rates but
had significantly degraded performance on higher-degree nodes.

The calculation of the node degree, however, could double count qubits
in a directional backend, and since the scaling factor is the total
number of qubits, this could cause error rates greater than one, which
then cause unpredictable behaviour on the scoring.
@jakelishman jakelishman added stable backport potential The bug might be minimal and/or import enough to be port to stable Changelog: Bugfix Include in the "Fixed" section of the changelog mod: transpiler Issues and PRs related to Transpiler labels Apr 17, 2025
@jakelishman jakelishman added this to the 2.0.1 milestone Apr 17, 2025
@jakelishman jakelishman requested a review from a team as a code owner April 17, 2025 13:46
@qiskit-bot
Copy link
Collaborator

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

  • @Qiskit/terra-core

@jakelishman
Copy link
Member Author

@Mergifyio backport stable/1.4 stable/2.0

@mergify Mergify
Copy link
Contributor
mergify bot commented Apr 17, 2025 •
edited
Loading

backport stable/1.4 stable/2.0

✅ Backports have been created

ElePT
ElePT reviewed Apr 17, 2025
View reviewed changes
Copy link
Contributor
@ElePT ElePT left a comment

Choose a reason for hiding this comment

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

LGTM, I am assuming that you found this by inspecting the code. Is there any way you could reproduce the bug to test the fix?

@coveralls
Copy link

Pull Request Test Coverage Report for Build 14517171718

Details

  • 2 of 2 (100.0%) changed or added relevant lines in 1 file are covered.
  • 9 unchanged lines in 3 files lost coverage.
  • Overall coverage increased (+0.004%) to 88.235%
Files with Coverage Reduction New Missed Lines %
crates/accelerate/src/unitary_synthesis.rs 1 94.79%
crates/qasm2/src/lex.rs 2 92.23%
crates/qasm2/src/parse.rs 6 97.15%
Totals Coverage Status
Change from base Build 14499882025: 0.004%
Covered Lines: 73737
Relevant Lines: 83569
💛 - Coveralls

@jakelishman
Copy link
Member Author

I could potentially try and engineer a circuit and coupling map that causes a high-degree node to get erroneously prioritised, but I think it might be a little bit tricky.

My new Rust form scores using $-\ln(1 - \bar\epsilon)$ as the score of a qubit/link (negative of the log "average" fidelity for a pretty questionable definition of "average"), which explodes if you feed it an out-of-bound error, and I accidentally encoded the exact same double-counting bug as here when I ported it. So I saw it by some defensive debug code I have elsewhere exploding because of a NaN.

kevinhartman
kevinhartman approved these changes May 7, 2025
View reviewed changes
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 fine to me, thanks!

@kevinhartman kevinhartman added this pull request to the merge queue May 7, 2025
Merged via the queue into Qiskit:main with commit 45778dd May 7, 2025
24 checks passed
mergify bot pushed a commit that referenced this pull request May 7, 2025
@jakelishman @mergify
Fix incorrect error estimation in VF2 fallback (#14218)
3901716 
The VF2 passes include a fall-back error heuristic if the `Target`
specifies no error rates: a number proportional to the node degree is
used.  This was a proxy metric, used historically becasue IBM bowtie
devices (amongst others) were unreliable at reporting error rates but
had significantly degraded performance on higher-degree nodes.

The calculation of the node degree, however, could double count qubits
in a directional backend, and since the scaling factor is the total
number of qubits, this could cause error rates greater than one, which
then cause unpredictable behaviour on the scoring.

(cherry picked from commit 45778dd)
mergify bot pushed a commit that referenced this pull request May 7, 2025
@jakelishman @mergify
Fix incorrect error estimation in VF2 fallback (#14218)
3ba46c0 
The VF2 passes include a fall-back error heuristic if the `Target`
specifies no error rates: a number proportional to the node degree is
used.  This was a proxy metric, used historically becasue IBM bowtie
devices (amongst others) were unreliable at reporting error rates but
had significantly degraded performance on higher-degree nodes.

The calculation of the node degree, however, could double count qubits
in a directional backend, and since the scaling factor is the total
number of qubits, this could cause error rates greater than one, which
then cause unpredictable behaviour on the scoring.

(cherry picked from commit 45778dd)
This was referenced May 7, 2025
Merged
Merged
@jakelishman jakelishman deleted the vf2/fallback branch May 7, 2025 22:56
github-merge-queue bot pushed a commit that referenced this pull request May 8, 2025
@mergify @jakelishman
Fix incorrect error estimation in VF2 fallback (#14218) (#14316)
5d49476 
The VF2 passes include a fall-back error heuristic if the `Target`
specifies no error rates: a number proportional to the node degree is
used.  This was a proxy metric, used historically becasue IBM bowtie
devices (amongst others) were unreliable at reporting error rates but
had significantly degraded performance on higher-degree nodes.

The calculation of the node degree, however, could double count qubits
in a directional backend, and since the scaling factor is the total
number of qubits, this could cause error rates greater than one, which
then cause unpredictable behaviour on the scoring.

(cherry picked from commit 45778dd)

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>
github-merge-queue bot pushed a commit that referenced this pull request May 8, 2025
@mergify @jakelishman
Fix incorrect error estimation in VF2 fallback (#14218) (#14316)
85be1e3 
The VF2 passes include a fall-back error heuristic if the `Target`
specifies no error rates: a number proportional to the node degree is
used.  This was a proxy metric, used historically becasue IBM bowtie
devices (amongst others) were unreliable at reporting error rates but
had significantly degraded performance on higher-degree nodes.

The calculation of the node degree, however, could double count qubits
in a directional backend, and since the scaling factor is the total
number of qubits, this could cause error rates greater than one, which
then cause unpredictable behaviour on the scoring.

(cherry picked from commit 45778dd)

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>
github-merge-queue bot pushed a commit that referenced this pull request May 8, 2025
@mergify @jakelishman @ElePT
Fix incorrect error estimation in VF2 fallback (#14218) (#14315)
75c9717 
The VF2 passes include a fall-back error heuristic if the `Target`
specifies no error rates: a number proportional to the node degree is
used.  This was a proxy metric, used historically becasue IBM bowtie
devices (amongst others) were unreliable at reporting error rates but
had significantly degraded performance on higher-degree nodes.

The calculation of the node degree, however, could double count qubits
in a directional backend, and since the scaling factor is the total
number of qubits, this could cause error rates greater than one, which
then cause unpredictable behaviour on the scoring.

(cherry picked from commit 45778dd)

Co-authored-by: Jake Lishman <jake.lishman@ibm.com>
Co-authored-by: Elena Peña Tapia <57907331+ElePT@users.noreply.github.com>
mtreinish added a commit to mtreinish/qiskit-core that referenced this pull request May 29, 2025
@mtreinish
Use correct minimum rustworkx requirement version
557064a 
The rustworkx version we have previously had set as the minimum
requirement is not correct. It was listed as 0.15.0 but we are using
`PyDiGraph.neighbors_undirected()` since Qiskit#14218 merged which was added
in rustworkx 0.16.0. [1] This means the requirement is incorrect and
if you try to run Qiskit with rustworkx 0.15.0 it will not work when
this method is run. This commit corrects this issue and bumps the
minimum supported rustworkx version in the requirements list to 0.16.0.

[1] https://www.rustworkx.org/release_notes.html#relnotes-0-16-0
@mtreinish mtreinish mentioned this pull request May 29, 2025
Closed
mtreinish added a commit to mtreinish/qiskit-core that referenced this pull request May 30, 2025
@mtreinish
Avoid using rustworkx 0.16.0 methods in vf2_utils
d458128 
In Qiskit#14218 the vf2_utils module was updated to use the
`PyDiGraph.neighbors_undirected()` method which was added in 0.16.0.
However that PR neglected to bump the minimum required version of
rustworkx to 0.16.0 from 0.15.0 which is the current minim version
listed. While we could bump the minimum version (see Qiskit#14507) to
rustworkx 0.16.0 using this method isn't strictly necessary and Qiskit#14218
was backported to stable branches and backporting a version bump is not
desireable. This commit instead just updates the rustworkx usage to use
APIs in 0.15.0.

This PR will need to be backported to stable/1.4 and stable/2.0 to fix
compatibility with the listed rustworkx requirement. However, in the
backport a fix note will be needed to document that the release fixes
compatibility with the listed requirement.
mtreinish added a commit to mtreinish/qiskit-core that referenced this pull request May 30, 2025
@mtreinish
Avoid using rustworkx 0.16.0 methods in vf2_utils
b3a5144 
In Qiskit#14218 the vf2_utils module was updated to use the
`PyDiGraph.neighbors_undirected()` method which was added in 0.16.0.
However that PR neglected to bump the minimum required version of
rustworkx to 0.16.0 from 0.15.0 which is the current minim version
listed. While we could bump the minimum version (see Qiskit#14507) to
rustworkx 0.16.0 using this method isn't strictly necessary and Qiskit#14218
was backported to stable branches and backporting a version bump is not
desireable. This commit instead just updates the rustworkx usage to use
A
8000
PIs in 0.15.0.

This PR will need to be backported to stable/1.4 and stable/2.0 to fix
compatibility with the listed rustworkx requirement. However, in the
backport a fix note will be needed to document that the release fixes
compatibility with the listed requirement.
@mtreinish mtreinish mentioned this pull request May 30, 2025
Merged
github-merge-queue bot pushed a commit that referenced this pull request Jun 4, 2025
@mtreinish
Avoid using rustworkx 0.16.0 methods in vf2_utils (#14513)
9aa1a29 
* Avoid using rustworkx 0.16.0 methods in vf2_utils

In #14218 the vf2_utils module was updated to use the
`PyDiGraph.neighbors_undirected()` method which was added in 0.16.0.
However that PR neglected to bump the minimum required version of
rustworkx to 0.16.0 from 0.15.0 which is the current minim version
listed. While we could bump the minimum version (see #14507) to
rustworkx 0.16.0 using this method isn't strictly necessary and #14218
was backported to stable branches and backporting a version bump is not
desireable. This commit instead just updates the rustworkx usage to use
APIs in 0.15.0.

This PR will need to be backported to stable/1.4 and stable/2.0 to fix
compatibility with the listed rustworkx requirement. However, in the
backport a fix note will be needed to document that the release fixes
compatibility with the listed requirement.

* Correctly handle duplicates across successors and predecessors
mergify bot pushed a commit that referenced this pull request Jun 4, 2025
@mtreinish @mergify
Avoid using rustworkx 0.16.0 methods in vf2_utils (#14513)
caf9939 
* Avoid using rustworkx 0.16.0 methods in vf2_utils

In #14218 the vf2_utils module was updated to use the
`PyDiGraph.neighbors_undirected()` method which was added in 0.16.0.
However that PR neglected to bump the minimum required version of
rustworkx to 0.16.0 from 0.15.0 which is the current minim version
listed. While we could bump the minimum version (see #14507) to
rustworkx 0.16.0 using this method isn't strictly necessary and #14218
was backported to stable branches and backporting a version bump is not
desireable. This commit instead just updates the rustworkx usage to use
APIs in 0.15.0.

This PR will need to be backported to stable/1.4 and stable/2.0 to fix
compatibility with the listed rustworkx requirement. However, in the
backport a fix note will be needed to document that the release fixes
compatibility with the listed requirement.

* Correctly handle duplicates across successors and predecessors

(cherry picked from commit 9aa1a29)
@mergify mergify bot mentioned this pull request Jun 4, 2025
Merged
mergify bot pushed a commit that referenced this pull request Jun 4, 2025
@mtreinish @mergify
Avoid using rustworkx 0.16.0 methods in vf2_utils (#14513)
6469ceb 
* Avoid using rustworkx 0.16.0 methods in vf2_utils

In #14218 the vf2_utils module was updated to use the
`PyDiGraph.neighbors_undirected()` method which was added in 0.16.0.
However that PR neglected to bump the minimum required version of
rustworkx to 0.16.0 from 0.15.0 which is the current minim version
listed. While we could bump the minimum version (see #14507) to
rustworkx 0.16.0 using this method isn't strictly necessary and #14218
was backported to stable branches and backporting a version bump is not
desireable. This commit instead just updates the rustworkx usage to use
APIs in 0.15.0.

This PR will need to be backported to stable/1.4 and stable/2.0 to fix
compatibility with the listed rustworkx requirement. However, in the
backport a fix note will be needed to document that the release fixes
compatibility with the listed requirement.

* Correctly handle duplicates across successors and predecessors

(cherry picked from commit 9aa1a29)
@mergify mergify bot mentioned this pull request Jun 4, 2025
Merged
github-merge-queue bot pushed a commit that referenced this pull request Jun 12, 2025
@mergify @mtreinish
Avoid using rustworkx 0.16.0 methods in vf2_utils (backport #14513) (#…
a7991d3 
…14533)

* Avoid using rustworkx 0.16.0 methods in vf2_utils (#14513)

* Avoid using rustworkx 0.16.0 methods in vf2_utils

In #14218 the vf2_utils module was updated to use the
`PyDiGraph.neighbors_undirected()` method which was added in 0.16.0.
However that PR neglected to bump the minimum required version of
rustworkx to 0.16.0 from 0.15.0 which is the current minim version
listed. While we could bump the minimum version (see #14507) to
rustworkx 0.16.0 using this method isn't strictly necessary and #14218
was backported to stable branches and backporting a version bump is not
desireable. This commit instead just updates the rustworkx usage to use
APIs in 0.15.0.

This PR will need to be backported to stable/1.4 and stable/2.0 to fix
compatibility with the listed rustworkx requirement. However, in the
backport a fix note will be needed to document that the release fixes
compatibility with the listed requirement.

* Correctly handle duplicates across successors and predecessors

(cherry picked from commit 9aa1a29)

* Add release note

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>
github-merge-queue bot pushed a commit that referenced this pull request Jun 12, 2025
@mergify @mtreinish
Avoid using rustworkx 0.16.0 methods in vf2_utils (backport #14513) (#…
d2ee4ba 
…14534)

* Avoid using rustworkx 0.16.0 methods in vf2_utils (#14513)

* Avoid using rustworkx 0.16.0 methods in vf2_utils

In #14218 the vf2_utils module was updated to use the
`PyDiGraph.neighbors_undirected()` method which was added in 0.16.0.
However that PR neglected to bump the minimum required version of
rustworkx to 0.16.0 from 0.15.0 which is the current minim version
listed. While we could bump the minimum version (see #14507) to
rustworkx 0.16.0 using this method isn't strictly necessary and #14218
was backported to stable branches and backporting a version bump is not
desireable. This commit instead just updates the rustworkx usage to use
APIs in 0.15.0.

This PR will need to be backported to stable/1.4 and stable/2.0 to fix
compatibility with the listed rustworkx requirement. However, in the
backport a fix note will be needed to document that the release fixes
compatibility with the listed requirement.

* Correctly handle duplicates across successors and predecessors

(cherry picked from commit 9aa1a29)

* Add release note

---------

Co-authored-by: Matthew Treinish <mtreinish@kortar.org>
rahaman-quantum pushed a commit to rahaman-quantum/qiskit that referenced this pull request Jun 20, 2025
@mtreinish @rahaman-quantum
Avoid using rustworkx 0.16.0 methods in vf2_utils (Qiskit#14513)
13235de 
* Avoid using rustworkx 0.16.0 methods in vf2_utils

In Qiskit#14218 the vf2_utils module was updated to use the
`PyDiGraph.neighbors_undirected()` method which was added in 0.16.0.
However that PR neglected to bump the minimum required version of
rustworkx to 0.16.0 from 0.15.0 which is the current minim version
listed. While we could bump the minimum version (see Qiskit#14507) to
rustworkx 0.16.0 using this method isn't strictly necessary and Qiskit#14218
was backported to stable branches and backporting a version bump is not
desireable. This commit instead just updates the rustworkx usage to use
APIs in 0.15.0.

This PR will need to be backported to stable/1.4 and stable/2.0 to fix
compatibility with the listed rustworkx requirement. However, in the
backport a fix note will be needed to document that the release fixes
compatibility with the listed requirement.

* Correctly handle duplicates across successors and predecessors
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@ElePT ElePT ElePT left review comments

@kevinhartman kevinhartman kevinhartman approved these changes

Assignees
No one assigned
Labels
Changelog: Bugfix Include in the "Fixed" section of the changelog mod: transpiler Issues and PRs related to Transpiler stable backport potential The bug might be minimal and/or import enough to be port to stable
Projects
None yet
Milestone
2.0.1
Development

Successfully merging this pull request may close these issues.
5 participants
@jakelishman @qiskit-bot @coveralls @kevinhartman @ElePT
0