Graph-Theoretical Arguments in Support of a Quantum Declarative Manifesto Alex Della Schiava1 , Carla Piazza1 and Riccardo Romanello1 1 Dipartimento di Scienze Matematiche, Informatiche e Fisiche, Università degli Studi di Udine Abstract The encoding of graphs and the development of efficient algorithms over graphs in the Quantum framework is still a challenging problem. More in general, the understanding of whether a problem can benefit of the Quantum speed-up or not is far from being complete. In this paper we analyse, compare, and generalize some proposals for the encoding of graphs in Quantum computing. A question peeping out on the horizon of our analysis concern the shift from a procedural way of thinking to a declarative one in the context of Quantum computing. Keywords Quantum computing, Graphs, Quantum walks, Quantum speed-up Introduction In May 1981, Feynman gave a conference lecture on “Simulating physics with computers". In that occasion, he proposed the idea of using quantum computers to simulate quantum systems that are too hard to simulate using classical computers. His talk, published in [1], is remembered as the big bang of quantum computing as a research field. Since that moment, both academia and companies have put a lot of effort in the task of developing useful Quantum Computers. Despite the stakeholders that joined the task, the path is far from being complete. One of the biggest problems is a manufacturing one: creating and preserving qubits. Qubits are the equivalent of bits in the quantum setting, but they are not as easy to preserve as their classical counterpart. They must be stored at a very low temperature in order to maintain coherence — any computation based on uncoherent qubits leads to error. Despite the high costs demanded by the task, a handful of companies have been able to construct working Quantum Computers. Confined by the rules of quantum mechanics, the quantum model of computation solely manipulates qubits through unitary operations, which are a subset of linear operators. Projec- tions, another subset of linear operators, allow to read the content of qubits, albeit by inevitably altering their state. Hence, every Quantum algorithm must be developed as a sequence of unitary operators and projections. Quantum algorithms such as Shor’s factorization [2] and CILC’23: 38th Italian Conference on Computational Logic, June 21–23, 2023, Udine, Italy † This work is partially supported by PRIN project NiRvAna and GNCS-INdAM project “Algoritmi Quantistici su Grafi” CUP_E53C22001930001. $ dellaschiava.alex@spes.uniud.it (A. Della Schiava); carla.piazza@uniud.it (C. Piazza); riccardo.romanello@uniud.it (R. Romanello) © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) Grover’s search [3] witness the different kind of speed-up achievable by adopting a quantum system as model of calculus. Nevertheless, there exists no standard recipe to systematically exploit the properties of quantum mechanics to obtain similarly remarkable results. For example, problems defined over graphs play a central role in Computer Science. Since their introduction by Euler in [4]–which is considered the first paper in Graph Theory–graphs have become more and more prominent in mathematics first and in computer science later. Not only do they allow to model and solve a vast amount of problems, but they also capture the notion of computation over procedural models such as Turing Machines, Random Access Machines, and imperative programming languages [5]. As a consequence, to understand and generalize quantum speed-up results, one could investi- gate how graphs and graph algorithms behave on quantum architectures. Nevertheless, graphs did not receive much attention in the quantum case: there are no exhaustive answers as to how these data structures may be encoded in the quantum setting. Current techniques require graphs to satisfy severely restrictive properties in order to be encoded [6, 7]. Starting from assumptions of this form, quantum algorithms over graphs are not general. Moreover, graphs have hardly been adopted and used in theoretical Quantum Computing to show results about expressiveness and complexity. It is enough to dig a little into the topic of Quantum Automata to see how many questions are still open [8]. In light of these theoretical questions, the use of Quantum Hardware is hardly justifiable: only a handful of algorithms fully exploit its benefits. While efforts have been directed toward defining further efficient quantum algorithms through Quantum Programming Languages [9, 10], in this paper we prompt investigations on the efficient compilation of declarative languages over quantum architectures. Joint efforts on the investigations would reciprocally benefit the two involved research fields: How can declarative programming and Quantum Computing assist each other? Our intuition starts by observing the difficulties arising in the quantum encoding and man- agement of graphs. These complications are strongly related to the intrinsic reversibility of quantum computation. Intuitively, only strongly connected graphs are reversible. As a conse- quence, an efficient compilation of procedural languages that rely on operational semantics, i.e., on graphs, looks difficult. On the other hand, because of their “natural” denotational semantics, declarative languages seem like better candidates. While the main part of this paper is devoted to give the reader evidence on the obstacles in using graphs within quantum computation, in Section 4 we come back to our claim on declarative languages. The paper is structured as follows. In Section 1 we give an overview of Quantum Computing from two different perspectives. The former builds up from a lower level, introducing the elements from linear algebra required to handle theoretical Quantum Computing. The latter is a high level view where we lay down the mathematical details to focus on the general ideas of quantum computation. The purpose of Section 2 is to introduce and explain the key role graphs play in classical computation. Section 3 thus shifts the discussion to the quantum setting, providing insights on the problem of encoding graphs into quantum computation. In Section 4 we speculate on the possible advantages of a shift of point of view in the direction of compilers from classical declarative languages on quantum machines. 1. From Low to High Level View of Quantum Computation 1.1. Low Level View The most used model of Quantum Computation relies on the formalism of state vectors, unitary operators and projectors. State vectors evolve during the computation through unitary operators, then projectors are used to remove part of the uncertainty on the internal state of the system. The state of the system is represented by a unitary vector over C𝑛 with 𝑛 = 2𝑚 for some 𝑚 ∈ N. The concept of a bit of classical computation is replaced by that of a qubit. While bits have value either 0 or 1, qubits are unitary vectors in C2 . The two components of the qubit are the complex numbers 𝛼 = 𝑥 + 𝑖𝑦 and 𝛽 = 𝑧 + 𝑖𝑤; their squared norms |𝛼|2 = 𝑥2 + 𝑦 2 and |𝛽|2 = 𝑧 2 +𝑤2 represent, respectively, the probability of measuring the qubit at either value 0 or 1. In the more general case of 𝑚 qubits the unitary vectors range in C𝑛 with 𝑛 = 2𝑚 . Adopting the standard Dirac notation we denote a column vector 𝑣 ∈ C𝑛 by |𝑣⟩, and its conjugate transpose 𝑣 † by ⟨𝑣|. A quantum state is a unitary vector ∑︁ |𝜓⟩ = 𝑐ℎ |𝑣ℎ ⟩ ℎ for some basis {|𝑣ℎ ⟩}. When not specified, we refer to the canonical basis. Further details can be found in [11]. Unitary operators and projectors are linear operators. Unitary operators are a particular class of reversible linear operators. They preserve both the angles between vectors and their lengths. In other terms, unitary operators are transformations from one orthonormal basis to another. Hence, they are represented by unitary matrices. Let 𝑈 be a square matrix over C. 𝑈 is said to be unitary iff 𝑈 𝑈 † = 𝑈 † 𝑈 = 𝐼. We describe the application of a unitary matrix 𝑈 to a state |𝜓⟩ by writing ⃒ ′ ⟩︀ ⃒𝜓 = 𝑈 |𝜓⟩ meaning that the state |𝜓⟩ becomes |𝜓 ′ ⟩ after applying the operator 𝑈 . In order to extract information from a quantum state |𝜑⟩ a measurement must be performed. The most common measurements are projectors. Let |𝑢⟩ be a quantum state. The projector operator 𝑃𝑢 along the direction of |𝑢⟩ is the linear operator defined as: |𝑢⟩⟨𝑢| 𝑃𝑢 = ⟨𝑢|𝑢⟩ where |𝑢⟩⟨𝑢|, being the product between a column vector and a row one both of size 𝑛, returns a matrix of size 𝑛 × 𝑛. Since throughout the paper we only use unitary vectors, the term ⟨𝑢|𝑢⟩ is always 1 and can be ignored. 1.2. High Level View In order to both summarize and take a step back from technical details, we can say that quantum computation is a computation over vectors of complex numbers which only exploits a subset of linear functions (i.e., unitaries and projectors) as basic operations. Each function that can be obtained as a composition of these basic operations is a quantum circuit. The model becomes Turing complete by either considering uniform families of circuits or by adding loops over classical Boolean variables (e.g., Boolean values obtained through projectors). One of the main peculiarities of quantum computation is that of being reversible. As a matter of fact once a unitary operator 𝑈 has modified the system, we can go back to the past state by applying the unitary operator 𝑈 † . Classical computation is in general non-reversible. Let us consider the conjunction Boolean operator ∧. When we apply it to the bits 𝑥 and 𝑦, we obtain the output bit 𝑧. From 𝑧 it is not always possible to infer the values of 𝑥 and 𝑦. However, any classical Boolean function 𝑓 𝑓 : {0, 1}𝑚 → {0, 1} can be embedded into the reversible function 𝑓 𝑓 : {0, 1}𝑚+1 → {0, 1}𝑚+1 defined as 𝑓 (𝑥, 𝑦) = (𝑥, 𝑦 ⊕ 𝑓 (𝑥)) where 𝑥 ∈ {0, 1}𝑚 and 𝑦 ∈ {0, 1}. Not only 𝑓 is reversible, but it is unitary and it coincides with its inverse. If we simply think at quantum computation as a sequence of unitary and projector operators applied to an initial vector, it shares some aspects with the computation done within a neural network. Both unitaries and projectors are linear transformations. So, Quantum compared with Neural Networks lacks of the key feature of non-linear activation functions. However, quantum computation is performed over complex numbers, while a neural network relies on the reals. As witnessed by quantum interference, a complex number is much more than a pair of reals. The main phenomena that distinguish quantum computation from the classical one are: superposition, interference and∑︀ entanglement. The quantum state |𝜓⟩ = ℎ 𝑐ℎ |𝑣ℎ ⟩ is in a superposition of classical states and a projector is necessary to collapse it in the classical world. Interference allows probabilities to behave in an unexpected way. In the quantum framework two events 𝐴 and 𝐵 can have both positive probabilities, while 𝐴 ∨ 𝐵 has probability 0. Entanglement is so surprisingly and unexplainable that even Einstein could not believe it. It is a sort of correlation between particles that remains true until they are observed. 2. Graphs at the Basis of Procedural Computation Models Graphs are a standard data structure in Computer Science for the representation of binary relations. We report below some standard definitions on graphs, while we refer the reader to [12] for further details. A directed graph 𝐺 is a pair (𝑉, 𝐸) where 𝑉 is a non empty set of vertices and 𝐸 ⊆ 𝑉 × 𝑉 is a set of edges. We say that an edge (𝑢, 𝑣) is directed from 𝑢 to 𝑣 and that 𝑢 is adjacent to 𝑣. We also say that 𝑢 is the source and 𝑣 is the target of (𝑢, 𝑣). Two edges of the form (𝑢, 𝑣) and (𝑣, 𝑤) are said to be consecutive. Given a vertex 𝑣, its out-neighbourhood 𝛿 + (𝑣) (in-neighbourhood 𝛿 − (𝑣)) is the set of vertices connected via an edge from (to) 𝑣; the out-degree (in-degree) of 𝑣 is 𝑑+ (𝑣) = |𝛿 + (𝑣)| (𝑑− (𝑣) = |𝛿 − (𝑣)|). Graphs are the key data structure for efficiently solving problems defined over maps, networks, processes and, more in general problems, that can be stated through binary relations. Not only graphs allow to model and efficiently solve such a wide range of problems, but they are at the core of every computation endowed with an operational semantics. As a consequence, time and space complexities of the reachability problem over deterministic and non-deterministic Turing machines are at the basis of the most important results in Complexity Theory, such as Savitch’s theorem and Immerman-Szelepscényi theorem [5]. In the context of randomized computations, again graphs, and in particular random walks over graphs, play a central role both in the design of efficient algorithms and in the development of general strategies for speeding-up their convergence [13]. So, on the one hand, one could observe that any computational model that aims at solving interesting problems should provide a set of tools for managing graphs (i.e., for solving problems over graphs). On the other hand, a computational model able to efficiently solve the reachability problem has already the ability to efficiently simulate classical machines, and can aim to beat them over specific problems. Such point of view naturally suggests some questions in the direction of a better understanding of the potential of quantum computation: • Which problems over graphs can be efficiently solved over a quantum model? • How can graphs be efficiently stored in a quantum machine? At the moment the answers to the above questions are not complete. Several approaches have been presented in the literature and we will provide details on some of them in the next sections. With different strategies these approaches try to encode graphs into unitary matrices. Intuitively, during a traversal/walk over the graph the state vector keeps track of the current superposition of vertices, which looks amazing, since it means that we are “in parallel” proceeding along different directions. Differently from classical random walks, some paths may interfere destructively with each other, introducing bias in the global behaviour of the quantum walk. Remarkably, this action significantly reduces the time required by the quantum walk to spread across certain graphs [14, 15]. Moreover, only some classes of graphs ensure the reversibility of the traversal, while all the others have to be somehow embedded in larger structures. Are these unsatisfactory answers to the above questions just a matter of how much effort has been put so far on the topic? Cannot be the case that they are a symptom of the need for a shift of point of view? We will come back to this in the last section. 3. Graph Encoding in Quantum In classical computations graphs are largely used as an abstract data structure where to encode the input knowledge and efficient graph algorithms are developed with the aim of computing the desired output. On the contrary, in the context of Quantum Computation graphs are mainly studied as the domain for quantum walks. As a matter of fact, quantum walks have been a fundamental tool in physics, where they have been employed to analyze/simulate the evolution of quantum systems. Quantum walks are the quantum mechanical counterpart of random walks. A “quantum walker" moves analogously to a classical one, albeit, with three key differences: (i) he may lie in a superposition of states; (ii) his steps are guided by probability amplitudes; (iii) only unitary transformations can be used to guide the changes of the quantum walker. In the context of quantum simulation, the quantum walker is meant to represent the quantum system under consideration and, as such, he obeys the laws of Quantum Mechanics. Indeed, conditions (i), (ii), and (iii) given above are but a coarse summary of these laws. Conditions (i) and (ii)— together with entanglement—are at the basis of quantum speed-up. Condition (iii) poses a strong limit by restricting the class of graphs over which walks may be performed. Nonetheless, both continuous and discrete-time quantum walks have been shown to be as powerful as the quantum circuit model of computation [16, 17]. However, issues arise when studying quantum walks and quantum representations of graphs in a more general setting. For the above reasons in this section we investigate the classes of graphs amenable to representations in the quantum setting and to quantum walks. Then, we analyse how general graphs can be embedded into ones belonging these classes as well as the costs such embedding procedures demand. 3.1. Directed Graphs and Unitary Matrices The relationship between graphs and unitary matrices is formalized via the adjacency matrix representation. As a preliminary notion, the support of a matrix 𝑀 ∈ C𝑛×𝑛 is defined as the matrix 𝑀 𝑆 ∈ {0, 1}𝑛×𝑛 such that, for any 1 ≤ 𝑖, 𝑗 ≤ 𝑛, {︃ 𝑆 1 if 𝑀𝑖𝑗 ̸= 0; 𝑀𝑖𝑗 = 0 otherwise. A graph and a unitary matrix may, thus, be related in terms of the following definition. Definition 1. A graph 𝐺 is said to be the graph of a unitary matrix 𝑈 if and only if the respective adjacency matrix 𝑀 (𝐺) supports 𝑈 . Example 1. Graph 𝐺 depicted in Figure 1 is the graph of the unitary matrix 𝑈 , ⎛ √ ⎞ 1/ 2 1/2 √ 1/2√ 𝑈 = ⎝ 0√ 1/ 2 −1/ 2⎠ . −1/ 2 1/2 1/2 Graphs of unitary matrices are amenable to quantum walks. In the case of graph 𝐺 from Figure 1, a quantum walk may be defined in terms of operator 𝑈 . Its construction is analogous to that of a classical Markov chain. The three vertices of 𝐺 induce the state space C3 , with each vertex 𝑣 being represented by a column vector |𝑣⟩ of the canonical basis. Transitions are guided by the adjoint of 𝑈 : 𝑈 † . The adjoint 𝑈 † is here required to abide to the conventional representation of unitary evolution as a matrix-vector multiplication. To provide an example, let the quantum walk start from state |1⟩ = (1, 0, 0)𝑇 . Performing the first step then leads to state 1 1 1 𝑈 † |1⟩ = √ |1⟩ + |2⟩ + |3⟩ . 2 2 2 𝐺= 1 ⎛ ⎞ 1 1 1 𝑀 (𝐺) = ⎝0 1 1⎠ . ⎜ ⎟ 1 1 1 2 3 Figure 1: Graph of a unitary matrix. After a single step, the quantum walker finds herself into a superposition of all three vertices of the graph. Another insightful example sees the quantum walk start from state |𝜓⟩ = 12 |1⟩+ √12 |2⟩+ 12 |3⟩. A single step transition leads to state 𝑈 † |𝜓⟩ = |2⟩ . The step has produced a rather singular effect: whereas the probability amplitudes for the paths leading to vertex 2 reinforce each other, the paths heading towards vertices 1 and 3 cancel out. These two phenomena are known, respectively, as constructive and destructive interference and characterize the peculiar behaviour of quantum walks: more paths heading towards the same vertex do not necessarily imply a higher probability of reaching it. As previously mentioned, the class of graphs of unitary matrices is severely restrictive. Moreover, it is hard to characterize the class through ordinary properties from Graph Theory. From the literature, three distinct approaches to the problem emerge, each relating graphs of unitary matrices to other graph properties: (i) via strong quadrangularity [18]; (ii) via graph reversibility [6]; (iii) via study of bridges and cuts [19]. As for (iii), the work explores how different connected components from graphs of unitary matrices are connected to each other. The study is here not elaborated any further. Strong Quadrangularity In [18], graphs of unitary matrices have been studied with respect to the property of strong quadrangularity. Definition 2 (Strong Quadrangularity). Given a graph 𝐺 = (𝑉, 𝐸), consider sets of the two following forms: • 𝑆out ⊆ 𝑉 , where, for any 𝑢 ∈ 𝑆out there exists 𝑣 ∈ 𝑆out such that 𝛿 + (𝑢) ∩ 𝛿 + (𝑣) ̸= ∅. • 𝑆in ⊆ 𝑉 , where, for any 𝑢 ∈ 𝑆in there exists 𝑣 ∈ 𝑆in such that 𝛿 − (𝑢) ∩ 𝛿 − (𝑣) ̸= ∅. Then, 𝐺 is said to be strongly quadrangular if and only if for any set of the form 𝑆out or 𝑆in it holds that ⃒ ⃒ ⃒ ⃒ ⃒ ⋃︁ ⃒ ⃒ ⋃︁ ⃒ + + − − 𝛿 (𝑢) ∩ 𝛿 (𝑣)⃒ ≥ |𝑆out |; 𝛿 (𝑢) ∩ 𝛿 (𝑣)⃒ ≥ |𝑆in |. ⃒ ⃒ ⃒ ⃒ ⃒ ⃒ ⃒ ⃒ ⃒ ⃒ 𝑢,𝑣∈𝑆out 𝑢,𝑣∈𝑆in Although apparently abstract, the property of strong quadrangularity provides deep, matrix- theoretical insights over the class of graphs of unitary matrices. Lemma 1. [18] Any graph of a unitary matrix is strongly quadrangular. The opposite direction of this relationship involves the property of specularity. Definition 3 (Specularity). A graph 𝐺 = (𝑉, 𝐸) is said to be specular if and only if, for any pair of vertices 𝑢, 𝑣 ∈ 𝑉 , the following two conditions are satisfied: 𝛿 + (𝑢) ∩ 𝛿 + (𝑣) = ∅ or 𝛿 + (𝑢) = 𝛿 + (𝑣); and 𝛿 − (𝑢) ∩ 𝛿 − (𝑣) = ∅ or 𝛿 − (𝑢) = 𝛿 − (𝑣). In other words, two vertices of a specular graph either share the entire in/out-neighbourhood or none of it. Pairing specularity and strong quadrangularity gives the following result. Theorem 1. [18] A specular, strongly quadrangular graph is the graph of a unitary matrix. A broader version of the discussion involves the notion of line graph. → − → − → − Definition 4 (Line Graph). Given a graph 𝐺 = (𝑉, 𝐸), the respective line graph is 𝐺 = ( 𝑉 , 𝐸 ) where: → − → − • 𝑉 = 𝐸. The vertices in 𝐺 represent the edges from 𝐺. → − → − • 𝐸 = { (𝑢, 𝑣), (𝑣, 𝑤) : (𝑢, 𝑣), (𝑣, 𝑤) ∈ 𝐸}. Two vertices are adjacent in 𝐺 if and only (︀ )︀ if they represent consecutive edges in 𝐺. The convenience in dealing with line graphs is twofold. On the one hand, a line graph encodes all adjacencies of the original graphs. On the other, line graphs are tightly linked to the property of specularity, as stated by the following result. Lemma 2. Any line graph is specular. Theorem 1 now prompts the question as to which graphs induce strongly quadrangular line graphs. As it turns out, the question is answered by Eulerian graphs or graphs that are disjoint unions of Eulerian components. → − Theorem 2. [18] Let 𝐺 be a graph. Then, 𝐺 is the graph of a unitary if and only if 𝐺 is Eulerian or the disjoint union of Eulerian components. As for Theorem 2, it should be clarified that the proof from left to right is only partially related to the reasoning constructed so far in this section. Graph Reversibility Following a different path, Montanaro studied graphs of unitary ma- trices from the perspective of graph reversibility [6]. This novel notion builds upon its local version: an edge (𝑢, 𝑣) is reversible if and only if there exists a path from 𝑣 to 𝑢. Definition 5 (Graph Reversibility). [6] A graph is said to be reversible if and only if all of its edges are reversible. Eulerian 𝐺 → − 𝐺 Strongly quadrangular Specular, strongly Graph of unitary matrix quadrangular Reversible Figure 2: Graphs of unitary matrices in Graph Theory. Reversibility is closely tied with the more standard property of strong connectivity: any strongly connected graph is reversible. However, the opposite is not true: the class of reversible graphs includes all graphs composed of different disconnected strongly connected components. The following result provides the main connection between graphs of unitary matrices and reversibility. Theorem 3. [6] If 𝐺 is the graph of a unitary matrix then 𝐺 is reversible. In light of these results, strong quadrangularity and reversibility appear to relate to graphs of unitary matrices in distinct ways. Whereas the study of strong quadrangularity requires a deeper quasi matrix-theoretical analysis, reversibility links to graphs of unitary matrices on a higher level. Because quantum computation is inherently reversible, it is of no surprise that graphs apt to describe it should satisfy some sort of Graph Theoretical-analogous of reversibility. To clarify the picture described by the results provided so far, Figure 2 provides a conceptual summary of the relationships between graphs of unitary matrices and the graph properties here reviewed. 3.2. Encoding Graphs into Unitary Matrices Section 3.1 provided insights over the properties that characterize graphs of unitary matrices. Because these are the graphs that lend themselves to quantum walks, a reasonable question would ask how to transform general graphs into graphs of unitary matrices. “Graph Encoding in Quantum Computing” refers precisely to this transformation. Hereby, two edge addition based encoding procedures are summarized: from general to Eulerian graphs [20]; from irreversible to reversible graphs [6]. Encoding General Graphs into Eulerian Ones In [20], an algorithmic solution aimed at encoding graphs into unitary matrices was proposed. Because the result solely relies on the assumption that the given multigraph be connected, the procedure may be extended to general graphs via reiteration over each connected component. The procedure builds upon Theorem 2 through the following steps: (i) the given graph −→ 𝐺 = (𝑉, 𝐸) is encoded into a Eulerian graph 𝐺′ ; (ii) the line graph 𝐺′ is computed; (iii) 𝐺 is −→ − → encoded into a unitary matrix 𝑈 supported by the adjacency matrix 𝑀 (𝐺′ ). By Theorem 2, 𝐺′ is the graph of a unitary matrix, thus 𝑈 exists. Providing a closer inspection over the workings of step (i), this exploits the following result. 𝑎 𝑏 𝑎 𝑏 𝑑 𝑐 𝑑 𝑐 (a) Input graph 𝐺. (b) Eulerian multigraph 𝐺′ . Figure 3: Encoding graph 𝐺 into the eulerian multigraph 𝐺′ via edge addition. Theorem 4. A connected graph 𝐺 = (𝑉, 𝐸) is Eulerian iff, for any 𝑣 ∈ 𝑉 , 𝑑+ (𝑣) = 𝑑− (𝑣). On these grounds, the procedure “Eulerifies” 𝐺 by balancing the in- and out-degree of each vertex through addition of edges. Figure 3 provides an example of this process, the added edges are highlighted in Figure 3b in orange color. Because edges may be duplicated, 𝐺 is, more generally, encoded into a Eulerian multigraph, that is, a graph where two vertices may be connected by more than one edge going the same direction. In light of the fact that, in a directed graph, incoming and outgoing edges always come in the same quantity, the procedure can be shown to converge in 𝒪(|𝑉 | + |𝐸|) time. All three steps considered, the overall time-complexity of the procedure is Θ(|𝐸|2 ). As is the case for the example in Figure 3, the encoded graph might include adjacencies that were not part of the original graph. While the encoding itself does not address the issue, projectors do come in to rescue. Let us briefly recall that the state space of a quantum walk is spanned by the vertices of the given graph. Now, because this encoding procedure constructs a quantum walk on a line graph, unwanted edges become unwanted vertices and are thus quickly taken care of with projectors. Elaborating on this, let 𝐸⊥ be the set of newly created edges and consider projector ∑︁ 𝑃𝐺 = 𝐼 − |𝑒⟩ ⟨𝑒| , 𝑒∈𝐸⊥ where 𝐼 is the identity operator. Applying 𝑃𝐺 on any state of the walk erases any part of the superposition concerning the unwanted edges, thus continuing the walk as they were never traversed. Clearly, 𝑃𝐺 needs to be applied after each step of the walk. Encoding Irreversible Graphs into Reversible Ones Apart from providing a reasonable notion of graph reversibility, Montanaro has also developed a procedure to edit irreversible graphs so to satisfy this newly defined graph property [6]. Before proceeding any further, it should be clarified what reversible graphs are good for; the results given thus far are silent as to the conditions these graphs must satisfy. As it turns out, once a reversible graph is equipped with self-loops at each vertex, a procedure exists to encode it into the graph of a unitary matrix. The process works through a specific cycle decomposition of the graph. Further details may be found in [6]. Returning to irreversible graphs, the path towards their transformation to reversible ones begins with the identification of all those edges that are irreversible. Trivially, these edges are to be turned into reversible ones, though defining the resulting quantum walk shall require a more elaborate plan. Given a graph 𝐺, removing all such edges inevitably leads to a reversible graph 𝐺𝑟𝑒𝑣 . Indeed, no reversible edge becomes irreversible through such removal. The effect of the removal is twofold: (i) 𝐺𝑟𝑒𝑣 is structured into different reversible connected (or, equivalently, strongly connected) components 𝐶1 , 𝐶2 , . . . , 𝐶𝐷 ; (ii) in 𝐺, irreversible edges always connect two distinct components 𝐶𝑖 , 𝐶𝑗 . Let (𝑢, 𝑣) be the irreversible edge connecting components 𝐶𝑖 , 𝐶𝑗 . 𝐶𝑖 is augmented with vertex 𝑣. To preserve reversibility of 𝐶𝑖 , edge (𝑣, 𝑢) is added. Finally two distinct quantum walks 𝑊𝑖 , 𝑊𝑗 are constructed over reversible components 𝐶𝑖 and 𝐶𝑗 via the above procedure. Depending on which component the walker is currently visiting, the respecting quantum walk operator is applied. However, with a solution comes a problem, namely that the quantum walker should be prevented from ever traversing edge (𝑣, 𝑢), as it does not belong the original graph 𝐺. To this end, projective measurements are devised, such that, upon superposition between vertices of 𝐶𝑖 , 𝐶𝑗 , the walker collapses to one of the components. That is, for any connected component of 𝐺𝑟𝑒𝑣 , the following projector is defined ∑︁ 𝑃𝑘 = |𝑣⟩ ⟨𝑣| . 𝑣∈𝐶𝑘 After a step, the walker is measured via all projectors 𝑃𝑘 . Measuring 𝑖 or 𝑗 means, respectively, finding the walker in either reversible component 𝐶𝑖 or 𝐶𝑗 . Thus, given measurement outcome 𝑘, the quantum walk is continued via operator 𝑊𝑘 . Naturally, the next step could again traverse an irreversible edge. Thus, just as in the encoding procedure into Eulerian graphs, quantum walk operators and projectors need be alternated. How Truthful Can an Encoding Procedure Be? Both encoding procedures here reviewed appear to heavily rely on the use of projectors to ensure truthfulness with respect to the structure of the original graph. More specifically, projectors are inevitable whenever dealing with non-strongly connected graphs: yet another hint to the restriction posed by computational reversibility and graph reversibility. In this regard, the study on truthful encoding procedures should also concern duplicated edges. Indeed, edge duplication also affects graph topology, albeit in a somewhat softer way. In turn, these effects appear to produce phenomena of local bias in the resulting quantum walk. 4. Conclusions and Future Declarative Directions A large part of quantum computing research focuses on the development of efficient quantum algorithms and quantum programming languages that should allow to code such algorithms (see, e.g., [10]). Pursuing this route has the advantage of directing the efforts in identifying the complexity classes including all the problems that can be efficiently solved in the quantum setting (e.g., the classes QP and BQP). However, it requires a deep change in the way we instruct new generations of computer scientists on algorithms and programming. The risk is that of finding only “small” classes of problems over which the quantum advantage is substantial. This paper follows an alternative path: coding quantum algorithms in a classical setting, relying on a compiler to achieve quantum speed-up. Ideally, the programmer would thus be relieved from any “quantum mechanical duty.” However, the generalized speed-up provided by a compiler would hardly compare with the speed-ups available for each given problem. In light of these observations, a compromise between the two approaches seems reasonable. Though, two questions arise: (i) What kind of compiler? (ii) What kind of classical paradigm? In Section 2 we recall the tight connection between graphs and procedural models (e.g., imperative programming languages). Throughout Section 3, the analogy between quantum computational and graph reversibility frequently emerges in a rather natural way. However, graphs defined by the operational semantics of procedural models are almost never reversible, being termination states sink vertices. We saw that whenever lacking graph reversibility, projectors play a fundamental role in providing quantum representation of graphs. However, to rely on projectors means to give up on unitary evolution. So it seems as if procedural computations and unitary evolution are like oil and water. One could argue that a reversible operational semantics can be defined for any imperative program that always terminates. Which is of course true, as it is true that classical Boolean circuits can be embedded into reversible ones, and hence into quantum circuits. The cost must be paid in terms of space occupancy and an upper bound for the number of computational steps should be available a-priori in order to allocate the right amount of space (qubits). Notice that a proposal for a compiler of a fragment of the C language into Quantum Annealers has been presented in [21]. It is worth mentioning that even though Quantum Annealers are currently one of the most used architectures that exploit quantum mechanics, they are not general quantum machines and the debate on the speed-up they achieve is still open (see, e.g., [22, 23]). As a matter of fact, the most recent works in the direction of defining the boundaries of quantum supremacy rely on photonic processors [24]. We argue that a better chance for compiling classical languages into quantum comes from declarative languages. The most easy way to get a grasp of our intuition is that of considering assignments and the no-cloning theorem. The no-cloning theorem states that the function that makes a copy of an unknown, generic quantum state is not unitary, and as such it cannot be realized in a purely quantum model. While this is a major obstacle for the compilation of procedural languages, where assignments make copies of values, it is coherent with the spirit of declarative programming, where assignments and in general side effects are avoided. We argue significant developments on this matter may come from joint efforts between the two involved research fields. In the case of functional languages, the most natural semantics is the denotational one, which associates to a program the function it defines. Since classical architectures are by nature operational, the denotational semantics of such languages have been mainly exploited to prove correctness of the programs, while the effort of producing the equivalent procedural version is paid by the compiler. In this sense a quantum compilation would instead consist in the embedding of the denotation of the program into a reversible unitary function, which should then be compiled into a quantum circuit. The compilation of unitaries into quantum circuits is a hot topic in the quantum community and different techniques are under development to optimize the task (see, e.g., [25, 26]). As far as the embedding of a computable function into a unitary one is concerned, since the framework of Quantum Circuits becomes Turing Complete only when we endow it a classical model that generates uniform families of circuits, we cannot expect to be able to compile any computable function into a unitary one. This is the point where we envisage that compositionality properties of the denotational semantics should come into play to decompose the whole denotation in subcomponents. For each of these subcomponents the compiler should be able to identify whether it is amenable to quantum compilation and quantum speed-up or it is better to implement it in a classical fashion. As far as logic and constraint based languages are concerned, a similar analysis should be conducted referring to model-theoretic semantics instead of denotational ones. In a sense this makes the picture more challenging than the functional case. It comes not as a surprise being the framework the most high level one. However, our analysis of graphs and quantum walks is pertinent with several aspects of this approach. One concerns the solving stage in Answer Set Programming (ASP), which relies on a depen- dency graph for the assignment of truth values to the atoms, in accordance with the constraints defined in the model. Dependency graphs supporting stable models and quantum walk amenable graphs share few commonalities due to loops. Future studies could focus on encoding techniques to conciliate these two conflicting classes of graphs. The link between ASP and quantum computation is reinforced by the work in [27], where stable models search was given a solution through Grover’s algorithm. Aside from the resulting quadratic speed-up, the work leads to a broader implication: any ASP program may be executed on quantum architecture. This is a first effort in the same direction that we are proposing; our aim is to generalize it. Ideally, the investigations could set off from quantum SAT solvers [28], thus extending the above result to any SAT solving-based program. The case of MiniZinc is analogous: a graph underlies the evolution of the domains of the vari- ables. In this context, consistency properties over such graph are at the basis of the computation. While on classical machines many techniques have been developed to remove symmetries over the graph, thus reducing the computational complexity, in the case of quantum computation we observed in Section 3 that the more a graph is symmetric the more likely it is amenable to quantum encoding and quantum walks. References [1] R. P. Feynman, Simulating physics with computers, in: Feynman and computation, CRC Press, 2018, pp. 133–153. [2] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete log- arithms on a quantum computer, SIAM Review 41 (1999) 303–332. doi:10.1137/ S0036144598347011. [3] L. K. Grover, A fast quantum mechanical algorithm for database search, in: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, Association for Computing Machinery, New York, NY, USA, 1996, p. 212–219. URL: https: //doi.org/10.1145/237814.237866. doi:10.1145/237814.237866. [4] L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 (1736) 128–140. [5] C. H. Papadimitriou, Computational complexity, 1993. [6] A. Montanaro, Quantum walks on directed graphs, arXiv preprint quant-ph/0504116 (2005). [7] J. Kempe, Quantum random walks: An introductory overview, Contemporary Physics 44 (2003) 307–327. doi:10.1080/00107151031000110776. [8] A. S. Bhatia, A. Kumar, Quantum finite automata: survey, status and research directions, 2019. arXiv:1901.07992. [9] A. W. Harrow, A. Hassidim, S. Lloyd, Quantum algorithm for linear systems of equations, Physical review letters 103 (2009) 150502. [10] M. Ying, Foundations of Quantum Programming, 1st ed., Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2016. [11] M. A. Nielsen, I. Chuang, Quantum computation and quantum information, 2002. [12] F. Harary, Graph Theory, Addison Wesley series in mathematics, Addison-Wesley, 1971. [13] R. Motwani, P. Raghavan, Randomized algorithms, Cambridge university press, 1995. [14] D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani, Quantum walks on graphs, in: Pro- ceedings of the thirty-third annual ACM symposium on Theory of computing, 2001, pp. 50–59. [15] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous, One-dimensional quantum walks, in: Proceedings of the thirty-third annual ACM symposium on Theory of computing, 2001, pp. 37–49. [16] A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett. 102 (2009) 180501. doi:10.1103/PhysRevLett.102.180501. [17] N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, V. Kendon, Universal quantum computa- tion using the discrete-time quantum walk, Physical Review A 81 (2010). doi:10.1103/ physreva.81.042330. [18] S. Severini, On the digraph of a unitary matrix, SIAM Journal on Matrix Analysis and Applications 25 (2003) 295–300. URL: https://doi.org/10.1137%2Fs0895479802410293. doi:10.1137/s0895479802410293. [19] S. Severini, Graphs of unitary matrices, 2003. URL: https://arxiv.org/abs/math/0303084. doi:10.48550/ARXIV.MATH/0303084. [20] D. Della 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, Springer International Publishing, Cham, 2022, pp. 75–92. [21] M. W. Hassan, S. Pakin, W.-c. Feng, C to d-wave: A high-level c compilation framework for quantum annealers, in: 2019 IEEE High Performance Extreme Computing Conference (HPEC), IEEE, 2019, pp. 1–8. [22] M. H. Amin, Searching for quantum speedup in quasistatic quantum annealers, Physical Review A 92 (2015) 052323. [23] J. King, S. Yarkoni, J. Raymond, I. Ozfidan, A. D. King, M. M. Nevisi, J. P. Hilton, C. C. McGeoch, Quantum annealing amid local ruggedness and global frustration, Journal of the Physical Society of Japan 88 (2019) 061007. [24] L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, et al., Quantum computational advantage with a programmable photonic processor, Nature 606 (2022) 75–81. [25] P. Niemann, R. Wille, R. Drechsler, Advanced exact synthesis of clifford+t circuits, Quantum Information Processing 19 (2020). doi:10.1007/s11128-020-02816-0. [26] M. Soeken, M. Roetteler, N. Wiebe, G. D. Micheli, Logic synthesis for quantum computing, 2017. arXiv:1706.02721. [27] D. Meyer, J. Pommersheim, J. Remmel, Finding stable models via quantum computation., 2004, pp. 285–291. [28] M. Mosca, S. R. Verschoor, Factoring semi-primes with (quantum) sat-solvers, Scientific Reports 12 (2019).