Qiskit / qiskit

Qiskit is an open-source SDK for working with quantum computers at the level of extended quantum circuits, operators, and primitives.
https://www.ibm.com/quantum/qiskit
Apache License 2.0
5.28k stars 2.37k forks source link

Port `circuit_to_dag` to Rust #13036

Closed raynelfss closed 2 months ago

raynelfss commented 2 months ago

Is tracked by and resolves #13001 and #13004

Summary

These commits bring circuit_to_dag into rust, leveraging all of the api's introduced by #12550. This also resulted in the addition of a rust-native method. DAGCircuit::from_circuit_data to convert from CircuitData to DAGCircuit from Rust alone.

Details and comments

The following commits aim to add the circuit converter circuit_to_dag to rust while leveraging the rust-side logic for DAGCircuit. This is originally used to turn an instance of QuantumCircuit into DAGCircuit. A rust method to convert CircuitData to DAGCircuit was also added.

Inital changes

Tasks

Blockers

Questions and suggestions

Feel free to ask any questions and give any feedback below, thank you! 🚀

raynelfss commented 2 months ago

There are still some bugs to fix but so far benchmarks look promising for this:

All benchmarks:

| Change   | Before [cc87318f] <main>   | After [24df33df] <rusty-circ-to-dag>   | Ratio   | Benchmark (Parameter)                                        |
|----------|----------------------------|----------------------------------------|---------|--------------------------------------------------------------|
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(14, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(20, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(20, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(32, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(32, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(53, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(53, 8192) |
| -        | 17.3±0.2μs                 | 7.56±0.09μs                            | 0.44    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 8)     |
| -        | 29.3±0.4μs                 | 11.1±0.1μs                             | 0.38    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 8)     |
| -        | 11.9±0.1ms                 | 3.67±0.1ms                             | 0.31    | converters.ConverterBenchmarks.time_circuit_to_dag(53, 128)  |
| -        | 283±2μs                    | 84.9±0.4μs                             | 0.30    | converters.ConverterBenchmarks.time_circuit_to_dag(20, 8)    |
| -        | 191±0.8μs                  | 55.1±0.5μs                             | 0.29    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 8)    |
| -        | 62.3±0.2μs                 | 18.0±0.1μs                             | 0.29    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 8)     |
| -        | 882±10μs                   | 259±3μs                                | 0.29    | converters.ConverterBenchmarks.time_circuit_to_dag(53, 8)    |
| -        | 106±0.8μs                  | 30.4±0.4μs                             | 0.29    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 8)     |
| -        | 434±8μs                    | 120±2μs                                | 0.28    | converters.ConverterBenchmarks.time_circuit_to_dag(32, 8)    |
| -        | 169±3μs                    | 44.2±0.4μs                             | 0.26    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 128)   |
| -        | 34.5±0.3ms                 | 8.74±0.2ms                             | 0.25    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 2048) |
| -        | 6.00±0.03ms                | 1.50±0.03ms                            | 0.25    | converters.ConverterBenchmarks.time_circuit_to_dag(32, 128)  |
| -        | 9.80±0.2ms                 | 2.27±0.2ms                             | 0.23    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 8192)  |
| -        | 2.20±0ms                   | 502±6μs                                | 0.23    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 128)  |
| -        | 3.44±0.05ms                | 805±4μs                                | 0.23    | converters.ConverterBenchmarks.time_circuit_to_dag(20, 128)  |
| -        | 76.6±0.8ms                 | 17.3±0.3ms                             | 0.23    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 8192)  |
| -        | 2.44±0.01ms                | 531±4μs                                | 0.22    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 2048)  |
| -        | 18.5±0.1ms                 | 4.05±0.1ms                             | 0.22    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 2048)  |
| -        | 351±1μs                    | 72.6±1μs                               | 0.21    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 128)   |
| -        | 47.6±0.9ms                 | 9.96±0.4ms                             | 0.21    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 8192)  |
| -        | 1.24±0.01ms                | 260±5μs                                | 0.21    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 128)   |
| -        | 20.6±0.09ms                | 4.10±0.2ms                             | 0.20    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 8192)  |
| -        | 755±2μs                    | 147±0.08μs                             | 0.20    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 128)   |
| -        | 5.14±0.06ms                | 880±4μs                                | 0.17    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 2048)  |
| -        | 11.6±0.09ms                | 2.01±0.05ms                            | 0.17    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 2048)  |

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.
raynelfss commented 2 months ago

After fixing all of the failing tests, there was a bit of a performance regression (probably from cloning all the instructions, which I don't think is needed anymore if we do things through rust). But it's still faster than the original.

All benchmarks:

| Change   | Before [cc2edc9f] <main>   | After [7b765db2] <rusty-circ-to-dag>   | Ratio   | Benchmark (Parameter)                                        |
|----------|----------------------------|----------------------------------------|---------|--------------------------------------------------------------|
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(14, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(20, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(20, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(32, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(32, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(53, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(53, 8192) |
| -        | 17.2±0.1μs                 | 12.0±0.3μs                             | 0.70    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 8)     |
| -        | 61.4±0.3μs                 | 37.9±0.5μs                             | 0.62    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 8)     |
| -        | 190±1μs                    | 115±0.7μs                              | 0.61    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 8)    |
| -        | 29.2±0.3μs                 | 17.9±0.2μs                             | 0.61    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 8)     |
| -        | 277±0.3μs                  | 168±1μs                                | 0.61    | converters.ConverterBenchmarks.time_circuit_to_dag(20, 8)    |
| -        | 107±4μs                    | 65.0±1μs                               | 0.61    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 8)     |
| -        | 425±2μs                    | 243±8μs                                | 0.57    | converters.ConverterBenchmarks.time_circuit_to_dag(32, 8)    |
| -        | 20.6±0.1ms                 | 11.3±0.2ms                             | 0.55    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 8192)  |
| -        | 869±6μs                    | 459±1μs                                | 0.53    | converters.ConverterBenchmarks.time_circuit_to_dag(53, 8)    |
| -        | 34.4±2ms                   | 17.9±0.5ms                             | 0.52    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 2048) |
| -        | 48.5±0.8ms                 | 24.7±0.5ms                             | 0.51    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 8192)  |
| -        | 3.35±0.06ms                | 1.67±0.04ms                            | 0.50    | converters.ConverterBenchmarks.time_circuit_to_dag(20, 128)  |
| -        | 11.8±0.04ms                | 5.86±0.1ms                             | 0.50    | converters.ConverterBenchmarks.time_circuit_to_dag(53, 128)  |
| -        | 78.7±0.9ms                 | 39.5±0.6ms                             | 0.50    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 8192)  |
| -        | 363±8μs                    | 178±0.9μs                              | 0.49    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 128)   |
| -        | 5.84±0.06ms                | 2.84±0.05ms                            | 0.49    | converters.ConverterBenchmarks.time_circuit_to_dag(32, 128)  |
| -        | 2.23±0.1ms                 | 1.06±0.02ms                            | 0.48    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 128)  |
| -        | 11.9±0.3ms                 | 5.66±0.2ms                             | 0.48    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 2048)  |
| -        | 18.7±0.4ms                 | 8.94±0.3ms                             | 0.48    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 2048)  |
| -        | 10.5±0.2ms                 | 4.90±0.3ms                             | 0.47    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 8192)  |
| -        | 5.14±0.06ms                | 2.34±0.07ms                            | 0.46    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 2048)  |
| -        | 755±2μs                    | 349±2μs                                | 0.46    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 128)   |
| -        | 1.23±0.02ms                | 569±3μs                                | 0.46    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 128)   |
| -        | 168±2μs                    | 76.0±4μs                               | 0.45    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 128)   |
| -        | 2.52±0.05ms                | 976±9μs                                | 0.39    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 2048)  |

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.
qiskit-bot commented 2 months ago

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

coveralls commented 2 months ago

Pull Request Test Coverage Report for Build 10799042871

Details


Changes Missing Coverage Covered Lines Changed/Added Lines %
crates/circuit/src/dag_circuit.rs 125 154 81.17%
<!-- Total: 184 213 86.38% -->
Files with Coverage Reduction New Missed Lines %
qiskit/transpiler/passes/synthesis/unitary_synthesis.py 2 88.26%
crates/qasm2/src/lex.rs 3 91.73%
crates/circuit/src/dag_node.rs 4 80.24%
qiskit/synthesis/two_qubit/xx_decompose/decomposer.py 6 90.84%
crates/qasm2/src/parse.rs 24 95.77%
<!-- Total: 39 -->
Totals Coverage Status
Change from base Build 10796516797: 2.3%
Covered Lines: 73175
Relevant Lines: 82093

💛 - Coveralls
raynelfss commented 2 months ago

After @mtreinish suggestions, the copying of instructions one by one is more effective.

All benchmarks:

| Change   | Before [3d4bab2b] <main>   | After [7fe0a365] <rusty-circ-to-dag>   | Ratio   | Benchmark (Parameter)                                        |
|----------|----------------------------|----------------------------------------|---------|--------------------------------------------------------------|
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(14, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(20, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(20, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(32, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(32, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(53, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(53, 8192) |
| -        | 15.3±0.05μs                | 7.85±0.2μs                             | 0.51    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 8)     |
| -        | 26.1±0.1μs                 | 11.7±0.03μs                            | 0.45    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 8)     |
| -        | 147±2μs                    | 61.3±0.3μs                             | 0.42    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 8)    |
| -        | 222±5μs                    | 93.4±0.4μs                             | 0.42    | converters.ConverterBenchmarks.time_circuit_to_dag(20, 8)    |
| -        | 81.7±0.8μs                 | 33.2±0.2μs                             | 0.41    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 8)     |
| -        | 50.0±0.1μs                 | 20.2±0.07μs                            | 0.40    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 8)     |
| -        | 346±1μs                    | 130±0.4μs                              | 0.38    | converters.ConverterBenchmarks.time_circuit_to_dag(32, 8)    |
| -        | 703±4μs                    | 271±0.7μs                              | 0.38    | converters.ConverterBenchmarks.time_circuit_to_dag(53, 8)    |
| -        | 9.38±0.08ms                | 3.23±0.02ms                            | 0.34    | converters.ConverterBenchmarks.time_circuit_to_dag(53, 128)  |
| -        | 4.38±0.02ms                | 1.38±0.01ms                            | 0.32    | converters.ConverterBenchmarks.time_circuit_to_dag(32, 128)  |
| -        | 2.46±0.02ms                | 719±3μs                                | 0.29    | converters.ConverterBenchmarks.time_circuit_to_dag(20, 128)  |
| -        | 1.57±0.01ms                | 436±4μs                                | 0.28    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 128)  |
| -        | 145±4μs                    | 38.7±0.3μs                             | 0.27    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 128)   |
| -        | 24.4±0.1ms                 | 6.38±0.2ms                             | 0.26    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 2048) |
| -        | 240±1μs                    | 63.5±0.4μs                             | 0.26    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 128)   |
| -        | 867±1μs                    | 226±1μs                                | 0.26    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 128)   |
| -        | 531±0.6μs                  | 129±0.3μs                              | 0.24    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 128)   |
| -        | 52.1±0.3ms                 | 11.9±0.2ms                             | 0.23    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 8192)  |
| -        | 2.13±0.04ms                | 446±4μs                                | 0.21    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 2048)  |
| -        | 8.46±0.2ms                 | 1.76±0.04ms                            | 0.21    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 8192)  |
| -        | 13.1±0.08ms                | 2.78±0.01ms                            | 0.21    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 2048)  |
| -        | 3.54±0.06ms                | 718±2μs                                | 0.20    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 2048)  |
| -        | 13.8±0.07ms                | 2.71±0.02ms                            | 0.20    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 8192)  |
| -        | 7.86±0.06ms                | 1.55±0.01ms                            | 0.20    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 2048)  |
| -        | 31.6±0.2ms                 | 6.44±0.03ms                            | 0.20    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 8192)  |

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.
raynelfss commented 2 months ago
All benchmarks:

| Change   | Before [3d4bab2b] <main>   | After [94f8ab42] <rusty-circ-to-dag>   | Ratio   | Benchmark (Parameter)                                        |
|----------|----------------------------|----------------------------------------|---------|--------------------------------------------------------------|
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(14, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(20, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(20, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(32, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(32, 8192) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(53, 2048) |
|          | n/a                        | n/a                                    | n/a     | converters.ConverterBenchmarks.time_circuit_to_dag(53, 8192) |
| -        | 15.0±0.4μs                 | 7.02±0.02μs                            | 0.47    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 8)     |
| -        | 25.6±0.2μs                 | 10.9±0.09μs                            | 0.43    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 8)     |
| -        | 217±0.6μs                  | 88.0±0.2μs                             | 0.41    | converters.ConverterBenchmarks.time_circuit_to_dag(20, 8)    |
| -        | 82.3±2μs                   | 33.0±2μs                               | 0.40    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 8)     |
| -        | 145±0.7μs                  | 56.4±0.4μs                             | 0.39    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 8)    |
| -        | 49.5±0.4μs                 | 18.8±0.3μs                             | 0.38    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 8)     |
| -        | 342±10μs                   | 123±1μs                                | 0.36    | converters.ConverterBenchmarks.time_circuit_to_dag(32, 8)    |
| -        | 711±1μs                    | 259±5μs                                | 0.36    | converters.ConverterBenchmarks.time_circuit_to_dag(53, 8)    |
| -        | 9.27±0.07ms                | 2.95±0.04ms                            | 0.32    | converters.ConverterBenchmarks.time_circuit_to_dag(53, 128)  |
| -        | 4.39±0.03ms                | 1.34±0.02ms                            | 0.31    | converters.ConverterBenchmarks.time_circuit_to_dag(32, 128)  |
| -        | 2.43±0.01ms                | 689±3μs                                | 0.28    | converters.ConverterBenchmarks.time_circuit_to_dag(20, 128)  |
| -        | 1.58±0.02ms                | 417±1μs                                | 0.26    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 128)  |
| -        | 145±1μs                    | 34.8±0.2μs                             | 0.24    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 128)   |
| -        | 24.1±0.1ms                 | 5.68±0.03ms                            | 0.24    | converters.ConverterBenchmarks.time_circuit_to_dag(14, 2048) |
| -        | 236±2μs                    | 57.1±0.3μs                             | 0.24    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 128)   |
| -        | 883±6μs                    | 216±3μs                                | 0.24    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 128)   |
| -        | 529±3μs                    | 119±0.5μs                              | 0.22    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 128)   |
| -        | 51.6±0.4ms                 | 10.9±0.2ms                             | 0.21    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 8192)  |
| -        | 8.17±0.05ms                | 1.61±0.03ms                            | 0.20    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 8192)  |
| -        | 13.3±0.2ms                 | 2.66±0.04ms                            | 0.20    | converters.ConverterBenchmarks.time_circuit_to_dag(8, 2048)  |
| -        | 2.06±0.01ms                | 395±6μs                                | 0.19    | converters.ConverterBenchmarks.time_circuit_to_dag(1, 2048)  |
| -        | 31.6±0.3ms                 | 5.98±0.07ms                            | 0.19    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 8192)  |
| -        | 3.51±0.03ms                | 648±4μs                                | 0.18    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 2048)  |
| -        | 13.8±0.2ms                 | 2.42±0.02ms                            | 0.18    | converters.ConverterBenchmarks.time_circuit_to_dag(2, 8192)  |
| -        | 7.84±0.08ms                | 1.41±0.01ms                            | 0.18    | converters.ConverterBenchmarks.time_circuit_to_dag(5, 2048)  |

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.

After @mtreinish 's suggestions there was a slight performance increase.