# What happens if we change $\mathcal{BQP}$ to allow quantum bits, but not quantum gates?

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).

• Can you simulate your model classically, perhaps using random bits for the final measurement? If so, then you should get BPP. Nov 14, 2021 at 15:17
• @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) Nov 14, 2021 at 19:53
• You can answer your own question, then. Nov 14, 2021 at 19:55
• @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. Nov 15, 2021 at 14:37
• 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.) Jan 23, 2022 at 22:26

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).
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.)