Compiling a classical function to a quantum circuit in practice

Question

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

Answer 1

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];

Answer 2

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.

Answer 3

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.