Introduction
See my Master's thesis [5] for a better introduction to these results.
The Database of Self-Dual Quantum Codes contains equivalence classes of objects that may be interpreted as quantum codes, self-dual additive codes over GF(4), graphs, or quadratic Boolean functions. Nonquadratic Boolean functions do not correspond to self-dual additive codes, but they correspond to hypergraphs and can be interpreted as quantum codes.
A nonquadratic Boolean function, f(x), can be interpreted as the quantum state described by the probability vector s = 2-n/2(-1)f(x) [1]. A single quantum state corresponds to a quantum error-correcting code of dimension zero. The distance of this code is the weight of the minimum weight quantum error operator that gives an errored state not orthogonal to the original state, and therefore not guaranteed to be detectable. This distance is equal to the APC distance [2]. Boolean functions with high APC distance may applications in cryptography, and for cryptographic purposes we are interested in Boolean functions of high degree.
The simplest nonquadratic function with APC distance greater than 2 is 012,03,04,13,15,24,25 (shorthand for x0x1x2 + x0x3 + x0x4 + x1x3 + x1x5 + x2x4 + x2x5). It corresponds to a bipolar vector of length 64, 2-3(-1)f(x) = 2-3(1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, -1, 1, -1, 1, 1, -1, -1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, -1), which may be interpreted as a the probability vector of a quantum state. As an example, consider the weight 1 error operator that bit-flips the qubit corresponding to the variable x0, i.e., x0 goes to x0+1. The errored state is f'(x) = 012,03,04,13,15,24,25,12,3,4. We can verify that 2-3(-1)f(x) and 2-3(-1)f'(x) are orthogonal vectors. By an exhaustive search, we find that all Pauli error operators of weight 1 and 2 give orthogonal errored states, i.e., all combinations of bit-flip, phase-flip and combined bit-flip/phase-flip errors on 1 or 2 qubits will always be detectable. There exist, however, 3-qubit errors that do not give orthogonal states. Hence, the APC distance is 3, and the function 012,03,04,13,15,24,25 can be interpreted as a [[6,0,3]] quantum code.
The APC distance of a Boolean function is invariant under the infinite set of local unitary transformations. We consider a subset of transformations:
- Bit-flip
- A bit-flip on variable xa maps xa to xa+1. If xa is part of term of degree d, the bit-flip will produce an additional term of degree d-1, (or remove this term if it is already present).
- Phase-flip (Affine offset)
- Addition of linear or constant terms do not influence the APC distance. This corresponds to a phase-flip on variable xa, which transforms f(x) into f(x)+xa.
- Permutation
- Reordering the indices of variables does not change the APC. Two function are equivalent if they are isomorphic, when interpreted as hypergraphs.
- {I,H,N}n transform
- APC distance is invariant under the {I,H,N}n transform [3].
In addition to APC distance, we are interested in other properties of Boolean functions. The Clifford Merit Factor [4] and peak-to-average power ratio with respect to the {I,H,N}n transform, PARIHN [3], are invariant under the same symmetries as the APC distance. This database contains a representative of every equivalence class of Boolean functions with 3, 4 and 5 variables, with respect to these symmetries. For 6 variables, we have only been able to generate all classes of functions with degree 3 or less. The Multivariate Merit Factor [4] is invariant only under bit-flip, phase-flip and permutation. This database also contains representatives of equivalence classes w.r.t. to these symmetries.
We have not found any nonquadratic function with higher APC distance than the best quadratic function with the same number of variables. For n=6, there are 11 inequivalent cubic functions with APC distance 3. For n higher than 6, nonexhaustive searches have revealed functions with the same APC distance as the best quadratic functions:
- [[7,0,3]]
- 013,023,123,012,04,05,14,16,25,26,34,35,36
- 0126,03,05,14,15,23,24,26,36,46,56
- [[8,0,4]]
- 456,056,246,026,245,025,04,07,15,16,17,23,26,27,35,36,45,46,47,57
- [[9,0,4]]
- 037,137,034,134,01,07,08,14,18,23,25,28,36,37,45,46,57,58,67,68
- [[10,0,4]]
- 016,02,03,08,12,13,17,26,39,45,46,48,57,59,67,68,79,89
Tables
These tables only enumerate indecomposable functions, i.e., functions whose corresponding hypergraphs are connected. All inequivalent decomposable functions can be found by combining indecomposable functions of fewer variables.
Number of inequivalent functions, w.r.t.
- A) Bit-flip, Phase-flip and Permutation
- B) Bit-flip, Phase-flip, Permutation and {I,H,N}n transform:
| n | A) | B) |
|---|---|---|
| 3 | 3 | 2 |
| 4 | 33 | 29 |
| 5 | 22,400 | 22,014 |
| 6 (only up to degree 3) | 850,705 | 746,326 |
The 22,400 inequivalent functions for n=5 under symmetries A) by distance and degree:
| distance\degree | 2 | 3 | 4 | 5 | All |
|---|---|---|---|---|---|
| 1 | 625 | 10,756 | 10,688 | 22,069 | |
| 2 | 18 | 109 | 201 | 328 | |
| 3 | 3 | 3 | |||
| All | 21 | 734 | 10,957 | 10,688 | 22,400 |
The 22,014 inequivalent functions for n=5 under symmetries B) by distance and degree:
| distance\degree | 2 | 3 | 4 | 5 | All |
|---|---|---|---|---|---|
| 1 | 505 | 10,570 | 10,688 | 21,736 | |
| 2 | 3 | 61 | 186 | 250 | |
| 3 | 1 | 1 | |||
| All | 4 | 566 | 10,756 | 10,688 | 22,014 |
The 850,705 inequivalent functions for n=6 with degree up to 3 under symmetries A) by distance and degree:
| distance\degree | 2 | 3 | 4 | 5 | 6 | All up to 3 |
|---|---|---|---|---|---|---|
| 1 | 804,326 | ? | ? | ? | 804,326 | |
| 2 | 94 | 46,243 | ? | ? | ? | 46,337 |
| 3 | 16 | 24 | ? | ? | ? | 40 |
| 4 | 2 | ? | ? | ? | 2 | |
| All | 112 | 850,593 | ? | ? | ? | 850,705 |
The 746,326 inequivalent functions for n=6 with degree up to 3 under symmetries B) by distance and degree:
| distance\degree | 2 | 3 | 4 | 5 | 6 | All up to 3 |
|---|---|---|---|---|---|---|
| 1 | 717,741 | ? | ? | ? | 717,741 | |
| 2 | 9 | 28,563 | ? | ? | ? | 28,572 |
| 3 | 1 | 11 | ? | ? | ? | 12 |
| 4 | 1 | ? | ? | ? | 1 | |
| All | 11 | 746,315 | ? | ? | ? | 746,326 |
File formats
The files contain one representative of each equivalence class. A shorthand ANF notation is used. Example: "03,13,23," is the function "x0x3+x1x3+x2x3". Some of the larger files are compressed with gzip.
^ TOPFiles
All equivalence classes of connected hypergraphs/functions w.r.t. Bit-flip, Phase-flip and Permutation:
| Variables | Download | File size |
|---|---|---|
| n=3 | 3BitAffinePerm.anf | 22B |
| n=4 | 4BitAffinePerm.anf | 482B |
| n=5 | 5BitAffinePerm.anf | 812KB |
| n=6 (only up to degree 3) | 6BitAffinePerm_deg3.anf.gz | 2.4MB |
All equivalence classes of connected hypergraphs/functions w.r.t. Bit-flip, Phase-flip, Permutation and {I,H,N}n transform:
| Variables | Download | File size |
|---|---|---|
| n=3 | 3BitAffinePermIHN.anf | 12B |
| n=4 | 4BitAffinePermIHN.anf | 421B |
| n=5 | 5BitAffinePermIHN.anf | 802KB |
| n=6 (only up to degree 3) | 6BitAffinePermIHN_deg3.anf.gz | 2.2MB |
References
[1] M.G. Parker and V. Rijmen. The quantum entanglement of binary and bipolar sequences. In T. Helleseth, P.V. Kumar and K. Yang (eds.), Sequences and Their Applications, SETA'01, Discrete Mathematics and Theoretical Computer Science Series, Springer-Verlag, 2001.
[2] L.E. Danielsen, T.A. Gulliver, and M.G. Parker: Aperiodic propagation criteria for Boolean functions, Information and Computation, 204(5), pp. 741–770, May 2006.
[3] L.E. Danielsen and M.G. Parker. Spectral orbits and peak-to-average power ratio of Boolean functions with respect to the {I,H,N}n transform. In Sequences and Their Applications – SETA 2004, Lecture Notes in Computer Science, volume 3486, pp. 373–388, Springer-Verlag, Berlin, 2005.
[4] M.G. Parker. Univariate and multivariate merit factors. In Sequences and Their Applications – SETA 2004, Lecture Notes in Computer Science, volume 3486, pp. 72–100, Springer-Verlag, Berlin, 2005.
[5] L.E. Danielsen. On Self-Dual Quantum Codes, Graphs, and Boolean Functions, Master's thesis, Department of Informatics, University of Bergen, Norway, March 2005.