### Lower bound on the number of patterns

←Return to chapter

## 99.2. Lower bound on the number of patterns

Proposition 99.2

Let N w, d N_{w,d}N w,d​ be the number of port graphs of width w w w, depth d dd and maximum degree Δ≥4\Delta \geq 4Δ≥4. We can lower bound

N w, d>(w 2 e)Θ(w d),N_{w,d} > \left(\frac{w}{2e}\right)^{\Theta(wd)},N w,d​>(2e w​)Θ(w d),

assuming w≤o(2 d)w \leq o(2^d)w≤o(2 d).

In the regime of interest, w w w is small, so the assumption w≤o(2 d)w \leq o(2^d)w≤o(2 d) is not a restriction.

Let w, d>0 w, d > 0 w, d>0 and Δ≥4\Delta \geq 4Δ≥4 be integers. We wish to lower bound the number of port graphs of depth d dd, width w w w and maximum degree Δ\DeltaΔ. It is sufficient to consider a restricted subset of such port graphs, whose size can be easily lower bounded. We will count a subset of CX quantum circuits, i.e. circuits with only C X CX CX gates, a two-qubit non-symmetric gate. Because we are using a single gate type, this is equivalent to counting a subset of port graphs with vertices of degree 4. Assume w.l.o.g that w w w is a power of two. We consider CX circuits constructed from two circuits with w w w qubits composed in sequence:

- Fixed tree circuit: A log⁡2(w)\log_2(w)log 2​(w)-depth circuit that connects qubits pairwise in such a way that the resulting port graph is connected. We fix such a tree-like circuit and use the same circuit for all CX circuits. We can use this common structure to fix an ordering of the w w w qubits, that refer to as qubits 1,…,w 1,\dots,w1,…,w.
- Bipartite circuit: A CX circuit of depth D=d−log⁡2(w)D = d - \log_2(w)D=d−log 2​(w) with exactly CX gates, each gate acting on a qubit and a qubit .

The following circuit illustrates the construction:

All that remains is to count the number of such bipartite circuits. Every slice of depth 1 must have w/2 w / 2 w/2 CX gates acting on distinct qubits. Every qubit 1 11 to w/2 w/2 w/2 must interact with one of the qubits w/2+1 w/2+1 w/2+1 to w w w, so there are (w/2)!(w/2)!(w/2)! such depth 1 slices. Repeating this depth 1 construction D D D times and using Sterling’s approximation, we obtain a lower bound for the number of port graphs of depth d dd, width w w w and maximum degree at least 4:

((w 2)!)D>w π(w 2 e)w D/2=(w 2 e)Θ(w⋅d)\left(\left(\frac{w}2\right)!\right)^D > \sqrt{w\pi}\left(\frac{w}{2e}\right)^{wD/2} = \left(\frac{w}{2e}\right)^{\Theta(w\cdot d)}((2 w​)!)D>w π
​(2e w​)w D/2=(2e w​)Θ(w⋅d)

where we used w=o(2 d)w = o(2^d)w=o(2 d) to obtain Θ(D)=Θ(d)\Theta(D) = \Theta(d)Θ(D)=Θ(d) in the last step.

←Return to chapter