4
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
4
  • $\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, 2014 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, 2014 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, 2014 at 20:46
  • $\begingroup$ @AlessandroCosentino - Please accept my invitation to: quantumcomputing.stackexchange.com . $\endgroup$
    – Rob
    Apr 4, 2018 at 2:11

Your Answer

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

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