2
$\begingroup$

I see that Toffoli and Hadamard gates are "universal for quantum calculation". This paper by Aharonov says that this universality has a slightly wider meaning than usual. This is clear from the fact that Toffoli and Hadamard gates are represented by matrices composed by real numbers, so they do not know anything about phase rotations and other gates that have imaginary numbers in their matrix. This is explained e.g. in this previous answer.

The matrices representing Toffoli and Hadamard gates are not only represended by real numbers, but, if we neglect a global real normalization factor, they are only composed by 0, 1, and -1. So we could work with them using amplitudes represented by integer numbers (times a global real normalization factor).

However, I still do not understand the extended definition of universality.

i) In the paper of Aharonov, the "universality" is still defined as the ability of approximating any other gate (definition 3). This is puzzling for me.

ii) On the other hand, this post suggests that the "universality" of Toffoli and Hadamard gates means that such circuits are able to perform BQP calculations. It is a weaker but very interesting statement.

iii) There is yet another interpretation, i.e. that Toffoli and Hadamard gates can implement any gate, if provided with suitable ancillae.

Probably my interpretation of (i) is wrong. (ii) says that we can perform the decision in BQP using circuits involving only real and integer numbers. Fascinating, but is it true? Probably (iii) is true, but it does not tell us too much about the possibility of quantum calculations with integer numbers, because the ancillae contain complex numbers.

Improve this question
$\endgroup$
7
  • $\begingroup$ Can you explain what you mean by “integer numbers”? Do you mean that arbitrary amplitudes are precluded, without being able to rotate by a continuous abgle? The Solovay-Kitaev theorem is still applicable to Hadamard+Toffoli. Other gate sets such can still only explore a discrete subset of the Hilbert space in polynomial time. $\endgroup$
    – Mark Spinelli
    Feb 7, 2022 at 18:03
  • $\begingroup$ I edited the question to clarify. Starting from $\left|0\right>$, the amplitudes obtained by applying any sequence of Toffoli and Hadamard gates can be represented with integer numbers, times a global normalization factor, which is a real number. $\endgroup$
    – Doriano Brogioli
    Feb 7, 2022 at 20:05
  • $\begingroup$ @Mark S: do you claim that you can approximate e.g. S, the phase shift of $\pi/2$, with Hadamard and Toffoli gates? With or without suitably prepared ancillae? $\endgroup$
    – Doriano Brogioli
    Feb 7, 2022 at 20:08
  • $\begingroup$ I don't know and there's a lot of subtleties that I don't fully grok yet (although there are a lot folks who frequent this site who most certainly do). "Approximating" might be too strong, I believe "emulating" or "encoding" would be better? You could do the interpretation of (iii) above, twice in a row, to get $S=T^2$, for example. $\endgroup$
    – Mark Spinelli
    Feb 7, 2022 at 22:33
  • $\begingroup$ The point is that the matrices representing Toffoli and Hadamard gates are made of real numbers, so, there is no way to get an imaginary number (contained in the matrix for S) from them. So (i) should be wrong. Alternatively you can insert the imaginary numbers from the initial state, in the form of ancillae, as in (iii). I got this. But my question is: what can we do without imaginary numebrs? Is (ii) really viable? This is the question in the title. $\endgroup$
    – Doriano Brogioli
    Feb 8, 2022 at 9:02

1 Answer 1

Reset to default
2
$\begingroup$

There is no discrepancy among (i), (ii) and (iii).

The basic idea is that $\{T, H\}$ is computationally universal and you can simulate any quantum circuit with it though overhead qubits may be necessary. However, that isn't the same thing as approximately decomposing an arbitrary quantum gate into some sequence of $\{T, H\}$ gates.

If you look at Aaronhov's paper (theorem 2), they clearly mention that they're simulating $\Lambda(P(i))$ which has complex entries by converting it to its real version using overhead qubits.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So the first step is to "simulate" the gates with the Bernstein and Vazirani method of representing them with real numbers, summarized as definition 1 in the paper of Aaronhov. If I understand correctly, this can be done with integers as well, so the answer to the question in the title is "yes, it can be done". Can you please explicitly confirm? $\endgroup$
    – Doriano Brogioli
    Feb 9, 2022 at 9:36
  • 1
    $\begingroup$ @DorianoBrogioli Yes. That's correct. It's not too surprising even when imaginary numbers are involved because the action of $i$ is algebraically equivalent to the action of the matrix $[0, 1; -1, 0]$ once you separate the real and imaginary parts of the wavefunction. $\endgroup$
    – Sanchayan Dutta
    Feb 10, 2022 at 0:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.