Benchmark transformers.routing.RouteCQC takes a lot of time to setup

[dkothari11]

Benchmark transformers.routing.RouteCQC takes a lot of time to setup
asv compare between two commits, is taking more than 2 hrs to run. While investigating why it's slow, I found that benchmark transformers.routing.RouteCQC has slow setup routine.

I have tried to go via method mentioned in this comment
Slow setup routines in our benchmarks (for time > 5sec):

Slow setup routines
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,50,0.5,10): 0.51 * 11 = 5.6s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,50,0.5,10): 0.6 * 11 = 6.6s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,500,0.5,10): 0.69 * 11 = 7.6s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,100,0.5,10): 1 * 11 = 11.3s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,50,0.5,10): 1.1 * 11 = 12.1s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,100,0.5,10): 1.2 * 11 = 13.2s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,1000,0.5,10): 1.4 * 11 = 15.0s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,250,0.5,10): 1.5 * 11 = 17.0s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,100,0.5,10): 2.2 * 11 = 24.0s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,500,0.5,10): 2.6 * 11 = 28.5s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,250,0.5,10): 3 * 11 = 32.8s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,1000,0.5,10): 5.2 * 11 = 57.4s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,250,0.5,10): 5.5 * 11 = 60.1s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,500,0.5,10): 6 * 11 = 66.0s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,500,0.5,10): 11 * 11 = 121.3s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,1000,0.5,10): 15 * 11 = 167.9s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,1000,0.5,10): 22 * 11 = 241.2s

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(50,20)
benchmarks: 1
repeats: 10
setup: 0.002213669940829277

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(50,40)
benchmarks: 1
repeats: 10
setup: 0.0017167190089821815

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(50,60)
benchmarks: 1
repeats: 10
setup: 0.0016303802840411663

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(50,80)
benchmarks: 1
repeats: 10
setup: 0.0016211103647947311

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(50,100)
benchmarks: 1
repeats: 10
setup: 0.0015438101254403591

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(100,20)
benchmarks: 1
repeats: 10
setup: 0.003328968770802021

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(100,40)
benchmarks: 1
repeats: 10
setup: 0.0034533990547060966

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(100,60)
benchmarks: 1
repeats: 10
setup: 0.0030543701723217964

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(100,80)
benchmarks: 1
repeats: 10
setup: 0.0029496289789676666

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(100,100)
benchmarks: 1
repeats: 10
setup: 0.0029646586626768112

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(150,20)
benchmarks: 1
repeats: 10
setup: 0.00461150985211134

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(150,40)
benchmarks: 1
repeats: 10
setup: 0.004394269082695246

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(150,60)
benchmarks: 1
repeats: 10
setup: 0.004237090237438679

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(150,80)
benchmarks: 1
repeats: 10
setup: 0.004319368861615658

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(150,100)
benchmarks: 1
repeats: 10
setup: 0.004277150146663189

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(200,20)
benchmarks: 1
repeats: 10
setup: 0.006351308897137642

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(200,40)
benchmarks: 1
repeats: 10
setup: 0.005670509301126003

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(200,60)
benchmarks: 1
repeats: 10
setup: 0.005756109952926636

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(200,80)
benchmarks: 1
repeats: 10
setup: 0.005629698745906353

benchmarks.parameter_resolution.RabiCalibration:RabiCalibration.setup(200,100)
benchmarks: 1
repeats: 10
setup: 0.005627229809761047

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(10,10,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.00583661999553442

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(10,50,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.018425337970256805

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(10,100,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.033675557002425194

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(10,250,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.07933415099978447

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(10,500,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.15707392198964953

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(10,1000,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.37925020698457956

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,10,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.017564218025654554

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,50,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.07377554196864367

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,100,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.1455010031349957

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,250,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.34853148087859154

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,500,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.6939294221810997
SLOW! (total 7.6s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,1000,0.5,10)
benchmarks: 2
repeats: 11
setup: 1.3627052651718259
SLOW! (total 15.0s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,10,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.05764468386769295

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,50,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.5061010727658868
SLOW! (total 5.6s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,100,0.5,10)
benchmarks: 2
repeats: 11
setup: 1.027008012868464
SLOW! (total 11.3s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,250,0.5,10)
benchmarks: 2
repeats: 11
setup: 1.5411530449055135
SLOW! (total 17.0s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,500,0.5,10)
benchmarks: 2
repeats: 11
setup: 2.5884914458729327
SLOW! (total 28.5s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,1000,0.5,10)
benchmarks: 2
repeats: 11
setup: 5.218800795264542
SLOW! (total 57.4s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,10,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.12721005594357848

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,50,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.5957539319060743
SLOW! (total 6.6s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,100,0.5,10)
benchmarks: 2
repeats: 11
setup: 1.1963338828645647
SLOW! (total 13.2s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,250,0.5,10)
benchmarks: 2
repeats: 11
setup: 2.9841034398414195
SLOW! (total 32.8s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,500,0.5,10)
benchmarks: 2
repeats: 11
setup: 5.997657195199281
SLOW! (total 66.0s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,1000,0.5,10)
benchmarks: 2
repeats: 11
setup: 15.261249690316617
SLOW! (total 167.9s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,10,0.5,10)
benchmarks: 2
repeats: 11
setup: 0.23066901415586472

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,50,0.5,10)
benchmarks: 2
repeats: 11
setup: 1.1030465941876173
SLOW! (total 12.1s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,100,0.5,10)
benchmarks: 2
repeats: 11
setup: 2.1857873778790236
SLOW! (total 24.0s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,250,0.5,10)
benchmarks: 2
repeats: 11
setup: 5.467197320889682
SLOW! (total 60.1s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,500,0.5,10)
benchmarks: 2
repeats: 11
setup: 11.030987066682428
SLOW! (total 121.3s)

benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,1000,0.5,10)
benchmarks: 2
repeats: 11
setup: 21.923182957805693
SLOW! (total 241.2s)

Slow setup routines
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,50,0.5,10): 0.51 * 11 = 5.6s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,50,0.5,10): 0.6 * 11 = 6.6s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,500,0.5,10): 0.69 * 11 = 7.6s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,100,0.5,10): 1 * 11 = 11.3s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,50,0.5,10): 1.1 * 11 = 12.1s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,100,0.5,10): 1.2 * 11 = 13.2s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(25,1000,0.5,10): 1.4 * 11 = 15.0s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,250,0.5,10): 1.5 * 11 = 17.0s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,100,0.5,10): 2.2 * 11 = 24.0s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,500,0.5,10): 2.6 * 11 = 28.5s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,250,0.5,10): 3 * 11 = 32.8s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(50,1000,0.5,10): 5.2 * 11 = 57.4s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,250,0.5,10): 5.5 * 11 = 60.1s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,500,0.5,10): 6 * 11 = 66.0s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,500,0.5,10): 11 * 11 = 121.3s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(75,1000,0.5,10): 15 * 11 = 167.9s
benchmarks.transformers.routing.RouteCQC:RouteCQC.setup(100,1000,0.5,10): 22 * 11 = 241.2s

Cirq version
1.1.0.dev

[tanujkhattar]

Thank you Disha for reporting this.

The RouteCQC.setup method is mainly doing the following 3 steps:

1. Construct a random circuit
2. Construct a grid device
3. Initialize the routing transformer

AFAICT, the majority of the time would be going in constructing the random circuit.

It is a known issue that [cirq.testing.random_circuit](https://github.com/quantumlib/Cirq/blob/cb6940a40141dba95cba84f5acc27acbeb65b17c/cirq-core/cirq/testing/random_circuit.py#L47) is very slow. Looking at the implementation we can notice that:

1. There is an outer loop on number of moments contributing a factor of D (depth of the circuit)
2. There is an inner loop on number of qubits in the circuit (most operations are 1/2 qubit operations so while len(free_qubits) >= max_arity will run O(Q) times where Q is number of qubits.
3. Within the nested loop, we have calls to prng.choice(sorted(free_qubits), size=arity, replace=False), prng.randint and prng.rand() to generate random numbers to choose the next operation.

Overall, for a circuit of depth 1000 on 100 qubits; we run the numpy functions to generate random numbers O(1e5) times; which is pretty slow. One way to speed this up would be to try and generate the random numbers in advance (since numpy can vectorize a single function call to generate 1e5 random numbers, which should be faster than generating 1e5 random numbers by individual function calls).

Curious to see what others think cc @maffoo