Although with some yet severe limitations, Physical working Quantum Computers are becoming available for end users. Such devices are based on the rules of Quantum Mechanics, which state that physical systems evolve through unitary transformations. However, as in the classical case, in order to have a model of computation, such unitary evolutions are expressed/approximated inside Quantum Computers in terms of a finite set of one/two qubit operations (i.e., through a universal set of gates). Single qubit gates are fault-tolerant, while the same cannot be said for two qubit gates. Hence, unitary matrices adopted in Quantum Algorithms must be synthesized in terms of this universal set of operations to obtain a quantum circuit. In such synthesis procedure we prefer circuits with minimum number of qubits and with minimum circuit depth. Cliford+T universal set is one of the most adopted in the literature for synthesis. In such set we have 3 single qubit gates and the CNOT, which is a two qubit gate. Many eforts have been directed to devise algorithms that synthesize general unitary matrices into Cliford+T circuits. These algorithms usually tend to optimize circuit depth or eventually the number of T gates. Since two qubit gates are not fault tolerant, in this work we propose an ASP based technique to minimize the number of CNOT gates inside a Cliford+T circuit. Moreover, in real world quantum computers, qubit are usually connected to each other according to some particular topology, thus providing further constraints. Two qubit gates -hence, CNOT gate- can be directly applied only to pair of gates that are connected. Such constraint has to be taken into account during the synthesis of CNOT minimal circuits. We propose an ASP model to solve the problem of synthesizing CNOT minimal circuits under topological constraints. We provide experimental evidence of the scalability of our proposal.
Quantum computations are becoming more and more available to end users thanks to online
platforms that allow to define and simulate quantum algorithms. However, in order scale on
larger circuits it is necessary to increase the number of qubits Quantum Computers are able to
manage. In fact, the so called Quantum speed-up [
The synthesis problem is however more challenging than that, since circuit depth and width have to be taken into account. The circuit depth is the length of the circuit, while the width is another term for the number of qubits used. The former has to be kept low since the coherence time of quantum states is not really high, hence circuits that are too long are doomed to fail in their computation. The latter is strictly related to the issue we addressed at the beginning: number of qubits in physical Quantum Computers is currently limited. So, it is fundamental to design algorithms for synthesizing unitaries while minimizing the depth and width of the resulting circuit.
Most of the synthesis algorithms that have been defined are based on the Cliford+T set of
universal gates. Such set is composed by 3 single qubit gates and a two-qubit gate. Diferent
techniques have been adopted for the synthesis problem. For example, exact techniques with
QMDD have been proposed in [
Given the complexity of the synthesis problem it is also reasonable to consider sub-problems. One possibility is that of focusing into minimizing of the number of occurrences of one fixed gate of the universal set. In [7], the authors devised an algorithm to minimize the number of T gates into a circuit. A similar problem was tackled in [8] where the authors proposed a SAT approach for the minimization of the number of CNOT gates in a T-optimal circuit — a circuit where the optimal number of T gates was already achieved.
Such kind of problem is really important since the CNOT gate is the only two-qubit gate in the Cliford+T base set. Two qubit gates cannot be physically implemented without introducing errors. Hence, their minimization could also lead to a reduction of the efort required for Quantum Error Correction [9] and Verification [10].
For this reason, we consider the same problem as in [8], but we try to solve it with a diferent approach. We take as input a T-optimal circuit made only of CNOT and T gates. We want to produce a circuit ′ that preserves the behaviour of and with the minimum number of CNOT gates. The approach in [8] starts by reducing the problem to a classical one using the notion of phase polynomial representation. Secondly, a satisfiability model is developed to obtain a solution to the following problem: can the circuit be written with CNOT gates? Hence, the model is queried for each possible value of starting from 1. When the first solution is found, it is given as output. Starting from this approach, we propose a solution to the same problem with two major diferences. The first is to encode the problem in an Answer Set Programming model instead that using a SAT encoding. The second is to introduce topological constraints on the CNOT that can be applied. Roughly speaking, in real world quantum computers, qubits are not all connected to each other, but they obey some particular topology. Due to this limitation, two-qubit gates cannot be applied to any pair of qubits. They can be applied only to qubits that are adjacent in such topology. Therefore, in this work we will give as input to the ASP model also a graph describing which pairs of qubits can actually be put in the same CNOT.
We want to stress the fact that this is work extends a previous proposal presented at CILC23 [11]. In such work we introduced two diferent models to solve the CNOT minimization problem without taking into account the topological constraints. Here, we introduce the topological constraints on one of such models and test it in comparison to the case without topological constraints.
The paper is structured as follows: Section 2 contains the definition of the problem and its translation to a classical one. Some results about circuit synthesis coming from the literature are presented in Section 3. Section 4 is used to describe the encoding we propose to solve the given problem. Notice that this section mirrors one section from [11] with an extra addition to handle the topological constraints. After that, Section 5 is devoted to experimental evaluation. Some conclusions and ideas for future works are drawn in Section 6. For space reason we omit the introduction of ASP, the reader may refer to [12].
Modern Quantum Computers (like Osprey from IBM) have two important limits: • Only a finite set of operations can be applied to the qubit • The quantum coherence can be maintained for a short amount of time The finite set of operations a Quantum Computer can apply is usually called
The process of rewriting in terms of gates of a Universal Set of Gates is called synthesis.
The most used Universal Set of Gates for synthesis is the Cliford + T, which contains the following single qubit gates: = √ 1 (︂ 1
1 )︂ 2 and the two-qubit gate CNOT: With the following efect: = ⎜⎜⎝00 10 00 01⎟⎠⎟
0 0 1 0 (, ) = (, ⊕ ) where , are the control and the target of the CNOT gate, respectively. Its efect is twofold: • it leaves the control qubit unchanged • the target is flipped if the control is 1 — a XOR between control and target Single qubit gates can be implemented in physical quantum computers with no errors. On the other hand, two-qubit gates introduce error that must be corrected using Quantum Error Correction (QEC) techniques. Hence, it is reasonable to think about synthesis techniques that aim at minimizing the number of CNOT gates in the resulting circuit.
In this paper, we will start from a circuit made of CNOT and T gates (same problem tackled in [8]), and we will minimize the number of CNOT gates. To do so, we first turn a Quantum problem, into a classical one using the following definition from [13]: Definition 1 (phase polynomial representation). The action of a {CNOT, T} circuit on the initial state |1, 2, · · · ⟩ has the form:
|1, 2, · · · ⟩ ↦→ 4 (1,2,· ,) |(1, 2, · · · )⟩ with (1, 2, · · · , ) defined as: =1 (1, 2, · · · , ) = ∑︁( mod 8)(1, 2, · · · ) → B is a linear reversible function and is a linear combination of linear boolean where : B functions : B
→ B.
(reduced modulo 8) measure the number of / 4 rotations applied to each .
Each circuit has its phase polynomial representation, uniquely defined by
, , for = 1, 2, . . . .
More than one {CNOT, T} circuit can share the same phase polynomial representation.
Since is a linear reversible function with inputs and outputs, it can be written as a × boolean matrix . On the other hand, each can be expressed as a boolean row vector . Example 1. Consider the following circuit: 1 2 3 Its phase polynomial representation is the following: 1 1 ⊕ 2 † • INPUT: , = (, ), 1, 2, · · · • OUTPUT: a sequence of CNOT gates to be applied such that the final behaviour of the circuit is the one described by .
The constraints we must fulfill are the following: • We can only apply CNOT gates that are legal according to . • For each with ∈ {1, 2, · · · , }, there must exist a moment during the computation in which a row of is exactly .
The two constraints allow us to avoid caring about the gates. We just have to create the correct slots for them to be applied, but nothing more.
Example 2. Let and 1 be defined as follows:
⎛1 0 0⎞ = ⎝1 1 1⎠ 0 0 1 1 = (1 1 0)
We must find a circuit such that 1 and 3 are unchanged while 2 becomes the XOR of all the three variables. Moreover, it must be true that at some point one of the variables must be the XOR between 1 and 2 to match the constraint on 1.
The following circuit, made only of CNOT gates, solves the problem.
1 2 3 1 1 We pointed out with the red line the moment in which the constraint on 1 is satisfied.
For what concerns the topological constraint, we adopted a graph based encoding. Let = (, ) be a directed graph. The set of nodes is = {1, 2, · · · , }, where is the number of qubit. The set of edges is such that a CNOT(, ) can be applied if and only if (, ) ∈ .
In Figure 1, we show an example of a topology turned into a graph. Only two CNOT gates are allowed: with control 1 and target 2 or with control 2 and target 3.
With this additional constraint, it is straightforward to see that the problem may become unsolvable in some cases. For example, if we need a CNOT between qubit and , there must exist a path in from to . If such path does not exists, the problem is unsolvable.
Circuit synthesis has become a more and more prominent problem since the first physically working quantum computers were manufactured. A generic synthesis algorithm takes two inputs: a generic unitary matrix ∈ C2× 2 and a universal set of gates ℬ. The output must be a circuit made only of gates from ℬ that implements exactly . Clearly, we are not interested in any type of circuit. We are interested in keeping the circuit (i) as short as possible, because of the very volatile qubit state, (ii) as thin as possible to use the minimum number of qubits.
Diferent approaches and algorithms have been proposed. A large branch of them is composed
by the ones using Quantum Multivalued Decision Diagrams (QMDD) [
QMDDs have been introduced as a means for the eficient representation and manipulation of quantum gates and circuits. The fundamental idea is a recursive partitioning of the respective transformation matrix and the use of edge and vertex weights to represent various complex-valued matrix entries. More precisely, a transformation matrix of dimension 2 × 2 is successively partitioned into four sub-matrices of dimension 2− 1 × 2− 1. This partitioning is represented by a directed acyclic graph - the QMDD.
In [
Not only exact algorithms have been defined. In [
Synthesis problem of Cliford+T circuits is not always addressed as one big problem. A lot of authors also tackled some sub-problems like the minimization with respect to one single gate in the universal set. One example is the minimization of the CNOT gates.
For such problem, an algebraic approach is given in [15] where the authors start by first describing the group structure underlying quantum circuits generated by CNOT gates. Such results are then exploited to create heuristics useful to reduce the number of CNOT in circuits.
A technique based on Steiner Trees has been adopted in [16]. In this case, the authors also took into account the problem of the actual neighbour relation between qubits. When working with physical quantum devices, not every qubit is connected to all the others. Hence, when applying a CNOT between two qubit, we must be sure that these two qubits are linked. Otherwise, we must apply also swap gates, which correspond to 3 CNOT gates.
Last but not least, the SAT based approach has been proposed in [8]. Authors aimed at minimizing the number of CNOT gates in a circuit by setting up the solution of a satisfiability 1 2
3 3 2 problem. Such solution is then iteratively queried until a first feasible model is found and returned as result to the main problem. The SAT solver will eventually be queried for at most 2 times, where is the number of qubit, because of this the following result from [17]: Theorem 1. Any n-qubit circuit of CNOT gates is equivalent to one composed of at most 2 gates.
A SAT encoding is used also in [18]. The authors noticed that synthesis can be related to the problem of finding best boolean chains to represent functions. Hence, they proposed a DAG based approach to generate all possible DAG structures with a fix number of nodes and then query the satisfiability model to check if such structure would solve the problem.
The model we propose is based on a Directed Acyclic Graph. The circuit from Example 1 (without the gates) can be interpreted as the labelled graph = (, ) depicted in Figure 4.
The leaves of the DAG represent the problem variables. Hence, we will have leaves labelled 1, 2, · · · , . A CNOT with control and target is represented by a node with two incoming edges. One edge comes from the closer node labelled . The other from the closer node labelled . The generic structure of a node is depicted in Figure 3.
The DAG structure induces a layering of the nodes. Leafs are at layer 0. A node at layer , can only have incoming edges from nodes in smaller layers. One layer can contain more than a single node. Nevertheless, any layer can contain at most one node labelled , for any ∈ {1, 2, · · · , }.
We solve the problem introduced in Section 2 by computing = (, ) starting from ∈ {0, 1}× , a set of , and some topological constraint = (, ). The set of nodes is always {1, 2, · · · }. Our aim is to build the set of minimum size .
First of all, it must hold that for each layer ≤ , each variable can be the target of at most one CNOT gate. After all the steps, the following has to be true: val() = ∀ ∈ {1, 2, · · · , } where val is defined as follows: val0() = val() = val− 1() val() = val− 1() ⊕ val− 1() ∀ ∈ {1, 2, · · · , } if ∄ | (, , ) ∈ ∧ > 0 if ∃ | (, , ) ∈ ∧ > 0
With the notation ∈ val(), we mean that the XOR operation described by val() contains .
The above constraint was necessary to ensure that the final circuit respects the limitations imposed by .
As far as is concerned, the following must hold:
∀ ∃ ≤ ∃ | val( ) =
In the end, we must ensure that CNOT are applied only to pair of qubits that are connected according to the input topology = (, ). Hence, it must hold that if at layer ^ there is a CNOT(, ), then (, ) ∈ . 4.1. Encoding in clingo We now briefly describe how we encoded the aforementioned solution in the clingo solver.
The input has been encoded in a very simple way. We provide the model with (the size of ) and , the number of diferent . Then, with a predicate of the form g(, , ) we describe the matrix , with the following rules: , = 1 ↔ g(, , 1) , = 0 ↔ g(, , 0) where , ∈ {1, 2, · · · , }
The same relation holds between predicate f(, , ) and . The only diference is that the domain of variable is {1, 2, · · · , }.
The variables we adopted to solve the problem have two types: • node that describes leafs of the DAG. Given an × boolean matrix, we will have exactly nodes with labels 1, 2, · · · , . The mapping from nodes to the variables is straightforward: node describes the variable —the variable that will have to match . • layer, which describes the layers of the DAG.
Inner nodes of the DAG are described by a predicate of the form xor_node(, , ) which has to be interpreted as follows: at layer , there is a node labelled which is the result of the XOR between and — CNOT( , ). Given a variable and a layer , we imposed that a single xor_node with target can exist at layer .
For what concerns the val of a node, we introduced the predicate
value(, , ) where , are nodes and is a step.
value(, , ) holds if and only if ∈ val ( ). We then encoded the update of value using the recursive definition introduced above.
We used the predicate value to check the final solution of the model at the -th step. For all , ∈ {1, 2, · · · , } the following must hold: Forcing the model to search for graphs that satisfy the total behaviour imposed by .
Something similar has been done for the constraint on , with the only diference that can match the val of a node at any time. Hence, for all there must exists a ≤ and a such that for all ∈ {1, 2, · · · , }: g(, , 1) ↔ value(, , ) g(, , 0) ↔ ¬value(, , )
f(, , 1) ↔ value(, , ) f(, , 0) ↔ ¬value(, , )
s(, ) ↔ (, ) ∈
Handling the topological constraints induced by is pretty straightforward. We encoded the edges of with a binary predicate s.
Using such predicate, we can enforce that xor_node(, ) can hold if and only if s(, ).
We tested the proposed model in two way. The former allowing any CNOT between the gates and the latter using the topological constraint forced by . For each ∈ {4, 5, 6, 7, 8} we generated 10 diferent random tests. For each test we created an × matrix, representing a linear reversible function, that will serve as — in the quantum case, is the number of qubits, that evolve through 2 × 2 unitary matrices. Moreover, for each test, we picked a number between 1 and , that will be the number of diferent we give as input to each test. The topology of the qubit that we adopted is depicted in Figure 4. It is a smaller version of the topology adopted in the 16-qubit guadalupe Quantum Computer from IBM.
We tested the proposed models with the following procedure. We then run the two diferent models with an iterative procedure that works as follow. Let , {} be the input for the current test case. We initialized a counter to 1. We then run the graph model with input , {} and , to see if the problem was solvable in steps. If true, then we stored the running time and move to next sample. Otherwise, we increased and queried the model again. Notice that, by Theorem 1, will at most be 2.
In Table 1 we report the obtained results without the topology, while in Table 2 the results with the topology taken into account.
In both tables, the first column is the quantity , the number of qubits. The second one is the average running time (in seconds) in the 10 tests. For each test, the time we measured is the overall time for the iterative procedure to find the solution, and not only the time for the satisfiable instance — even if we noticed that the unsatisfiability is found in less than 0.01 seconds in most of the cases. The tests have been run in a 2021 MacBookPro, with a 2 GHz Intel Core i5 quad-core CPU and 16GB of LPDDR4X Ram.
Results depicted in Table 1 show that the model with no topological constraint outperforms the constrained one (Table 2). Even if the test cases are rather small, it seems that forcing the model to use only a particular subset of all the possible CNOT makes the search for the optimal model harder. It is correct to notice that we only took into account one single ASP model and only a single qubit topology. In the future we would like to extend this round of tests by implementing faster models and testing them against diferent topologies.
In this paper we extended the work presented in [11]. Our main goal was to introduce the notion of topological constraint into the ASP model. Doing so, we could mimic and study real Quantum Computer scenarios were qubits are connected according to some particular and strict topology. The model we presented is the same as in [11]. We only added some extra constraints to take the topology of the qubit into account. The results obtained show that the model with no topological constraint is faster than the other one. Despite this outcome, it is worth to study this complete version of the problem since it better describes real-life synthesis scenarios.
Despite that, it seems that Answer Set Programming can be fruitfully applied to the synthesis problem of quantum circuits in general, and not only in the CNOT case. Moreover, the solutions to this problem and solutions to problems such as the minimization of the number of T gates, paves down the road to the idea that the synthesis problem is not a monolith. Fast and not optimal techniques may be adopted to obtain a first and rough synthesis of some unitary . Starting from such synthesis, algorithms can be applied to systematically minimize parts of the circuits to obtain a reduction that is close to the optimal one. A fast and reliable synthesis (re-synthesis) algorithm would also allow to test a great variety of algorithms on real world quantum computers. For example, reachability on graphs [19] or the eficiency of quantum automata [20]. quantum circuit synthesis, in: Nature Inspired Cooperative Strategies for Optimization, 2007. [6] Y.-H. Chou, S.-Y. Kuo, Y.-C. Jiang, C.-H. Wu, J.-Y. Shen, C.-Y. Hua, P.-S. Huang, Y.-T. Lai, Y. F.
Tong, M.-H. Chang, A novel quantum-inspired evolutionary computation-based quantum circuit synthesis for various universal gate libraries, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’22, Association for Computing Machinery, New York, NY, USA, 2022, p. 2182–2189. doi:10.1145/3520304. 3533956. [7] M. Amy, D. Maslov, M. Mosca, Polynomial-time t-depth optimization of cliford+t circuits via matroid partitioning, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33 (2014) 1476–1489. doi:10.1109/tcad.2014.2341953. [8] G. Meuli, M. Soeken, G. D. Micheli, Sat-based {CNOT, T} quantum circuit synthesis, in:
International Workshop on Reversible Computation, 2018. [9] J. Rofe, Quantum error correction: an introductory guide, Contemporary Physics 60 (2019) 226–245. doi:10.1080/00107514.2019.1667078. [10] L. Anticoli, C. Piazza, L. Taglialegne, P. Zuliani, Towards quantum programs verification: From quipper circuits to QPMC, in: S. J. Devitt, I. Lanese (Eds.), Reversible Computation - 8th International Conference, RC 2016, Proceedings, volume 9720 of Lecture Notes in Computer Science, Springer, 2016, pp. 213–219. doi:10.1007/978-3-319-40578-0\_16. [11] C. Piazza, R. Romanello, R. Wille, An asp approach for the synthesis of cnot minimal quantum circuits, volume 3428, 2023. URL: https://www.scopus.com/inward/record.uri? eid=2-s2.0-85164570648&partnerID=40&md5=b43c2519b280693049364e26a7554169, cited by: 0. [12] W. Faber, An Introduction to Answer Set Programming and Some of Its Extensions, Springer International Publishing, Cham, 2020, pp. 149–185. doi:10.1007/978-3-030-60067-9_ 6. [13] M. Amy, D. Maslov, M. Mosca, M. Roetteler, A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2013). [14] M. Amy, D. Maslov, M. Mosca, M. Roetteler, A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32 (2013) 818–830. doi:10.1109/tcad.2013. 2244643. [15] M. Bataille, Quantum circuits of CNOT gates: optimization and entanglement, Quantum
Information Processing 21 (2022) 269. doi:10.1007/s11128-022-03577-8. [16] V. Gheorghiu, J. Huang, S. M. Li, M. Mosca, P. Mukhopadhyay, Reducing the cnot count for cliford+t circuits on nisq architectures, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2022) 1–1. doi:10.1109/tcad.2022.3213210. [17] M. Bataille, Quantum circuits of cnot gates, 2020. arXiv:2009.13247. [18] W. Haaswijk, A. Mishchenko, M. Soeken, G. De Micheli, Sat based exact synthesis using dag topology families, in: Proceedings of the 55th Annual Design Automation Conference, DAC ’18, Association for Computing Machinery, New York, NY, USA, 2018. doi:10.1145/ 3195970.3196111. [19] D. D. Giustina, C. Piazza, B. Riccardi, R. Romanello, Directed graph encoding in quantum computing supporting edge-failures, in: C. A. Mezzina, K. Podlaski (Eds.), Reversible Computation - 14th International Conference, RC 2022, Urbino, Italy, July 5-6, 2022, Proceedings, volume 13354 of Lecture Notes in Computer Science, Springer, 2022, pp. 75–92. doi:10.1007/978-3-031-09005-9\_6. [20] C. Piazza, R. Romanello, Mirrors and memory in quantum automata, in: E. Ábrahám, M. Paolieri (Eds.), Quantitative Evaluation of Systems, Springer International Publishing, Cham, 2022, pp. 359–380.