Typically the notion of quantum Turing machine is introduced with its transition function.

$$ \delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}} $$

Where $\mathbb{C}'\subseteq\mathbb{C}$ is a computable subset of $\mathbb{C}.$ This sort of definition basically gives any 1-qubit unitary gates "for free," you only need one step to perform any such unitary transform.

We knew that there's Solovay Kitaev theorem saying that any single qubit transformation could be approximated by a finite set of gates, but sometimes it still require more than $\Omega(1)$ gates to do this (grow with the precision). So it's natural to ask whether there exist an "efficient" approximation, so that when we're using just regular gates, the complexity would be roughly the same. (e.g. with only some polynomial amount of resources added up).

Let's say we're given another QTM with transition $\delta'$ only allowing $O(1)$ gates as a generating set of a dense subset of $SU_2(\mathbb{C})$, then we redefine the $BQP_{\delta'}$ with it, is it the case that $BQP_{\delta'}=BQP_{\delta}$?


1 Answer 1


After a while I look back on this problem. It turns out using universal gates to generate constant-qubit gates would make no difference to BQP class. The gate complexity, however, depends on $\epsilon$ for the error we try to bound, but precision could be reached in $poly(-\log{\epsilon})$ number of operations.


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.