The benchmark suite contains quantum circuits implementing small Boolean functions and expressed in the Q# quantum programming language.
The circuits are optimized according to the requirements of fault-tolerant quantum computing. For each representative of a spectral-equivalent class of Boolean functions with 4 and 5 inputs, the benchmark contains three different implementations: optimized for T-count, T-depth or number of qubits.
The paper [1] explains how a representative implementation can be used to generate a circuit for all Boolean functions in the same spectral-equivalent class, without increasing any of the indicated cost functions.
The algorithms used to generate the circuits optimized for the T-count and the T-depth are based on Xor-And-inverter Graphs (XAG) and are described in [1] and [2].
The algorithm that generates the circuits optimized for the number of qubits use ESOP-based synthesis and techniques from [3] and [4].
The benchmarks can be used in association with the LUT-based compilation method in [5] to generate quantum circuits implementing larger Boolean functions.
[1] G. Meuli, M. Soeken, M. Roetteler, G. De Micheli, Enumerating Optimal Quantum Circuits using Spectral Classification, ISCAS, 2020.
[2] G. Meuli, M. Soeken, E. Campbell, M. Roetteler, G. De Micheli, The Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits
[3] M. Amy, D. Maslov, M. Mosca, Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33(10), 2014.
[4] D. Maslov, On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization, Phys. Rev. A 93, 2016.
[5] G. Meuli, M. Soeken, M. Roetteler, G. De Micheli, ROS: Resource Constrained Oracle Synthesis for Quantum Computers, QPL, 2019.
| optimal T-count | optimal T-depth | optimal number of qubits | |||||||
|---|---|---|---|---|---|---|---|---|---|
| truth table | Qubits | T-count | T-depth | Qubits | T-count | T-depth | Qubits | T-count | T-depth |
| 8000 | 7 | 12 | 4 | 11 | 12 | 3 | 6 | 24 | 12 |
| 8080 | 6 | 8 | 3 | 8 | 8 | 2 | 5 | 16 | 8 |
| 0888 | 7 | 12 | 4 | 10 | 12 | 3 | 6 | 31 | 14 |
| 8888 | 5 | 4 | 2 | 7 | 4 | 1 | 5 | 7 | 3 |
| 7080 | 6 | 8 | 3 | 9 | 8 | 2 | 5 | 19 | 8 |
| 7880 | 8 | 12 | 4 | 11 | 12 | 3 | 6 | 36 | 13 |
| 7888 | 7 | 8 | 2 | 8 | 8 | 1 | 5 | 12 | 3 |
| 6ac06ac0 | 8 | 8 | 2 | 9 | 8 | 1 | 6 | 12 | 3 |
| 6ac8e000 | 10 | 16 | 5 | 15 | 16 | 2 | 6 | 63 | 28 |
| 80008000 | 8 | 12 | 4 | 12 | 12 | 3 | 6 | 24 | 12 |
| 80808080 | 7 | 8 | 3 | 9 | 8 | 2 | 6 | 16 | 8 |
| 88808000 | 9 | 12 | 4 | 11 | 12 | 3 | 6 | 26 | 11 |
| 88808080 | 9 | 16 | 4 | 12 | 16 | 3 | 7 | 48 | 21 |
| 88808880 | 8 | 12 | 4 | 11 | 12 | 3 | 6 | 31 | 14 |
| 88888888 | 6 | 4 | 2 | 8 | 4 | 1 | 6 | 7 | 3 |
| a8808000 | 10 | 16 | 5 | 13 | 16 | 3 | 7 | 54 | 22 |
| a8808080 | 8 | 12 | 4 | 11 | 12 | 3 | 6 | 40 | 20 |
| a8808880 | 10 | 16 | 5 | 12 | 16 | 3 | 7 | 55 | 22 |
| a880a880 | 7 | 8 | 3 | 10 | 8 | 2 | 6 | 15 | 6 |
| a8888880 | 8 | 12 | 4 | 11 | 12 | 3 | 6 | 27 | 12 |
| a888a080 | 8 | 12 | 4 | 11 | 12 | 3 | 6 | 55 | 24 |
| a8e0c800 | 10 | 16 | 5 | 12 | 16 | 3 | 7 | 87 | 36 |
| aa808080 | 9 | 16 | 4 | 12 | 16 | 3 | 7 | 65 | 28 |
| b884a880 | 9 | 12 | 4 | 11 | 12 | 3 | 6 | 32 | 13 |
| bc88a080 | 10 | 16 | 5 | 13 | 16 | 3 | 6 | 55 | 21 |
| e0a8c880 | 10 | 16 | 5 | 13 | 16 | 2 | 6 | 27 | 13 |
| e1808880 | 9 | 12 | 4 | 12 | 12 | 3 | 6 | 70 | 33 |
| e8808000 | 8 | 12 | 4 | 12 | 12 | 3 | 6 | 42 | 18 |
| e8808002 | 10 | 16 | 5 | 12 | 16 | 3 | 7 | 83 | 34 |
| e8808080 | 10 | 16 | 4 | 13 | 16 | 3 | 7 | 58 | 27 |
| e8808880 | 9 | 12 | 4 | 12 | 12 | 3 | 6 | 55 | 26 |
| e880a880 | 10 | 16 | 5 | 12 | 16 | 3 | 7 | 51 | 19 |
| e880e880 | 9 | 12 | 4 | 12 | 12 | 3 | 6 | 36 | 14 |
| e8818880 | 10 | 16 | 4 | 12 | 16 | 3 | 7 | 69 | 29 |
| e881e880 | 10 | 16 | 5 | 13 | 16 | 3 | 7 | 44 | 15 |
| e8888880 | 10 | 16 | 5 | 13 | 16 | 3 | 7 | 63 | 25 |
| e8a08880 | 10 | 16 | 5 | 13 | 16 | 3 | 7 | 89 | 38 |
| e8c0a880 | 10 | 16 | 5 | 12 | 16 | 3 | 6 | 47 | 21 |
| e9a0c088 | 10 | 16 | 5 | 13 | 16 | 3 | 7 | 65 | 24 |
| e9c0a880 | 10 | 16 | 5 | 13 | 16 | 3 | 7 | 79 | 32 |
| ea808080 | 9 | 12 | 3 | 12 | 12 | 2 | 6 | 42 | 18 |
| eca08880 | 10 | 16 | 5 | 13 | 16 | 3 | 6 | 47 | 22 |
| f8808880 | 10 | 16 | 4 | 13 | 16 | 3 | 7 | 79 | 32 |
| f8888880 | 9 | 12 | 4 | 12 | 12 | 3 | 6 | 29 | 11 |
| fca08880 | 10 | 16 | 5 | 13 | 16 | 3 | 7 | 68 | 25 |
| 2888a000 | 8 | 12 | 3 | 11 | 12 | 2 | 6 | 32 | 16 |
| 6ac8e240 | 10 | 16 | 5 | 12 | 16 | 3 | 6 | 44 | 17 |
| 78888888 | 9 | 12 | 4 | 13 | 12 | 2 | 6 | 19 | 8 |
| 80000000 | 9 | 16 | 4 | 11 | 16 | 3 | 7 | 34 | 15 |
| 80808000 | 9 | 16 | 4 | 11 | 16 | 3 | 7 | 58 | 26 |
| 88888880 | 10 | 16 | 4 | 11 | 16 | 3 | 7 | 41 | 15 |
| e9808080 | 8 | 12 | 4 | 13 | 12 | 2 | 6 | 27 | 13 |
| eac86240 | 9 | 12 | 4 | 11 | 12 | 3 | 6 | 19 | 8 |
| ee84a060 | 10 | 16 | 5 | 15 | 16 | 2 | 6 | 43 | 20 |