Add random circuit with graph #12474

MozammilQ · 2024-05-29T00:50:31Z

Summary

The function qiskit.circuit.random.utils.random_circuit_from_graph adds a new feature
of generating random circuits with interaction graph.

Details and comments

qiskit-bot · 2024-05-29T00:50:36Z

Thank you for opening a new pull request.

Before your PR can be merged it will first need to pass continuous integration tests and be reviewed. Sometimes the review process can be slow, so please be patient.

While you're waiting, please feel free to review other open PRs. While only a subset of people are authorized to approve pull requests for merging, everyone is encouraged to review open pull requests. Doing reviews helps reduce the burden on the core team and helps make the project's code better for everyone.

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

@Qiskit/terra-core

coveralls · 2024-05-29T01:11:52Z

Pull Request Test Coverage Report for Build 14320951686

Details

135 of 138 (97.83%) changed or added relevant lines in 2 files are covered.
5 unchanged lines in 1 file lost coverage.
Overall coverage increased (+0.02%) to 88.17%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/circuit/random/utils.py	134	137	97.81%

Files with Coverage Reduction	New Missed Lines	%
crates/qasm2/src/lex.rs	5	91.48%

Totals
Change from base Build 14318441199:	0.02%
Covered Lines:	73619
Relevant Lines:	83497

💛 - Coveralls

sbrandhsn · 2024-05-29T13:11:03Z

Dear @MozammilQ thanks for showing interest in this issue. I will be on vacation and look into this PR next week! In the meantime make yourself familiar with https://github.com/Qiskit/qiskit/blob/main/CONTRIBUTING.md and the unitaryhack rules (if you have not already). :-)

MozammilQ

I have added the suggestions :)

MozammilQ · 2024-06-03T13:39:17Z

@sbrandhsn , please see if this is good enough :)

sbrandhsn · 2024-06-04T16:44:21Z

@MozammilQ thanks for your interest in looking at issue #12364 ! I agree this issue is a bit tricky but I think your contribution is going into the right direction. :-) Also, thanks for exploring different options for that issue!

I did not have time yet to look into your code but wanted to spend the time to clarify some of your questions. To give a little bit of context, the output of this procedure will likely not be executed directly on a quantum computer but will prove valuable for investigating compiler capabilities and efficiencies. The problem I wanted to fix with the depth parameter is that the given input graph may not be observed by random_circuit_from_graph otherwise. Likely the name of depth is not optimal and should be replaced by something like min_2q_gate_per_edge.

You rightfully noted that the generated circuits may become quite large but I think this is fine. I suspect that if you have N edges in the input graph and uniformly draw 10*N random edges from your input graph, you are pretty much guaranteed to have drawn every edge at least one. While this implies that the circuit depth of the random circuit can be 10*N occasionally, the circuit depth should be much smaller in practice, depending on the structure of the input graph. If an user decides to assign non-uniform weights to the input graph edges, they will need to accept that the returned random circuit will be deeper.

I think it would be a good idea to raise an error with a reasonable error message if some of the edge weights are none while others are not none. If all edge weights are none, you can assume the weight of each edge to be 1/N.

With respects to resets and conditional operations, you can simply follow the approach given in the original random_circuit function, i.e. meaning make some operations conditional with some probability and regard resets as single-qubit gates.

Some of your 'reviewer markers' should actually be comments in your code, it would be great if you add those as you see fit. :-)

I think the implementation should eventually consider the edge weight as well as consider the depth/min_2q_gate_per_edge parameter, e.g. guarantee that the returned random circuit actually has the interaction graph specified by interaction_graph when depth/min_2q_gate_per_edge is set to one.

I like the idea to fill unused qubits in a layer with a single-qubit gate if insert_1q_oper is set and otherwise do not use single-qubit gates at all. However, a layer should consist of multiple two-qubit gates (even though the number of two-qubit gates does not have be maximal in each layer). You are also right about max_operands - it is confusing in the way the issue is currently stated. In the future, one might want to include 3-qubit or 4-qubit gates but currently for this issue only two-qubit gates and optional single-qubit gates should be used.

Let me know if things became clearer and whether you require any other information. Also, if you make modifications to your PR, let me know for which implementation you went for eventually. :-)

MozammilQ · 2024-06-04T22:49:09Z

I have already worked a lot on this PR, so I will surely do some modifications to the code, but, actually right now bit busy in "IBM Quantum Challenge 2024"
will come back to it, after 4 days :)

@sbrandhsn , you explained it very very well, thanks a lot for the time you gave to write and explain these.

sbrandhsn · 2024-06-05T07:24:50Z

Absolutely! :-)

MozammilQ · 2024-06-10T10:47:14Z

This is python so, focus is on code readability.
Therefore, I am leaving some code repetetions deliberately :)

@sbrandhsn , please have a look, and let me know what to change.
I think reading the docstring will suffice for the explanation of the way the logic works in this PR.

sbrandhsn

Thanks @MozammilQ, this already looks like it is in good shape! :-) I left a couple of comments. I also think there should be a couple of more test cases with different types of interaction graphs such as sparse graphs, (almost) fully connected and a couple more random ones. Also, I think it would be best if you reused the code in other test cases instead of copying them. See https://networkx.org/documentation/stable/reference/generators.html for how to generate these graphs.

qiskit/circuit/random/utils.py

releasenotes/notes/Added-random-circuit-from-graph-95c22eeabdea89d0.yaml

test/python/circuit/test_random_circuit.py

sbrandhsn · 2024-06-12T10:33:20Z

test/python/circuit/test_random_circuit.py

+        for wire in dag.wires:
+            for dag_op_node in dag.nodes_on_wire(wire, only_ops=True):
+                if dag_op_node.op.num_qubits == 2:
+                    control, target = dag_op_node.qargs
+                    control_idx = control._index
+                    target_idx = target._index
+                    cp_mp.update({(control_idx, target_idx)})
+
+        # make sure every qubit-pair from the circuit actually present in the edge_list
+        for cp in cp_mp:
+            self.assertTrue(cp in edge_list)


You can replace this chunk of code by build_interaction_graph in https://github.com/Qiskit/qiskit/blob/main/qiskit/transpiler/passes/layout/vf2_utils.py and a subgraph isomorphism check. :-)

I have kept the logic untouched, because for some reasons build_interaction_graph is giving out a coupling map, which is not correct for the given circuit.
On visual inspection, it was confirmed that the coupling map given out by this logic is indeed correct and serve the purpose.

test/python/circuit/test_random_circuit.py

qiskit/circuit/random/utils.py

MozammilQ · 2025-01-31T13:45:16Z

@eliarbel , I have done with the changes, please do have a look :)

Regarding testing: I'm missing some validation related to the probabilities aspect.
Can you come up with a test(s) (possibly using a fixed seed) to make sure 2Q
gate distribution is within a reasonable expectancy w.r.t to the input probabilities?

Performance: for very large circuits, how is the random_circuit_from_graph
performance compared to random_circuit?

The test has been added in 6e7ede8

Below is the performance comparison :)
I am comparing the performance based on time taken to generate same number of operations.

from qiskit.circuit.random import random_circuit_from_graph, random_circuit
import numpy as np
import rustworkx as rx
import time

distance = 5
h_h_g = rx.generators.directed_heavy_hex_graph(d=distance, bidirectional = False)
seed = 32434
rng = np.random.default_rng(seed = seed)
cp_map_list = []
edge_list = h_h_g.edge_list()

# generating a non-normalized list of integers.
random_probs = rng.choice(range(10, 25), size = len(edge_list)).tolist()
sum_probs = sum(random_probs)

for idx, qubits in enumerate(edge_list):
    ctrl, trgt = qubits
    cp_map_list.append((ctrl, trgt, random_probs[idx]))

h_h_g.clear_edges()
h_h_g.add_edges_from(cp_map_list)

start_time = time.time()
qc = random_circuit_from_graph(h_h_g,
                               min_2q_gate_per_edge = 10,
                               max_operands = 2,
                               measure = True,
                               conditional = True, # Just making it a bit more challenging.
                               reset = True,
                               seed = seed,
                               insert_1q_oper = True,
                               prob_conditional = 0.91,
                               prob_reset = 0.50)
end_time = time.time()
count_oper = sum(qc.count_ops().values())
print(f"For `random_circuit_from_graph`:\nTime taken: {end_time - start_time} to generate {count_oper} operations")
print(f"Time taken per operation: {(end_time-start_time)/count_oper*1000000} us\n", 40*'#', '\n')

rand_start_time = time.time()
qc_rand = random_circuit(num_qubits = 70, depth = 299, max_operands = 2, measure = True, conditional = True, reset = True, seed = seed)
rand_end_time = time.time()
count_rand_oper = sum(qc_rand.count_ops().values())
print(f"For `random_circuit`:\nTime taken: {rand_end_time-rand_start_time} to generate {count_rand_oper} operations")
print(f"Time taken per operation: {(rand_end_time-rand_start_time)/count_rand_oper*1000000} us")

Output

For `random_circuit_from_graph`:
Time taken: 18.229220867156982 to generate 151169 operations
Time taken per operation: 120.58835387650234 us
 ######################################## 

For `random_circuit`:
Time taken: 18.196982622146606 to generate 151748 operations
Time taken per operation: 119.91579870671512 us

eliarbel

Thanks @MozammilQ for addressing the comments in the previous review, I think it was a big step forward. Now with random_circuit almost back to its original state, I gave a more thorough look at the other parts. Please see my line comments. I hope this will be the last round of changes before we can merge the PR.

Regarding your performance comparison, it was helpful. It does help with getting a rough sense for the scaling of random_circuit_from_graph compared to random_circuit. If we want at some point to get a better understanding of it, we'll need to explore the parameter space more rigorously. For example, I played with your code a bit and got this:

qc = random_circuit_from_graph(h_h_g,
                               min_2q_gate_per_edge = 90,
                               max_operands = 2,
                               measure = True,
                               conditional = False, # Just making it a bit more challenging.
                               reset = False,
                               seed = seed,
                               insert_1q_oper = True)

qc_rand = random_circuit(num_qubits = 70, depth = 298, max_operands = 2, measure = True, conditional = False, reset = False, seed = seed)

# For `random_circuit_from_graph`:
# Time taken: 1.6271507740020752 to generate 19729 operations
# Time taken per operation: 82.47507597962772 us
#  ########################################

# For `random_circuit`:
# Time taken: 0.5127830505371094 to generate 19067 operations
# Time taken per operation: 26.893745766880443 us

But still it's good to have some sense that the new function is not too far off. I've left a couple optimization suggestions that might help but I wouldn't go beyond that in this PR trying to optimize performance more. We can handle this aspect in a new PR if there will be a use-case for which performance becomes a bottleneck.

qiskit/circuit/__init__.py

releasenotes/notes/Added-random-circuit-from-graph-95c22eeabdea89d0.yaml

qiskit/circuit/random/__init__.py

qiskit/circuit/random/utils.py

eliarbel · 2025-03-29T10:55:44Z

test/python/circuit/test_random_circuit.py

@@ -75,13 +80,14 @@ def test_random_mid_circuit_measure_conditional(self):
        circ = random_circuit(num_qubits, depth, conditional=True, seed=16)
        self.assertEqual(circ.width(), 2 * num_qubits)
        op_names = [instruction.operation.name for instruction in circ]
+        self.assertEqual(4, len(op_names))


What changed in random_circuit that requires this change?

Referring to test.python.circuit.test_random_circuit.TestCircuitRandom.test_random_mid_circuit_measure_conditional

qc.append leads to the following result.

For this code:

from qiskit.circuit.random import random_circuit num_qubits = depth = 2 circ = random_circuit(num_qubits, depth, conditional=True, seed=16) for instr in circ._data: print(instr)

CircuitInstruction(operation=Instruction(name='ry', num_qubits=1, num_clbits=0, params=[np.float64(3.9050564582327985)]), qubits=(<Qubit register=(2, "q"), index=0>,), clbits=()) CircuitInstruction(operation=Instruction(name='measure', num_qubits=1, num_clbits=1, params=[]), qubits=(<Qubit register=(2, "q"), index=0>,), clbits=(<Clbit register=(2, "c"), index=0>,)) CircuitInstruction(operation=Instruction(name='measure', num_qubits=1, num_clbits=1, params=[]), qubits=(<Qubit register=(2, "q"), index=1>,), clbits=(<Clbit register=(2, "c"), index=1>,)) CircuitInstruction(operation=Instruction(name='if_else', num_qubits=2, num_clbits=2, params=[<qiskit.circuit.quantumcircuit.QuantumCircuit object at 0x7d9dfe398710>, None]), qubits=(<Qubit register=(2, "q"), index=1>, <Qubit register=(2, "q"), index=0>), clbits=(<Clbit register=(2, "c"), index=0>, <Clbit register=(2, "c"), index=1>))

circ.draw(output='mpl')

len(op_names)

Gives: 4

Now, qc._append on the same code

For this code:

from qiskit.circuit.random import random_circuit num_qubits = depth = 2 circ = random_circuit(num_qubits, depth, conditional=True, seed=16) for instr in circ._data: print(instr)

CircuitInstruction(operation=Instruction(name='ry', num_qubits=1, num_clbits=0, params=[np.float64(3.9050564582327985)]), qubits=(<Qubit register=(2, "q"), index=0>,), clbits=()) CircuitInstruction(operation=Instruction(name='measure', num_qubits=1, num_clbits=1, params=[]), qubits=(<Qubit register=(2, "q"), index=0>,), clbits=(<Clbit register=(2, "c"), index=0>,)) CircuitInstruction(operation=Instruction(name='measure', num_qubits=1, num_clbits=1, params=[]), qubits=(<Qubit register=(2, "q"), index=1>,), clbits=(<Clbit register=(2, "c"), index=1>,)) CircuitInstruction(operation=Instruction(name='cs', num_qubits=2, num_clbits=0, params=[]), qubits=(<Qubit register=(2, "q"), index=1>, <Qubit register=(2, "q"), index=0>), clbits=()) CircuitInstruction(operation=Instruction(name='if_else', num_qubits=0, num_clbits=2, params=[<qiskit.circuit.quantumcircuit.QuantumCircuit object at 0x704da052f470>, None]), qubits=(), clbits=(<Clbit register=(2, "c"), index=0>, <Clbit register=(2, "c"), index=1>))

Noticed, the problem?

for instr in circ._data: print(instr.operation.num_qubits)

Gives

1 1 1 2 0

circ.draw(output='mpl')

len(op_names)

Gives: 5

The above observation suggests that may be not in the future but at present we should go with qc.append.

Regarding the speed, qc.append looks ~x2 slower than qc._append.

Ah... this was a good catch! So QuantumCircuit._append could not be used within a control-flow builder context (e.g. within with qc.if_test) since it doesn't look at the current circuit scope, effectively ignoring the control-flow scope here. This is why we don't see the if test surrounding the CS gate.
So let's keep the qc.append inside all the control-flow build contexts here and use qc._append elsewhere. You can also do this in random_circuit_with_graph for an enhanced performance.

test/python/circuit/test_random_circuit.py

MozammilQ · 2025-04-02T10:57:09Z

Regarding performance code in the comment
Changed distance from 7 to 17
Changed min_2q_gate_per_edge from 90 to 200
Changed num_qubits from 70 to 600
and, depth from 298 to 620

After change in the logic comment
It seems like there is a x2 performance gain,

After building rust in release mode

from qiskit.circuit.random import random_circuit_from_graph, random_circuit
import numpy as np
import rustworkx as rx
import time

distance = 17
h_h_g = rx.generators.directed_heavy_hex_graph(d=distance, bidirectional = False)
seed = 32434
rng = np.random.default_rng(seed = seed)
cp_map_list = []
edge_list = h_h_g.edge_list()

# generating a non-normalized list of integers.
random_probs = rng.choice(range(10, 25), size = len(edge_list)).tolist()
sum_probs = sum(random_probs)

for idx, qubits in enumerate(edge_list):
    ctrl, trgt = qubits
    cp_map_list.append((ctrl, trgt, random_probs[idx]))

h_h_g.clear_edges()
h_h_g.add_edges_from(cp_map_list)

start_time = time.time()
qc = random_circuit_from_graph(h_h_g,
                               min_2q_gate_per_edge = 200,
                               max_operands = 2,
                               measure = True,
                               conditional = False, 
                               reset = False,
                               seed = seed,
                               insert_1q_oper = True)

end_time = time.time()
count_oper = sum(qc.count_ops().values())
print(f"For `random_circuit_from_graph`:\nTime taken: {end_time - start_time} to generate {count_oper} operations")
print(f"Time taken per operation: {(end_time-start_time)/count_oper*1000000} us\n", 40*'#', '\n')

rand_start_time = time.time()
qc_rand = random_circuit(num_qubits = 600, depth = 620, max_operands = 2, measure = True, conditional = False, reset = False, seed = seed)
rand_end_time = time.time()
count_rand_oper = sum(qc_rand.count_ops().values())
print(f"For `random_circuit`:\nTime taken: {rand_end_time-rand_start_time} to generate {count_rand_oper} operations")
print(f"Time taken per operation: {(rand_end_time-rand_start_time)/count_rand_oper*1000000} us")

For `random_circuit_from_graph`:
Time taken: 12.82305383682251 to generate 369606 operations
Time taken per operation: 34.69384651986848 us
 ######################################## 

For `random_circuit`:
Time taken: 6.758020639419556 to generate 339428 operations
Time taken per operation: 19.91002698486735 us

random_circuit_from_graph here with its parameters looks ~x1.6 slower than random_circuit, the observation remains consistent with the size of the circuit generated.

For logic change see comment
For qc.append see comment

Please, see if the changes are good enough :)
@eliarbel

eliarbel

Thanks @MozammilQ for making all the changes. Looks good!
Regarding the qc.append comment, please see my response here. Let's apply it and we're done.

qiskit/circuit/random/__init__.py

MozammilQ · 2025-04-07T12:39:05Z

After 53f7628
Roughly speaking there is a performance gain of ~1.6x seen in case of both random_circuit and random_circuit_from_graph, and their relative speed difference stands roughly the same. Of-course the observation varies with different seed.
@eliarbel , applied your suggestions :)

MozammilQ · 2025-04-08T00:22:49Z

@eliarbel , I was curious enough to update the branch, I hope I didn't mess up anything :)

eliarbel

This is ready, thanks @MozammilQ for your contribution!

@brandhsn

All comments by @brandhsn have been addressed but one regarding some unit test, which seems not critical for blocking this PR from being merged.

MozammilQ added 4 commits May 29, 2024 00:19

Added random_circuit_with_graph

fd31959

added tests

e173505

added release note

f0b3e5a

lint

81a5207

MozammilQ requested a review from a team as a code owner May 29, 2024 00:50

qiskit-bot added the Community PR PRs from contributors that are not 'members' of the Qiskit repo label May 29, 2024

MozammilQ mentioned this pull request May 29, 2024

Generation of Random Circuits with Pre-Defined Inter-Qubit Connectivity #12364

Closed

MozammilQ added 3 commits May 29, 2024 01:31

fix docs lint

7238cac

fix lint

7195850

refactor code;lint

69f7824

sbrandhsn self-assigned this May 29, 2024

1ucian0 added the unitaryhack Issues/PR participating (now or in the past) in the UnitaryHack event see https://unitaryhack.dev/ label May 29, 2024

MozammilQ added 2 commits May 29, 2024 23:33

refactor code;lint

940eed5

refactor code;lint

692b052

MozammilQ commented Jun 3, 2024

View reviewed changes

refactor code; added suggestions

aca4e1a

MozammilQ and others added 4 commits June 10, 2024 16:27

Merge branch 'main' into add_random_circuit_with_graph

b359f6a

fix weird merge conflict

aa5bf41

edit docstrings; fix typos

79efdf5

added a test;fixed lint

4c69570

sbrandhsn requested changes Jun 12, 2024

View reviewed changes

sbrandhsn reviewed Jun 13, 2024

View reviewed changes

qiskit/circuit/random/utils.py Outdated Show resolved Hide resolved

MozammilQ added 2 commits January 31, 2025 07:56

fixed releasenote; added test to validate probs

6e7ede8

added support of cp_map; fixed lint

eab2a4c

Merge branch 'Qiskit:main' into add_random_circuit_with_graph

7cb79aa

sbrandhsn removed their assignment Feb 3, 2025

MozammilQ and others added 4 commits February 5, 2025 10:20

refactor code

aabacb9

Merge branch 'main' into add_random_circuit_with_graph

7c1cca7

Merge branch 'main' into add_random_circuit_with_graph

9d74c1d

removed c_if dependency

03a68c3

eliarbel requested changes Mar 29, 2025

View reviewed changes

MozammilQ and others added 3 commits April 1, 2025 22:46

applied Eli Arbel's suggestion

30647c7

fixed renormalization, typo

ed963dd

Merge branch 'main' into add_random_circuit_with_graph

be572a2

refactor code; optimized test

8e84db7

eliarbel requested changes Apr 7, 2025

View reviewed changes

eliarbel reviewed Apr 7, 2025

View reviewed changes

qiskit/circuit/random/__init__.py Outdated Show resolved Hide resolved

applied Eli Arbel's suggestions

53f7628

eliarbel and others added 2 commits April 7, 2025 17:52

Merge branch 'main' into add_random_circuit_with_graph

e99e967

Merge branch 'Qiskit:main' into add_random_circuit_with_graph

b4fe737

eliarbel approved these changes Apr 8, 2025

View reviewed changes

eliarbel added this pull request to the merge queue Apr 8, 2025

Merged via the queue into Qiskit:main with commit 45ee089 Apr 8, 2025
24 checks passed

github-project-automation bot moved this to Done in Contributor Monitoring Apr 8, 2025

eliarbel added this to the 2.1.0 milestone Jun 3, 2025

eliarbel added the Changelog: New Feature Include in the "Added" section of the changelog label Jun 3, 2025

Add random circuit with graph #12474

Add random circuit with graph #12474

Uh oh!

Conversation

MozammilQ commented May 29, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Details and comments

Uh oh!

qiskit-bot commented May 29, 2024

Uh oh!

coveralls commented May 29, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Test Coverage Report for Build 14320951686

Details

💛 - Coveralls

Uh oh!

sbrandhsn commented May 29, 2024

Uh oh!

MozammilQ left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

MozammilQ commented Jun 3, 2024

Uh oh!

sbrandhsn commented Jun 4, 2024

Uh oh!

MozammilQ commented Jun 4, 2024

Uh oh!

sbrandhsn commented Jun 5, 2024

Uh oh!

MozammilQ commented Jun 10, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sbrandhsn left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sbrandhsn Jun 12, 2024

Choose a reason for hiding this comment

Uh oh!

MozammilQ Jun 19, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

MozammilQ commented Jan 31, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

eliarbel left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

eliarbel Mar 29, 2025

Choose a reason for hiding this comment

Uh oh!

MozammilQ Apr 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

eliarbel Apr 7, 2025

Choose a reason for hiding this comment

Uh oh!

Uh oh!

MozammilQ commented Apr 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

MozammilQ commented May 29, 2024 •

edited

Loading

coveralls commented May 29, 2024 •

edited

Loading

MozammilQ left a comment •

edited

Loading

MozammilQ commented Jun 10, 2024 •

edited

Loading

MozammilQ commented Jan 31, 2025 •

edited

Loading

MozammilQ Apr 2, 2025 •

edited

Loading

MozammilQ commented Apr 2, 2025 •

edited

Loading

MozammilQ commented Apr 7, 2025 •

edited

Loading