3
$\begingroup$

As I've come across Grovers algorithm I dont understand why when computing F(X), which is an oracle function people use classical reversible circuits(toffoli, fredkin) to evaluate the circuit. Why can't it just be done using classical logic gates(and, or, etc) when the function doesn't have any thing to do with changing the superposition of the bits.

|cite|improve this question
$\endgroup$
  • $\begingroup$ basically toffoli gates can implement classical logic via quantum gates. the opposite is not possible. $\endgroup$ – vzn Jul 24 '14 at 19:15
3
$\begingroup$

Reversible gates are unitary, see for example https://en.wikipedia.org/wiki/Quantum_gate. The eigenvalues are $\pm 1$. The quantum computation model requires all gates to be unitary, so you can't just use classical gates.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ But this says toffoli is not unitary. I'm confused. $\endgroup$ – CSK Jul 24 '14 at 18:01
  • 1
    $\begingroup$ No it doesn't. It says it's not universal, that is, you can't implement all unitary transformations using only this gate. $\endgroup$ – Yuval Filmus Jul 24 '14 at 18:05
  • $\begingroup$ okay, so classical reversible gates is a subset of quantum gates? ie.,all quantum gates are unitary but all classical reversible gates are not. $\endgroup$ – CSK Jul 24 '14 at 18:07
  • $\begingroup$ This appears to be the case. $\endgroup$ – Yuval Filmus Jul 24 '14 at 18:08
  • $\begingroup$ but note (as that other Q/A points out) toffoli gates are universal from the pov of classical circuits. $\endgroup$ – vzn Jul 24 '14 at 18:30

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.