Skip to content

Fix RNG-compatibility of Sabre for large sizes #12172

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
Apr 12, 2024
Merged

Fix RNG-compatibility of Sabre for large sizes #12172

merged 1 commit into from
Apr 12, 2024

Conversation

jakelishman
Copy link
Member

Summary

The recent Sabre refactor (gh-11977, 3af3cf5) inadvertently switched the order that physical qubits were considered when modifying the front layer after a swap insertion. This could occasionally have an impact in the swap-chooser and extended-set population, if a swap enabled two separate gates at once.

Details and comments

The reason that this changed is that before #11977 we looked at the two physical qubits of the swap in this order, but before we swapped them. After #11977 we look at them afterwards, so to maintain RNG compatibility, we should look at them in the reverse order.

ASV flagged modifications in the depths and sizes (and mostly corresponding changes in the timings) following #11977 that were unexpected. Timing the large-scale passes on my laptop is a little volatile because of other stuff it's doing and thermal throttling, but I can easily verify that this PR fixes the RNG variance.

Commit 4ff0fa2 is main before #11977. Commit 3af3cf5 is #11977. Commit 902557f is this PR. I ran the LargeQuantumVolume benches and the QUEKO benches (which are in the changed set), and first up we can reproduce the changes caused by #11977:

       before           after         ratio
     [4ff0fa2f]       [3af3cf58]
     <var/qpy~3>       <var/qpy~2>
-             547              495     0.90  quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(115, 10, 'lookahead')
-        456±30ms          346±5ms     0.76  queko.QUEKOTranspilerBench.time_transpile_bss(2, 'sabre')
-             672              499     0.74  queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(0, 'sabre')
-             394              348     0.88  queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(1, 'sabre')
-             836              684     0.82  queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(0, 'sabre')
-             370              314     0.85  queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(1, 'sabre')
       before           after         ratio
     [4ff0fa2f]       [3af3cf58]
     <var/qpy~3>       <var/qpy~2>
+      2.31±0.01s        3.10±0.1s     1.34  quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(1081, 10, 'lookahead')
+         364±4ms         512±20ms     1.40  quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(409, 10, 'decay')
+            2955             3527     1.19  quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(409, 10, 'decay')
+          217448           251736     1.16  quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(1081, 10, 'decay')
+           42115            46814     1.11  quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(409, 10, 'decay')
+        554±30ms         696±30ms     1.26  queko.QUEKOTranspilerBench.time_transpile_bntf(3, 'sabre')
+             299              384     1.28  queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(2, 'sabre')
+             200              224     1.12  queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(3, 'sabre')
+             261              290     1.11  queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(3, 'sabre')

Then we can see that the diff from #11977 to this PR inverts that:

       before           after         ratio
     [3af3cf58]       [902557f265]
     <var/qpy~2>
-       3.10±0.1s       2.42±0.01s     0.78  quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(1081, 10, 'lookahead')
-        512±20ms          380±8ms     0.74  quantum_volume.LargeQuantumVolumeMappingTimeBench.time_sabre_swap(409, 10, 'decay')
-            3527             2955     0.84  quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(409, 10, 'decay')
-          251736           217448     0.86  quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(1081, 10, 'decay')
-           46814            42115     0.90  quantum_volume.LargeQuantumVolumeMappingTrackBench.track_size_sabre_swap(409, 10, 'decay')
-        374±30ms          328±3ms     0.88  queko.QUEKOTranspilerBench.time_transpile_bntf(2, 'sabre')
-        696±30ms         513±10ms     0.74  queko.QUEKOTranspilerBench.time_transpile_bntf(3, 'sabre')
-         743±7ms          655±6ms     0.88  queko.QUEKOTranspilerBench.time_transpile_bss(3, 'sabre')
-             384              299     0.78  queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(2, 'sabre')
-             224              200     0.89  queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(3, 'sabre')
-             290              261     0.90  queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(3, 'sabre')
       before           after         ratio
     [3af3cf58]       [90ef7f28]
     <var/qpy~2>
+             495              547     1.11  quantum_volume.LargeQuantumVolumeMappingTrackBench.track_depth_sabre_swap(115, 10, 'lookahead')
+         346±5ms          406±6ms     1.17  queko.QUEKOTranspilerBench.time_transpile_bss(2, 'sabre')
+             499              672     1.35  queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(0, 'sabre')
+             348              394     1.13  queko.QUEKOTranspilerBench.track_depth_bntf_optimal_depth_25(1, 'sabre')
+             684              836     1.22  queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(0, 'sabre')
+             314              370     1.18  queko.QUEKOTranspilerBench.track_depth_bss_optimal_depth_100(1, 'sabre')

and then finally the diff between 4ff0fa2 and this PR shows no change.

@jakelishman
Fix RNG-compatibility of Sabre for large sizes
902557f 
The recent Sabre refactor (Qiskitgh-11977, 3af3cf5) inadvertently switched
the order that physical qubits were considered when modifying the front
layer after a swap insertion. This could occasionally have an impact in
the swap-chooser and extended-set population, if a swap enabled two
separate gates at once.
@jakelishman jakelishman added Changelog: None Do not include in changelog Rust This PR or issue is related to Rust code in the repository mod: transpiler Issues and PRs related to Transpiler labels Apr 12, 2024
@jakelishman jakelishman added this to the 1.1.0 milestone Apr 12, 2024
@jakelishman jakelishman requested a review from a team as a code owner April 12, 2024 13:14
@qiskit-bot
Copy link
Collaborator

One or more of the the following people are requested to review this:

@jakelishman jakelishman mentioned this pull request Apr 12, 2024
Merged
@coveralls
Copy link

Pull Request Test Coverage Report for Build 8662659116

Details

  • 2 of 2 (100.0%) changed or added relevant lines in 1 file are covered.
  • 5 unchanged lines in 1 file lost coverage.
  • Overall coverage increased (+0.003%) to 89.365%
Files with Coverage Reduction New Missed Lines %
crates/qasm2/src/lex.rs 5 92.37%
Totals Coverage Status
Change from base Build 8653934653: 0.003%
Covered Lines: 60171
Relevant Lines: 67332
💛 - Coveralls

@jakelishman jakelishman mentioned this pull request Apr 12, 2024
Merged
mtreinish
mtreinish approved these changes Apr 12, 2024
View reviewed changes
Copy link
Member

@mtreinish mtreinish left a comment

Choose a reason for hiding this comment

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

LGTM, nice find digging this up.

@mtreinish mtreinish enabled auto-merge April 12, 2024 14:21
@mtreinish mtreinish added this pull request to the merge queue Apr 12, 2024
Merged via the queue into Qiskit:main with commit eed5388 Apr 12, 2024
@jakelishman jakelishman deleted the sabre/fix-rng branch April 12, 2024 15:25
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@mtreinish mtreinish mtreinish approved these changes

Assignees
No one assigned
Labels
Changelog: None Do not include in changelog mod: transpiler Issues and PRs related to Transpiler Rust This PR or issue is related to Rust code in the repository
Projects
None yet
Milestone
1.1.0
Development

Successfully merging this pull request may close these issues.
4 participants
@jakelishman @qiskit-bot @coveralls @mtreinish