3
$\begingroup$

In the definition of the class $\mathcal{BQP}$ found in textbooks we (as the circuit builders) have access to an unlimited number of deterministic zero-initialized qubits and to a finite set of quantum gets (it turns out that some sets of gates are universal). I'm struggling to make the definition of $\mathcal{BQP}$ intuitive for me and to figure out which parts are essential. What would happen if we were to only allow the Toffoli gate (which is universal for classical computation) and an unlimited number of qubits, each with a state chosen from a finite set? The question arises, are some sets of qubits universal, that is no other set induces a bigger complexity class? If so, what is this maximal complexity class?

When going from deterministic to randomized computation it is enough to have random bits and no random gates, and $\mathcal{NP}$ could I think also be defined in terms of "nondeterministic" bits, so that makes me wonder if the same can be done for quantum computation (and if, as I expect, not, then why not).

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you simulate your model classically, perhaps using random bits for the final measurement? If so, then you should get BPP. $\endgroup$
    – Yuval Filmus
    Commented Nov 14, 2021 at 15:17
  • $\begingroup$ @YuvalFilmus I may have gotten it: since the Toffoli gate matrix just swaps two amplitudes between strings, the qubits turn out to be equivalent to random bits (with probability equal to the squared amplitude of outcome 1) $\endgroup$
    – acupoftea
    Commented Nov 14, 2021 at 19:53
  • $\begingroup$ You can answer your own question, then. $\endgroup$
    – Yuval Filmus
    Commented Nov 14, 2021 at 19:55
  • $\begingroup$ @YuvalFilmus If my guess was right then it was luck, I can't make a precise argument. The amplitudes can interfere destructively and then it's not easily equivalent to random bits. $\endgroup$
    – acupoftea
    Commented Nov 15, 2021 at 14:37
  • $\begingroup$ What measurements do you allow for? I think this is universal unless you restrict the measurements. (Happy to post an answer once this is clarified.) $\endgroup$
    – Norbert Schuch
    Commented Jan 23, 2022 at 22:26

1 Answer 1

Reset to default
2
$\begingroup$

This is universal for BQP, unless you put strong restrictions on the allowed measurements.

To start with, if you apply the Toffoli to a target qubit in the $\lvert-\rangle$ state, you get a Controlled-Z (CZ) gate.

Using the CZ gate and initial $\lvert+\rangle$ states, you can create the cluster state (in fact, on any lattice of your liking).

Once you have the cluster state, you can carry out universal quantum computations in you allow for measurements in a discrete set of directions in the XY-plane. (You don't need Z measurements if you create the cluster state on the right graph right away.)

Finally, I suspect that you could even further restrict the required measurements - I would strongly suspect down to only an X measurement. The idea would be to create the cluster state "on the fly" as you measure, and then start from a suitably rotated state in the XY plane rather than the $\lvert+\rangle$ state; this should effectively give you the ability to measure in any direction in the XY plane you want. (There's a subtlety that you have to make this choice before you measure the preceding site, but I don't think this matters.)

On the other hand, measuring in the Z basis only is indeed efficiently simulatable classically, since the Z measurement can be "pushed" through the Toffolis, to give another Z measurement on the initial product state with some classical relabeling of measurement outcomes.

Improve this answer
$\endgroup$

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.