OFFSET
0,4
COMMENTS
Using transvections as the generating set of the matrix group, this is the number of inequivalent minimal words in k generators; the number of elements at distance k from the identity in the corresponding Cayley graph.
Also the number of different elements that can be represented by minimal quantum circuits of k CNOT gates on n qubits.
LINKS
Søren Fuglede Jørgensen, Table of n, a(n) for n = 0..83
Marc Bataille, Quantum Circuits of CNOT gates: Optimization and Entanglement, Quantum Information Processing, 21(7):269 (2022).
Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol, On Exact Sizes of Minimal CNOT Circuits, RC 2025, LNCS, vol 15716, pp. 71-88; arXiv:2503.01467 [quant-ph], 2025.
Ketan N. Patel, Igor L. Markov, and John P. Hayes, Optimal synthesis of linear reversible circuits, Quantum Info. Comput., 8(3) (2008), pp. 282-294.
FORMULA
T(n, 0) = 1.
T(n, 1) = n^2 - n.
T(n, 2) = (1/2)*(n^4 - 5*n^2 + 4*n).
T(n, 3) = (1/6)*(n^6 + 3*n^5 - 9*n^4 - 63*n^3 + 179*n^2 - 111*n).
Sum_{k>=0} T(n,k) = A002884(n).
EXAMPLE
Triangle begins:
n\k 0 1 2 3 4 5 6 7 8 9
0: 1
1: 1
2: 1 2 2 1
3: 1 6 24 51 60 24 2
4: 1 12 96 542 2058 5316 7530 4058 541 6
...
For n = 2, k = 1, the two matrices are [[1, 1], [0, 1]] and [[1, 0], [1, 1]].
For n = 2, k = 2, the two matrices are [[1, 1], [1, 0]] and [[0, 1], [1, 1]].
For n = 2, k = 3, the only matrix is [[0, 1], [1, 0]].
CROSSREFS
KEYWORD
nonn,tabf,hard
AUTHOR
Søren Fuglede Jørgensen, Mar 08 2025
STATUS
approved