3
$\begingroup$

BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In quantum computer allowed operations can be represented by unitary matrices. In general, unitary matrices do not commute with each other.

My question is what would be BQP analog for a quantum computer where only unitary matrices that commute with each other are allowed?

$\endgroup$
3
$\begingroup$

There isn't a one word answer to your question, but you can have a look at

Xiaotong Ni's master thesis,

where commuting circuits with several restrictions are considered and compared to classical classes. There you can also find the definition of the class IQP, which is a subclass of polynomial size commuting Pauli circuits.

$\endgroup$
  • $\begingroup$ Commuting Pauli circuits are pretty limited, doesn't IQP have to do with circuits of gates commuting with $X$? $\endgroup$ – Niel de Beaudrap Aug 30 '14 at 20:12
  • $\begingroup$ @NieldeBeaudrap Maybe there is ambiguity in the definition of Pauli circuits. I meant the same definition used in Xiaotong's thesis. $\endgroup$ – Alessandro Cosentino Aug 30 '14 at 20:40
  • $\begingroup$ Anyway, I just mentioned that class because the OP asked for a specific class whose definition concerns commutativity of the gates. $\endgroup$ – Alessandro Cosentino Aug 30 '14 at 20:46
  • $\begingroup$ @AlessandroCosentino - Please accept my invitation to: quantumcomputing.stackexchange.com . $\endgroup$ – Rob Apr 4 '18 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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