# Complexity of $n$-Toffoli with phase difference

I'm interested in the $$n$$-Toffoli gates with phase differences. I found a quadratic technique in section 7.2 of this paper.

Here's the front page of the paper.

Here's an image of the section that I'm referring to.

Does anyone know if there has been any improvement on the decomposition of the general n-qubits control X with phase differences in terms of elementary gates up to this day? Phase differences have to be consistent but not need fixing. Feedback is not allowed and no ancilla qubits are used.

And also what is the theoretical lower bound?

• What is it that you're wanting improved? That circuit, or the decomposition of that circuit in terms of elementary gates? Jun 21, 2021 at 6:56
• @DaftWullie I want to improve the decomposition of the general n-qubits control X with phase differences in terms of elementary gates. Jun 21, 2021 at 18:07
• Is it acceptable for the phase differences to be different from run to run, and expensive to fix? Is feedback allowed? How many ancilla qubits? Jun 21, 2021 at 23:48
• Phase differences have to be consistent and does not need fixing. Feedback is not allowed and no Ancilla qubits are used. Jun 22, 2021 at 3:31
• There is a paper dealing with mulitply controlled NOTs (and SWAPs and QFTs) without phase error using control theoretical optimized building blocks: Quantum CISC Compilation by Optimal Control and Scalable Assembly of Complex Instruction Sets beyond Two-Qubit Gates Jun 27, 2021 at 17:56

(This answer uses ancillae and feedback)

Does anyone know if there has been any improvement on the decomposition of the general n-qubits control X with phase differences in terms of elementary gates up to this day? [...] And also what is the theoretical lower bound?

About a week ago I would have told you it's probably not possible to do better than a T cost of $$4n \pm O(1)$$. But then, well...

Here's a construction that reduces an $$n$$-control Toffoli into an $$n-2$$ control Toffoli, with a 50/50 chance of introducing heralded phase error on the controls. It uses 6 T gates, 1 ancilla, 12 stabilizer gates, and classical feedback.

By iterating this construction, you can perform an $$n$$-control Toffoli with relative phase error using $$3n$$ T gates, $$n/2$$ ancillae, and $$6n$$ stabilizer gates.

The downside is that you will eventually need to correct the relative phase error, and this will cost you more than $$n$$ T gates so you ultimately come out behind vs just using ANDs to temporarily merge controls which has a total cost (including eventually fixing the phase error) of $$4n$$ T gates (that construction is explained in halving the cost of quantum addition).

• I read your blog posts, and I have questions regarding some of the decomposition. For part 1, the final decomposition that uses 1 Ancilla bits the same as that of section 7.1 of the Barenco et al. paper. Also, for part 3, the bootstrap gate is the same as that of section 7.4 of the same paper. Am I correct in assuming this? Jun 22, 2021 at 14:16
• @user13500265 Yes, that's right. The "hard part" of bootstrapping the ancilla was closing the gap between those two parts by realizing I needed an increment and finding the linear cost increment that only used borrowed ancillae. Jun 22, 2021 at 14:53

Feedback is not allowed and no ancilla qubits are used.

Here's a relative-phase-error no-ancilla $$C^n X$$ construction with a T count of $$12n \pm O(1)$$.

I think it's easiest to understand as $$3n \pm O(1)$$ Toffoli gates with $$O(1)$$ other gates:

(The left hand side might not look like it only has relative phase error, but you can propagate the CCZ out of the Toffolis creating a more complicated looking phase error, and then all the Toffolis cancel out.)

The basic ideas in this construction are:

1. Start with the bootstrap ancilla circuit, but throw out the increments and phase gates on the controls since those are just to correct relative phase error. Also, instead of dividing the controls into two groups of wildly mismatched sizes, divide them into two evenly sized groups.

2. Each control group must control an X gate in two places in the circuit. Use the n-borrowed-ancilla $$C^n X$$, but conjugate the borrowed ancilla with Hadamards. This switches the direction of the Toffolis, and means that leaving out the "second mountain" in the construction that does not touch the target results in phase error instead of permutation error. We're fine with phase error, so leave out the second mountain.

3. Because the Toffolis all come in matched pairs, the mountain phase error from leaving out a moutain is free to commute across the circuit. And because the control group X gates each occur twice, this makes the mountain phase error all cancel out.

4. One of the control group Xs is next to a hadamard on the side of the circuit. It's actually a phase correction. Turn it into phase error by moving it to the left hand side of the equality.

5. Propagate the target Hadamard across the circuit, which ultimately makes it look simpler.

6. When decomposing the Toffolis into Clifford+T, you will want to use the 4T decomposition that has a phase kickback on the controls. Because the Toffolis in each mountain come in matched pairs whose controls are applied to the same computational basis states, the phase kickback from one member of the pair can be cancelled against the kickback from the other.

• > Note that almost all the Toffolis come in matched pairs, so if you wanted to use T gates instead of Toffolis it should take 4 Ts per Tof instead of 7. How do you replace the Toffoli gates by T gates? Jun 23, 2021 at 7:51
• @MinhPham Take the 7 T construction then discard all the Ts on the control qubits. Jun 23, 2021 at 10:57