13
$\begingroup$

Background:

In most setups of fault-tolerant quantum computation, universality is achieved using Clifford gates such as $(S, H, \text{CNOT})$ and the $T$-gate.

The Eastin-Knill theorem can be informally stated that it will be difficult (although possible through circumvention) to implement a universal set of gates fault-tolerantly.

Question:

The Quantum Fourier Transform is an important primitive, but does there exist a finite gate set which is non-universal that generates the Quantum Fourier Transform?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Note that when executed at the end of a circuit, followed by a measurement in the computational basis (such as in Shor's algorithm), the QFT can be implemented using single-qubit gates alone, in which case it is definitely not universal. $\endgroup$
    – Norbert Schuch
    Commented Apr 15 at 18:41

1 Answer 1

Reset to default
18
$\begingroup$

Yes, the QFT requires universality. No, there isn't a non-universal gate set that implements the QFT. Just having the QFT as an operation is already computationally universal, because it can generate H+TOFFOLI:

enter image description here

Therefore anything that generates the QFT must also be computationally universal.

I bet you can prove the 2-qubit QFT is fully universal on its own, not just computationally universal, since it's non-Clifford and just randomly putting some together seems to generate weird looking angles.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Follow-up question: how did you come up with these equivalences so quickly? $\endgroup$
    – Sam Jaques
    Commented Apr 17 at 0:04
  • 3
    $\begingroup$ @SamJaques I used algassert.com/quirk . I set up Bell pairs to see the unitary matrix in the output display via the state channel duality, then tried simple repeating patterns of QFTs to see if useful matrices appeared. Then I assembled those into more well known operations. The hardest one to find was the X gate. It's surprisingly useful to just try one basic random thing per five seconds for five minutes, before thinking too hard about it. $\endgroup$
    – Craig Gidney
    Commented Apr 17 at 1:45
  • $\begingroup$ Cool equivalences! Interestingly, the two 2-qubit QFTs are equivalent to a CX (ZNOT). As 1-qubit QFT=H, H ZNOT H = X controlled-Not (XNOT), so we can simplify further to XNOT,ZNOT,XNOT,ZNOT = IX. $\endgroup$
    – Balint Pato
    Commented Apr 18 at 19:25
  • 1
    $\begingroup$ @BalintPato Yup, that's right. But I have to admit it's funner to sometimes just dump the circuit and leave people asking why. I almost did the Toffoli with the X gates decomposed but that probably would have been too much. $\endgroup$
    – Craig Gidney
    Commented Apr 18 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.