Sick of using Qiskit for the implementation of quantum circuits—they change and broke the APIs with each release— I decided to implement a CL library that allows the definition of quantum circuits and translates the code into openQASM v2.0. The library CLQ is already almost 2 years old but, being occupied with other things, I didn’t use it in big projects; just some minor circuits like 4 qubits adders, 4 qubits Grover and so on. From the development I noticed a weak point in not having n-qubits Toffoli gates. And somehow, I avoided the library until I decided to implement a quantum genetic algorithm using it.
A n-qubits Toffoli gate is relatively easy to implement using ancilla qubits. I won’t dive into the circuit, but the basic idea is to use CCNOT gates to change the state of the ancilla qubits, and finally, use a CNOT with the last ancilla qubit as control. But this technique requires a lot of qubits and, in my circuit, to implement a simple knapsack solver it required over 32 qubits, with most of them being ancilla. That’s a waste and one cannot simulate that on a machine using Qiskit, QVM (my new favourite), or others.
Thus, welcome to the Barenco et all. Elementary gates for quantum computation. After studying the paper, I started to write some qasm to define a base case, and after defining CNOTS with 2 control qubits, I jumped to 3 control qubits and so on.
Therefore, using CLQ library I implemented the decomposition for a CCNOT gate:
(defun barenco-decomposition (qc ctrl-reg-0 ctrl-0 ctrl-reg-1 ctrl-1 target-reg targ) (clq:hgate qc target-reg targ) (clq:cxgate qc ctrl-reg-1 ctrl-1 target-reg targ) (clq:tdggate qc target-reg targ) (clq:cxgate qc ctrl-reg-0 ctrl-0 target-reg targ) (clq:tgate qc target-reg targ) (clq:cxgate qc ctrl-reg-1 ctrl-1 target-reg targ) (clq:tdggate qc target-reg targ) (clq:cxgate qc ctrl-reg-0 ctrl-0 target-reg targ) (clq:tgate qc ctrl-reg-1 ctrl-1) (clq:tgate qc target-reg targ) (clq:hgate qc target-reg targ))
and then I started to think about how to use 3,4,5,etc. controls. (By the way, LLMs are pretty stupid, I would say quite idiots, at implementing it, giving the same incorrect code over and over again.)
(defun mcx-no-ancilla (qc ctrl-reg ctrl-pos target-reg targ) (let ((len (length ctrl-pos))) (cond ((= len 0) (clq:xgate qc target-reg targ)) ((= len 1) (clq:cxgate qc ctrl-reg (car ctrl-pos) target-reg targ)) ((= len 2) (barenco-decomposition qc ctrl-reg (nth 0 ctrl-pos) ctrl-reg (nth 1 ctrl-pos) target-reg targ)) ((> len 2) (dotimes (i (- len 2)) (barenco-decomposition qc ctrl-reg (nth i ctrl-pos) ctrl-reg (nth (+ i 1) ctrl-pos) target-reg targ)) (clq:cxgate qc ctrl-reg (car (last ctrl-pos)) target-reg targ) (dotimes (i (- len 2)) (barenco-decomposition qc ctrl-reg (nth i ctrl-pos) ctrl-reg (nth (+ i 1) ctrl-pos) target-reg targ))))))
Finally, we can define the circuit as
(defun build-circuit () (let* ((qreg (clq:make-qregister 8 "qr")) (creg (clq:make-cregister 8 "cr")) (qc (clq:make-qcircuit (list qreg) (list creg)))) (dotimes (i 7) (clq:xgate qc qreg i)) (mcx-no-ancilla qc qreg (list 0 1 2 3 4 5 6) qreg 7) (dotimes (i 8) (clq:measure qc qreg i creg i)) (clq:save-openqasm-to-file qc "test.qasm")
And simulate it using QVM or Qiskit (YAC!) or other simulators.
¶Later edit
Furthermore, we can define different multi-controlled gates, like for the H,S,T gates.
(defun mch-no-ancilla (qc ctrl-reg ctrl-pos target-reg targ) (let ((len (length ctrl-pos))) (cond ((= len 0) (clq:hgate qc target-reg targ)) ((= len 1) (clq:chgate qc ctrl-reg (car ctrl-pos) target-reg targ)) ((= len 2) (clq:cchgate qc ctrl-reg (car ctrl-pos) ctrl-reg (car (cdr ctrl-pos)) target-reg targ)) ((> len 2) (dotimes (i (- len 2)) (barenco-decomposition qc ctrl-reg (nth i ctrl-pos) ctrl-reg (nth (+ i 1) ctrl-pos) target-reg targ)) (clq:chgate qc ctrl-reg (car (last ctrl-pos)) target-reg targ) (dotimes (i (- len 2)) (barenco-decomposition qc ctrl-reg (nth i ctrl-pos) ctrl-reg (nth (+ i 1) ctrl-pos) target-reg targ)))))) (defun mcs-no-ancilla (qc ctrl-reg ctrl-pos target-reg targ) (let ((len (length ctrl-pos))) (cond ((= len 0) (clq:sgate qc target-reg targ)) ((= len 1) (clq:csgate qc ctrl-reg (car ctrl-pos) target-reg targ)) ((= len 2) (barenco-decomposition qc ctrl-reg (nth 0 ctrl-pos) ctrl-reg (nth 1 ctrl-pos) target-reg targ)) ((> len 2) (dotimes (i (- len 2)) (barenco-decomposition qc ctrl-reg (nth i ctrl-pos) ctrl-reg (nth (+ i 1) ctrl-pos) target-reg targ)) (clq:csgate qc ctrl-reg (car (last ctrl-pos)) target-reg targ) (dotimes (i (- len 2)) (barenco-decomposition qc ctrl-reg (nth i ctrl-pos) ctrl-reg (nth (+ i 1) ctrl-pos) target-reg targ)))))) (defun mct-no-ancilla (qc ctrl-reg ctrl-pos target-reg targ) (let ((len (length ctrl-pos))) (cond ((= len 0) (clq:tgate qc target-reg targ)) ((= len 1) (clq:ctgate qc ctrl-reg (car ctrl-pos) target-reg targ)) ((= len 2) (barenco-decomposition qc ctrl-reg (nth 0 ctrl-pos) ctrl-reg (nth 1 ctrl-pos) target-reg targ)) ((> len 2) (dotimes (i (- len 2)) (barenco-decomposition qc ctrl-reg (nth i ctrl-pos) ctrl-reg (nth (+ i 1) ctrl-pos) target-reg targ)) (clq:ctgate qc ctrl-reg (car (last ctrl-pos)) target-reg targ) (dotimes (i (- len 2)) (barenco-decomposition qc ctrl-reg (nth i ctrl-pos) ctrl-reg (nth (+ i 1) ctrl-pos) target-reg targ))))))