How to calculate quantum cost of a reversible logic circuit?

I am trying to develop new reversible logic synthesis algorithm. But I need a good quantum cost measure for a synthesized circuit to compare my results with existing ones.

For now I'm using RCViewer+ software to calculate quantum cost of a circuit. Unfortunately, I was told that this software is based on an outdated technique and that I should use "T-count for fault tolerant logical-level implementations".

My questions are:

1. Which quantum cost measure is the most up-to-date and widely used?
2. Is there any software to calculate it automatically?
• if yes, which input format for a circuit should I use?

If it is matter, my software produces circuits consisting of Toffoli gates with multiple control inputs, both positive and negative ones.

• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization chapter 4 A. Circuit cost ( about this ... ) : may help – user46925 Jan 16 '16 at 11:13
• @igael, thank you, I've read this paper. It helps, but not entirely, because all implementations I can see in the paper are for Toffoli gates without negative control inputs and they almost always require ancilla qubits, which is not always possible in my case. – Dmitriy Zakablukov Jan 16 '16 at 11:46
• The cost measure depends on what you are building the circuit for, i.e., which are the costly operations in your hardware. Thus, there is no unique answer to your question. Having said that, in many error correction schemes Clifford gates are much easier to realize in a robust way than other gates, so one often only counts those other gates (such as the T gate). – Norbert Schuch Jan 16 '16 at 13:38

Thanks to Dr. Dmitry Maslov, now I'm able to answer my own question.

Among all quantum cost metrics the most popular are:

1. The number of elementary quantum gates required for an implementation of a reversible circuit. The calculation of this cost metric is based on the following papers:

The table with Toffoli gates cost can be found here. In short, the cost of a Toffoli gate of size $k$ in a circuit with $n$ inputs is $QC = 2^k$, if $k=n$, $QC = 24n - 88$ if $k \leq n - 1$ and $QC = 12n - 34$ if $k \leq \frac{n+3}{2}$.

The quantum cost of generalized Toffoli gates with at least one positive control is the same as those with all positive controls. The quantum cost of generalized Toffoli gates with all negative controls is increased by 2.

RCViewer+ is capable to calculate this quantum cost automatically. A circuit's file should be in the TFC format.

2. The number of $T$ gates required for an implementation of a reversible circuit using Clifford+$T$ gates ($T$-count). This cost metric is used for fault tolerant circuits, because the cost of any Clifford gate is very low compared to the cost of a $T$ gate. But unlike the previous cost metric, this one is not universal: if a circuit with $n$ inputs has a Toffoli gate of size $n$, it cannot be implemented using Clifford+$T$ gates and without an ancillary line. Hence, it is not possible to calculate the $T$-count cost for such circuit if no ancillary line is available.

The calculation of this cost metric is based on the following paper:

In short, the $T$-count cost of a Toffoli gate of size $k$ in a circuit with $n$ inputs is $QC = 8k - 16$, if $k \leq \lfloor \frac{n+3}{2}\rfloor$. Otherwise, one should apply the Lemma 7.3 from "Elementary gates for quantum computation", obtain four new Toffoli gates and calculate their cost by the formula. If $k = n$, then one ancillary line is required to apply this cost calculation.

A Toffoli gate with negative control lines has the same $T$-count cost as the Toffoli gate without them, because NOT and CNOT gates don't require any $T$ gate for their implementation.

For now, there is no any software capable to calculate this cost metric automatically. RCViewer+ can calculate the quantum cost in "2-qubit cost model", which is close to the $T$-count, but the formula it used for the calculation is $QC = 10k - 25$ (see "Reversible Circuit Optimization via Leaving the Boolean Domain").

I've written a simple Python script to calculate the $T$-count cost of a reversible circuit, consisting of Toffoli gates. A file with its description should be in the TFC or the REAL format. Hope it will be useful for someone.