5
$\begingroup$

It can be shown that any classical function $f$ can be implemented by a quantum circuit $Q_f$, so that $$ \sum_{x}|x,0^k\rangle \xrightarrow{\mathit{Q_f}} \sum_{x}|x,f(x)\rangle $$ where $f$ has $k$ output bits, and ingnoring normalization. I have seen such circuits called quantum oracles and treated as black boxes in quantum algorithms. If I want to write a quantum computer program that includes the circuit $Q_f$, it is convenient to write a classical program for $f$ in a high level language (like C or Java or python) and have it compiled to a quantum circuit.

My question is: is there an implementation of a compiler (preferably open source) that will compile my classical high-level program for $f$ into some representation of the quantum circuit $Q_f$ (e.g. using OpenQASM)? If not, is there a compiler that will compile into reversible gates?

Thanks!
kgi

$\endgroup$
  • $\begingroup$ Not super sure, but I'd guess not - are there many compilers that take classical programs and convert them into a classical gate representation? I think there are a lot of challenges because "high-level" classical is like, sky-high quantum. Realistically, you'd need a compiler that can turn a function into a series of reversible gates (preferably NOT/Toffoli), which would then be the gate sequence you need $\endgroup$ – C. Kang Jun 16 at 21:23
  • 1
    $\begingroup$ In the classical case, most compilers will output a language close to the architecture of the platform in question (e.g. assembly, object code, machine code). In the quantum case, there is OpenQASM which uses quantum gates. Perhaps there will eventually be different quantum assembly languages for different quantum computer architectures, but for now it seems most quantum algorithms are expressed in terms of gates. You are right, reversible gates would be a good start. $\endgroup$ – kgi Jun 17 at 4:56
4
$\begingroup$

Using Qiskit you can compile a boolean function to a Quantum circuit. 2 options are available: Using a logical expression LogicalExpressionOracle() or a thuth table TruthTableOracle().

The Logical Expression Oracle constructs circuits for any arbitrary input logical expressions. It also supports input strings in the DIMACS CNF format, for specifying SAT problems.

an example with LogicalExpressionOracle()

from qiskit.aqua.components.oracles import TruthTableOracle, LogicalExpressionOracle
expression = 'Or(And(v0, v1, v2), And(~v0, ~v1, ~v2))'
#expression = '(v0&v1&v2) | (~v0&~v1&~v2)'
oracle=LogicalExpressionOracle(expression, optimization=True)

# then get the OpenQasm code from the circuit 
print(oracle.circuit.qasm())
OPENQASM 2.0;
include "qelib1.inc";
qreg v[3];
qreg c[2];
qreg o[1];
mcx v[0],v[1],v[2],c[0];
u3(pi,0,pi) c[0];
x v[0];
x v[1];
x v[2];
mcx v[0],v[1],v[2],c[1];
u3(pi,0,pi) c[1];
x v[0];
x v[1];
x v[2];
u3(pi,0,pi) o[0];
ccx c[0],c[1],o[0];
u3(pi,0,pi) c[0];
u3(pi,0,pi) c[1];
mcx v[0],v[1],v[2],c[0];
x v[0];
x v[1];
x v[2];
mcx v[0],v[1],v[2],c[1];
x v[0];
x v[1];
x v[2];
| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Patrick, that's very useful. However it's still a far cry from expressing the classical function in a high-level language like C. Let's see what others come up with. $\endgroup$ – kgi Jun 18 at 6:14
0
$\begingroup$

In theory:

Any classical algorithm can be expressed in an assembly language containing instruction of a processor. Any instruction is somehow connected with a logical circuit(s) composed of logical gates. Any logical gate can be decomposed to basic gates (for example NAND or set consisting of AND, OR and NOT).

Toffoli gate implements AND which can be easily converted to universal NAND. Hence any classical algorithm (code) can be implemented on quantum computer. Resulting quantum circuit can be simplified and after that expressed in assembly language of a quantum processor.


To sum up, in theory it is possible to convert any classical code into quantum code (gates, QASM etc.). However, this seems to be difficult to do in practice. Maybe, this can be done only for the simplest codes.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks Martin. I agree it can be done. My question was whether anyone has written such a compiler yet. ScaffCC used to have what they called CTQG compilation (Classical To Quantum Gate) but they have removed it from their code base. $\endgroup$ – kgi Jun 17 at 10:09
0
$\begingroup$

Yes, here it is: this project (https://github.com/softwareQinc/staq) attempts to synthesize Verilog code to OpenQASM.

As you may know, the Verilog is used to build very complex/large classical circuits, which can implement any functions.

The project has limitations because it supports only a small subset of the Verilog. Though it is hard to prove mathematically what is the minimum subset of the Verilog required to implement all the functions, the project is useful enough to implement a lot of non-trivial functions.

There is another practical drawback: that project has a few critical bugs that prevent it from doing what is supposed to do. When they are fixed by the project owner, it should give you what you want.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Emscripten Fan, looks like something to keep an eye on. Although verilog appears to be a low level language, there are tools to compile e.g. C to verilog. I will look into it further. Thanks for the heads up that the project only supports a subset of verilog. $\endgroup$ – kgi Jun 27 at 12:38
  • $\begingroup$ In addition to this I would research how high level code is compiled onto FPGAs, this would be a very similar process. $\endgroup$ – Sam Palmer Jun 27 at 15:35
  • $\begingroup$ I might as well mention that the people at University of California, Berkeley did some work many years ago with Scala. Here it is people.eecs.berkeley.edu/~kubitron/papers/qarc/pdf/Chisel-q.pdf, I didn't say it earlier because you prefer open source. They have never published their code and have done very little follow-up work since 2013. I am interested in this area too. If you find out any new development of the project, please let us know. $\endgroup$ – Emscripten Fan Jun 27 at 23:03
  • $\begingroup$ Thanks for the tip Sam $\endgroup$ – kgi Jun 29 at 9:08
  • $\begingroup$ will keep you posted Emscripten Fan $\endgroup$ – kgi Jun 29 at 9:09

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.