We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
building wide random circuits scales worse than deep ones.
<!-- ⚠️ If you do not respect this template, your issue will be closed -->
<!-- ⚠️ Make sure to browse the opened and closed issues to confirm this idea does not exist. -->

When using `random_circuit` from qiskit/circuit/random/utils.py to generate random circuits, scaling width appears to be worse than scaling depth. This was profiled using cProfile for running,

```python
    circuit = random_circuit(width, depth)
    dag = circuit_to_dag(circuit)
```
where we use
1. width = 2, depth =  10, 100, 1000, 10000, 100000, 1000000
or 
2. depth = 2, width = 10, 100, 1000, 10000, 100000

Ranking the top functions by total time spent within the function, and not sub-functions, for the first case shows linear scaling,

![image](https://user-images.githubusercontent.com/25756217/133529229-f837308b-0724-4917-874a-f6f5393e411e.png)

For the second case, however, we get superlinear scaling.

![image](https://user-images.githubusercontent.com/25756217/133529905-c59461e7-4ee8-4ab3-830b-327f05d61e27.png)

Looking at the function call dependency it seems that a greater proportion of time is spent in `rng.shuffle` and the list comprehensions.

deep circuit:
![image](https://user-images.githubusercontent.com/25756217/133530454-7bf8dfda-6c41-4d2a-978f-8870a78d09e9.png)

wide circuit
![image](https://user-images.githubusercontent.com/25756217/133531396-faddd775-7d7a-4ec6-b87d-26d6490c7c6b.png)

qiskit version: 0.19.0.dev0+7ea4d6e


### What is the expected enhancement?




--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `qiskit/circuit/random/utils.py`
Content:
```
1 # This code is part of Qiskit.
2 #
3 # (C) Copyright IBM 2017.
4 #
5 # This code is licensed under the Apache License, Version 2.0. You may
6 # obtain a copy of this license in the LICENSE.txt file in the root directory
7 # of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
8 #
9 # Any modifications or derivative works of this code must retain this
10 # copyright notice, and modified files need to carry a notice indicating
11 # that they have been altered from the originals.
12 
13 """Utility functions for generating random circuits."""
14 
15 import numpy as np
16 
17 from qiskit.circuit import QuantumRegister, ClassicalRegister, QuantumCircuit
18 from qiskit.circuit import Reset
19 from qiskit.circuit.library.standard_gates import (
20     IGate,
21     U1Gate,
22     U2Gate,
23     U3Gate,
24     XGate,
25     YGate,
26     ZGate,
27     HGate,
28     SGate,
29     SdgGate,
30     TGate,
31     TdgGate,
32     RXGate,
33     RYGate,
34     RZGate,
35     CXGate,
36     CYGate,
37     CZGate,
38     CHGate,
39     CRZGate,
40     CU1Gate,
41     CU3Gate,
42     SwapGate,
43     RZZGate,
44     CCXGate,
45     CSwapGate,
46 )
47 from qiskit.circuit.exceptions import CircuitError
48 
49 
50 def random_circuit(
51     num_qubits, depth, max_operands=3, measure=False, conditional=False, reset=False, seed=None
52 ):
53     """Generate random circuit of arbitrary size and form.
54 
55     This function will generate a random circuit by randomly selecting gates
56     from the set of standard gates in :mod:`qiskit.extensions`. For example:
57 
58     .. jupyter-execute::
59 
60         from qiskit.circuit.random import random_circuit
61 
62         circ = random_circuit(2, 2, measure=True)
63         circ.draw(output='mpl')
64 
65     Args:
66         num_qubits (int): number of quantum wires
67         depth (int): layers of operations (i.e. critical path length)
68         max_operands (int): maximum operands of each gate (between 1 and 3)
69         measure (bool): if True, measure all qubits at the end
70         conditional (bool): if True, insert middle measurements and conditionals
71         reset (bool): if True, insert middle resets
72         seed (int): sets random seed (optional)
73 
74     Returns:
75         QuantumCircuit: constructed circuit
76 
77     Raises:
78         CircuitError: when invalid options given
79     """
80     if max_operands < 1 or max_operands > 3:
81         raise CircuitError("max_operands must be between 1 and 3")
82 
83     one_q_ops = [
84         IGate,
85         U1Gate,
86         U2Gate,
87         U3Gate,
88         XGate,
89         YGate,
90         ZGate,
91         HGate,
92         SGate,
93         SdgGate,
94         TGate,
95         TdgGate,
96         RXGate,
97         RYGate,
98         RZGate,
99     ]
100     one_param = [U1Gate, RXGate, RYGate, RZGate, RZZGate, CU1Gate, CRZGate]
101     two_param = [U2Gate]
102     three_param = [U3Gate, CU3Gate]
103     two_q_ops = [CXGate, CYGate, CZGate, CHGate, CRZGate, CU1Gate, CU3Gate, SwapGate, RZZGate]
104     three_q_ops = [CCXGate, CSwapGate]
105 
106     qr = QuantumRegister(num_qubits, "q")
107     qc = QuantumCircuit(num_qubits)
108 
109     if measure or conditional:
110         cr = ClassicalRegister(num_qubits, "c")
111         qc.add_register(cr)
112 
113     if reset:
114         one_q_ops += [Reset]
115 
116     if seed is None:
117         seed = np.random.randint(0, np.iinfo(np.int32).max)
118     rng = np.random.default_rng(seed)
119 
120     # apply arbitrary random operations at every depth
121     for _ in range(depth):
122         # choose either 1, 2, or 3 qubits for the operation
123         remaining_qubits = list(range(num_qubits))
124         while remaining_qubits:
125             max_possible_operands = min(len(remaining_qubits), max_operands)
126             num_operands = rng.choice(range(max_possible_operands)) + 1
127             rng.shuffle(remaining_qubits)
128             operands = remaining_qubits[:num_operands]
129             remaining_qubits = [q for q in remaining_qubits if q not in operands]
130             if num_operands == 1:
131                 operation = rng.choice(one_q_ops)
132             elif num_operands == 2:
133                 operation = rng.choice(two_q_ops)
134             elif num_operands == 3:
135                 operation = rng.choice(three_q_ops)
136             if operation in one_param:
137                 num_angles = 1
138             elif operation in two_param:
139                 num_angles = 2
140             elif operation in three_param:
141                 num_angles = 3
142             else:
143                 num_angles = 0
144             angles = [rng.uniform(0, 2 * np.pi) for x in range(num_angles)]
145             register_operands = [qr[i] for i in operands]
146             op = operation(*angles)
147 
148             # with some low probability, condition on classical bit values
149             if conditional and rng.choice(range(10)) == 0:
150                 value = rng.integers(0, np.power(2, num_qubits))
151                 op.condition = (cr, value)
152 
153             qc.append(op, register_operands)
154 
155     if measure:
156         qc.measure(qr, cr)
157 
158     return qc
159
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/qiskit/circuit/random/utils.py b/qiskit/circuit/random/utils.py
--- a/qiskit/circuit/random/utils.py
+++ b/qiskit/circuit/random/utils.py
@@ -121,12 +121,11 @@
     for _ in range(depth):
         # choose either 1, 2, or 3 qubits for the operation
         remaining_qubits = list(range(num_qubits))
+        rng.shuffle(remaining_qubits)
         while remaining_qubits:
             max_possible_operands = min(len(remaining_qubits), max_operands)
             num_operands = rng.choice(range(max_possible_operands)) + 1
-            rng.shuffle(remaining_qubits)
-            operands = remaining_qubits[:num_operands]
-            remaining_qubits = [q for q in remaining_qubits if q not in operands]
+            operands = [remaining_qubits.pop() for _ in range(num_operands)]
             if num_operands == 1:
                 operation = rng.choice(one_q_ops)
             elif num_operands == 2:

{"golden_diff": "diff --git a/qiskit/circuit/random/utils.py b/qiskit/circuit/random/utils.py\n--- a/qiskit/circuit/random/utils.py\n+++ b/qiskit/circuit/random/utils.py\n@@ -121,12 +121,11 @@\n     for _ in range(depth):\n         # choose either 1, 2, or 3 qubits for the operation\n         remaining_qubits = list(range(num_qubits))\n+        rng.shuffle(remaining_qubits)\n         while remaining_qubits:\n             max_possible_operands = min(len(remaining_qubits), max_operands)\n             num_operands = rng.choice(range(max_possible_operands)) + 1\n-            rng.shuffle(remaining_qubits)\n-            operands = remaining_qubits[:num_operands]\n-            remaining_qubits = [q for q in remaining_qubits if q not in operands]\n+            operands = [remaining_qubits.pop() for _ in range(num_operands)]\n             if num_operands == 1:\n                 operation = rng.choice(one_q_ops)\n             elif num_operands == 2:\n", "issue": "building wide random circuits scales worse than deep ones.\n<!-- \u26a0\ufe0f If you do not respect this template, your issue will be closed -->\r\n<!-- \u26a0\ufe0f Make sure to browse the opened and closed issues to confirm this idea does not exist. -->\r\n\r\nWhen using `random_circuit` from qiskit/circuit/random/utils.py to generate random circuits, scaling width appears to be worse than scaling depth. This was profiled using cProfile for running,\r\n\r\n```python\r\n    circuit = random_circuit(width, depth)\r\n    dag = circuit_to_dag(circuit)\r\n```\r\nwhere we use\r\n1. width = 2, depth =  10, 100, 1000, 10000, 100000, 1000000\r\nor \r\n2. depth = 2, width = 10, 100, 1000, 10000, 100000\r\n\r\nRanking the top functions by total time spent within the function, and not sub-functions, for the first case shows linear scaling,\r\n\r\n![image](https://user-images.githubusercontent.com/25756217/133529229-f837308b-0724-4917-874a-f6f5393e411e.png)\r\n\r\nFor the second case, however, we get superlinear scaling.\r\n\r\n![image](https://user-images.githubusercontent.com/25756217/133529905-c59461e7-4ee8-4ab3-830b-327f05d61e27.png)\r\n\r\nLooking at the function call dependency it seems that a greater proportion of time is spent in `rng.shuffle` and the list comprehensions.\r\n\r\ndeep circuit:\r\n![image](https://user-images.githubusercontent.com/25756217/133530454-7bf8dfda-6c41-4d2a-978f-8870a78d09e9.png)\r\n\r\nwide circuit\r\n![image](https://user-images.githubusercontent.com/25756217/133531396-faddd775-7d7a-4ec6-b87d-26d6490c7c6b.png)\r\n\r\nqiskit version: 0.19.0.dev0+7ea4d6e\r\n\r\n\r\n### What is the expected enhancement?\r\n\r\n\r\n\n", "before_files": [{"content": "# This code is part of Qiskit.\n#\n# (C) Copyright IBM 2017.\n#\n# This code is licensed under the Apache License, Version 2.0. You may\n# obtain a copy of this license in the LICENSE.txt file in the root directory\n# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.\n#\n# Any modifications or derivative works of this code must retain this\n# copyright notice, and modified files need to carry a notice indicating\n# that they have been altered from the originals.\n\n\"\"\"Utility functions for generating random circuits.\"\"\"\n\nimport numpy as np\n\nfrom qiskit.circuit import QuantumRegister, ClassicalRegister, QuantumCircuit\nfrom qiskit.circuit import Reset\nfrom qiskit.circuit.library.standard_gates import (\n    IGate,\n    U1Gate,\n    U2Gate,\n    U3Gate,\n    XGate,\n    YGate,\n    ZGate,\n    HGate,\n    SGate,\n    SdgGate,\n    TGate,\n    TdgGate,\n    RXGate,\n    RYGate,\n    RZGate,\n    CXGate,\n    CYGate,\n    CZGate,\n    CHGate,\n    CRZGate,\n    CU1Gate,\n    CU3Gate,\n    SwapGate,\n    RZZGate,\n    CCXGate,\n    CSwapGate,\n)\nfrom qiskit.circuit.exceptions import CircuitError\n\n\ndef random_circuit(\n    num_qubits, depth, max_operands=3, measure=False, conditional=False, reset=False, seed=None\n):\n    \"\"\"Generate random circuit of arbitrary size and form.\n\n    This function will generate a random circuit by randomly selecting gates\n    from the set of standard gates in :mod:`qiskit.extensions`. For example:\n\n    .. jupyter-execute::\n\n        from qiskit.circuit.random import random_circuit\n\n        circ = random_circuit(2, 2, measure=True)\n        circ.draw(output='mpl')\n\n    Args:\n        num_qubits (int): number of quantum wires\n        depth (int): layers of operations (i.e. critical path length)\n        max_operands (int): maximum operands of each gate (between 1 and 3)\n        measure (bool): if True, measure all qubits at the end\n        conditional (bool): if True, insert middle measurements and conditionals\n        reset (bool): if True, insert middle resets\n        seed (int): sets random seed (optional)\n\n    Returns:\n        QuantumCircuit: constructed circuit\n\n    Raises:\n        CircuitError: when invalid options given\n    \"\"\"\n    if max_operands < 1 or max_operands > 3:\n        raise CircuitError(\"max_operands must be between 1 and 3\")\n\n    one_q_ops = [\n        IGate,\n        U1Gate,\n        U2Gate,\n        U3Gate,\n        XGate,\n        YGate,\n        ZGate,\n        HGate,\n        SGate,\n        SdgGate,\n        TGate,\n        TdgGate,\n        RXGate,\n        RYGate,\n        RZGate,\n    ]\n    one_param = [U1Gate, RXGate, RYGate, RZGate, RZZGate, CU1Gate, CRZGate]\n    two_param = [U2Gate]\n    three_param = [U3Gate, CU3Gate]\n    two_q_ops = [CXGate, CYGate, CZGate, CHGate, CRZGate, CU1Gate, CU3Gate, SwapGate, RZZGate]\n    three_q_ops = [CCXGate, CSwapGate]\n\n    qr = QuantumRegister(num_qubits, \"q\")\n    qc = QuantumCircuit(num_qubits)\n\n    if measure or conditional:\n        cr = ClassicalRegister(num_qubits, \"c\")\n        qc.add_register(cr)\n\n    if reset:\n        one_q_ops += [Reset]\n\n    if seed is None:\n        seed = np.random.randint(0, np.iinfo(np.int32).max)\n    rng = np.random.default_rng(seed)\n\n    # apply arbitrary random operations at every depth\n    for _ in range(depth):\n        # choose either 1, 2, or 3 qubits for the operation\n        remaining_qubits = list(range(num_qubits))\n        while remaining_qubits:\n            max_possible_operands = min(len(remaining_qubits), max_operands)\n            num_operands = rng.choice(range(max_possible_operands)) + 1\n            rng.shuffle(remaining_qubits)\n            operands = remaining_qubits[:num_operands]\n            remaining_qubits = [q for q in remaining_qubits if q not in operands]\n            if num_operands == 1:\n                operation = rng.choice(one_q_ops)\n            elif num_operands == 2:\n                operation = rng.choice(two_q_ops)\n            elif num_operands == 3:\n                operation = rng.choice(three_q_ops)\n            if operation in one_param:\n                num_angles = 1\n            elif operation in two_param:\n                num_angles = 2\n            elif operation in three_param:\n                num_angles = 3\n            else:\n                num_angles = 0\n            angles = [rng.uniform(0, 2 * np.pi) for x in range(num_angles)]\n            register_operands = [qr[i] for i in operands]\n            op = operation(*angles)\n\n            # with some low probability, condition on classical bit values\n            if conditional and rng.choice(range(10)) == 0:\n                value = rng.integers(0, np.power(2, num_qubits))\n                op.condition = (cr, value)\n\n            qc.append(op, register_operands)\n\n    if measure:\n        qc.measure(qr, cr)\n\n    return qc\n", "path": "qiskit/circuit/random/utils.py"}], "after_files": [{"content": "# This code is part of Qiskit.\n#\n# (C) Copyright IBM 2017.\n#\n# This code is licensed under the Apache License, Version 2.0. You may\n# obtain a copy of this license in the LICENSE.txt file in the root directory\n# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.\n#\n# Any modifications or derivative works of this code must retain this\n# copyright notice, and modified files need to carry a notice indicating\n# that they have been altered from the originals.\n\n\"\"\"Utility functions for generating random circuits.\"\"\"\n\nimport numpy as np\n\nfrom qiskit.circuit import QuantumRegister, ClassicalRegister, QuantumCircuit\nfrom qiskit.circuit import Reset\nfrom qiskit.circuit.library.standard_gates import (\n    IGate,\n    U1Gate,\n    U2Gate,\n    U3Gate,\n    XGate,\n    YGate,\n    ZGate,\n    HGate,\n    SGate,\n    SdgGate,\n    TGate,\n    TdgGate,\n    RXGate,\n    RYGate,\n    RZGate,\n    CXGate,\n    CYGate,\n    CZGate,\n    CHGate,\n    CRZGate,\n    CU1Gate,\n    CU3Gate,\n    SwapGate,\n    RZZGate,\n    CCXGate,\n    CSwapGate,\n)\nfrom qiskit.circuit.exceptions import CircuitError\n\n\ndef random_circuit(\n    num_qubits, depth, max_operands=3, measure=False, conditional=False, reset=False, seed=None\n):\n    \"\"\"Generate random circuit of arbitrary size and form.\n\n    This function will generate a random circuit by randomly selecting gates\n    from the set of standard gates in :mod:`qiskit.extensions`. For example:\n\n    .. jupyter-execute::\n\n        from qiskit.circuit.random import random_circuit\n\n        circ = random_circuit(2, 2, measure=True)\n        circ.draw(output='mpl')\n\n    Args:\n        num_qubits (int): number of quantum wires\n        depth (int): layers of operations (i.e. critical path length)\n        max_operands (int): maximum operands of each gate (between 1 and 3)\n        measure (bool): if True, measure all qubits at the end\n        conditional (bool): if True, insert middle measurements and conditionals\n        reset (bool): if True, insert middle resets\n        seed (int): sets random seed (optional)\n\n    Returns:\n        QuantumCircuit: constructed circuit\n\n    Raises:\n        CircuitError: when invalid options given\n    \"\"\"\n    if max_operands < 1 or max_operands > 3:\n        raise CircuitError(\"max_operands must be between 1 and 3\")\n\n    one_q_ops = [\n        IGate,\n        U1Gate,\n        U2Gate,\n        U3Gate,\n        XGate,\n        YGate,\n        ZGate,\n        HGate,\n        SGate,\n        SdgGate,\n        TGate,\n        TdgGate,\n        RXGate,\n        RYGate,\n        RZGate,\n    ]\n    one_param = [U1Gate, RXGate, RYGate, RZGate, RZZGate, CU1Gate, CRZGate]\n    two_param = [U2Gate]\n    three_param = [U3Gate, CU3Gate]\n    two_q_ops = [CXGate, CYGate, CZGate, CHGate, CRZGate, CU1Gate, CU3Gate, SwapGate, RZZGate]\n    three_q_ops = [CCXGate, CSwapGate]\n\n    qr = QuantumRegister(num_qubits, \"q\")\n    qc = QuantumCircuit(num_qubits)\n\n    if measure or conditional:\n        cr = ClassicalRegister(num_qubits, \"c\")\n        qc.add_register(cr)\n\n    if reset:\n        one_q_ops += [Reset]\n\n    if seed is None:\n        seed = np.random.randint(0, np.iinfo(np.int32).max)\n    rng = np.random.default_rng(seed)\n\n    # apply arbitrary random operations at every depth\n    for _ in range(depth):\n        # choose either 1, 2, or 3 qubits for the operation\n        remaining_qubits = list(range(num_qubits))\n        rng.shuffle(remaining_qubits)\n        while remaining_qubits:\n            max_possible_operands = min(len(remaining_qubits), max_operands)\n            num_operands = rng.choice(range(max_possible_operands)) + 1\n            operands = [remaining_qubits.pop() for _ in range(num_operands)]\n            if num_operands == 1:\n                operation = rng.choice(one_q_ops)\n            elif num_operands == 2:\n                operation = rng.choice(two_q_ops)\n            elif num_operands == 3:\n                operation = rng.choice(three_q_ops)\n            if operation in one_param:\n                num_angles = 1\n            elif operation in two_param:\n                num_angles = 2\n            elif operation in three_param:\n                num_angles = 3\n            else:\n                num_angles = 0\n            angles = [rng.uniform(0, 2 * np.pi) for x in range(num_angles)]\n            register_operands = [qr[i] for i in operands]\n            op = operation(*angles)\n\n            # with some low probability, condition on classical bit values\n            if conditional and rng.choice(range(10)) == 0:\n                value = rng.integers(0, np.power(2, num_qubits))\n                op.condition = (cr, value)\n\n            qc.append(op, register_operands)\n\n    if measure:\n        qc.measure(qr, cr)\n\n    return qc\n", "path": "qiskit/circuit/random/utils.py"}]}