5
$\begingroup$

The question is quite straightforward. In classical computation, there exists several ways to build logical circuits based on thruth tables and Karnaugh maps. Is there anything equivalent for quantum computation?

Every circuit that I have made is mostly either guessing or saw someone else's answer and paved my way to it.

$\endgroup$
3
  • $\begingroup$ you can systematically build quantum circuits that do the same thing their classical counterparts do. It's worth stressing that this would not provide algorithms that give any advantage over classical computing. Quantum algorithms that outperform classical ones usually work in completely different ways, and there is no systematic way to find them as of yet (that I know of at least) $\endgroup$
    – glS
    Commented Mar 24, 2020 at 10:24
  • $\begingroup$ From the first part of your comment, can you reference me to any literature? How would I make a quantum circuit that would do the exact same thing as the classical counterpart? Is it a obvious proof? Couldn't it be a good starting point to any efficient algorithm? $\endgroup$
    – Bidon
    Commented Mar 24, 2020 at 10:29
  • $\begingroup$ @Bidon: Partial answer: you can implement any classical logical function with construction I provided at the begining of my answer below. Or since Toffoli gate implements NAND function, you can use these gates to build any logical function you can build "classicaly" because NAND is universal gate. However, as gIS mentioned, this way in not efficient and there is no speed-up on quantum computer in comparison with classical one. $\endgroup$ Commented Mar 24, 2020 at 11:07

1 Answer 1

4
$\begingroup$

Designing a logical function for quantum computer is similar to same process for classical one. You can also use truth tables. But you have to design the function to be reversible. Assume you have truth table for logical function $f(x): \{0;1\}^n \rightarrow \{0,1\}$, then reversible equivalent can be build in this way:

$$ |x_n\rangle |y\rangle \rightarrow |x_n\rangle |f(x_n) \oplus y\rangle. $$

You should do this for all basis quantum states. Then arrange mapping you got to a matrix. Because of construction above, the matrix is unitary. After that you have to decompose the matrix to some basic gates.

Any unitary 2x2 matrix (i.e. single qubit gate) can be decomposed into three matrices

$$ \begin{pmatrix} \mathrm{e}^{i\alpha} & 0\\ 0 & \mathrm{e}^{-i\alpha}\ \end{pmatrix} \begin{pmatrix} \cos (\theta/2) & \sin(\theta/2)\\ -\sin (\theta/2) & \cos (\theta/2) \end{pmatrix} \begin{pmatrix} \mathrm{e}^{i\beta} & 0\\ 0 & \mathrm{e}^{-i\beta}\ \end{pmatrix}, $$ $\alpha, \beta$ and $\theta$ being real numbers.

When you single out $\mathrm{e}^{i\alpha}$ from the first matrix and $\mathrm{e}^{i\beta}$ from the third, you get $U1$ gate (up to global phase) on IBM Q. A matrix in the middle can be implemented with gate $U3$ on IBM Q (or $y$ rotation up to phase). So, this is a universal approach how to build single qubit gate.

Any contolled gate (with one control qubit) can be decomposed to

$$ (I\otimes C) \,CNOT\, (I \otimes B)\, CNOT\, (I \otimes A), $$

where $I$ is and 2x2 unit matrix and $ABC = I$.

See Elementary gates for quantum computation for more information on three and more qubits gates.

Also these articles could be helpful:

$\endgroup$
5
  • $\begingroup$ Well yes, that is a quite straightforward way to make single qubit gates, but what about 2,3 and even 4 qubit circuits? We then have to account for several kinds of gates, even taking sometimes two qubit gates, or maybe three qubit gates. Classically Carnot maps are independent of the number of variables used, we can always apply it. But in QC that doesn't seem to be the case $\endgroup$
    – Bidon
    Commented Mar 24, 2020 at 10:22
  • 1
    $\begingroup$ @Bidon: Yes, you are right. The process is not very straighforward on quantum computers. I added two more articles on quantum gate decomposition, maybe they help. Besides, you mentioned Carnot map, did you mean Karnaugh map for logical function minimization? $\endgroup$ Commented Mar 24, 2020 at 11:02
  • $\begingroup$ @MartinVesely "After that you have to decompose the matrix to some basic gates" Do you? If the overall gate can be built from a truth table, presumably it's performing some classical algorithm. Then you can just use the elementary logic gates defining the classical algorithm and replace each one with its reversible counterpart. No need to further decompose the gate afterwards (well unless the gates implementing the elementary operations need to be decomposed) $\endgroup$
    – glS
    Commented Mar 24, 2020 at 11:17
  • $\begingroup$ @gIS: But what about NAND implemented by Toffoli? This gate is also decomposed to CNOTs, H, S and T gates. Or swap gate implemented by three CNOTs. $\endgroup$ Commented Mar 24, 2020 at 11:20
  • $\begingroup$ @MartinVesely Yes, I meant Karnaugh map. The pronounciation tricked me. Thank you $\endgroup$
    – Bidon
    Commented Mar 24, 2020 at 11:31

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.