The encoding of graphs and the development of eficient 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.
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 [
Since that moment, both academia and companies have put a lot of efort 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.
Projections, 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 [
As a consequence, to understand and generalize quantum speed-up results, one could
investigate 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 [
In light of these theoretical questions, the use of Quantum Hardware is hardly justifiable:
only a handful of algorithms fully exploit its benefits. While eforts have been directed toward
defining further eficient quantum algorithms through Quantum Programming Languages [
Our intuition starts by observing the dificulties arising in the quantum encoding and management of graphs. These complications are strongly related to the intrinsic reversibility of quantum computation. Intuitively, only strongly connected graphs are reversible. As a consequence, an eficient compilation of procedural languages that rely on operational semantics, i.e., on graphs, looks dificult. 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 diferent 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.
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 [
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 if † = † = . 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.
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 can be embedded into the reversible function defined as
: {0, 1} → {0, 1} : {0, 1}+1 → {0, 1}+1
(, ) = (, ⊕ ()) 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.
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 [
Graphs are the key data structure for eficiently 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 eficiently 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 [
In the context of randomized computations, again graphs, and in particular random walks
over graphs, play a central role both in the design of eficient algorithms and in the development
of general strategies for speeding-up their convergence [
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 eficiently solve the reachability problem has already the ability to eficiently 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 eficiently solved over a quantum model?
• How can graphs be eficiently 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 diferent 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 diferent directions. Diferently 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 [
Are these unsatisfactory answers to the above questions just a matter of how much efort 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.
In classical computations graphs are largely used as an abstract data structure where to encode the input knowledge and eficient 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 diferences: (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 [
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.
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
0 − 1/√2 1/2 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⟩ = √2 |1⟩ + 2 |2⟩ + 2 |3⟩ . =
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 efect: 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 [
Strong Quadrangularity In [
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 +() ∩ +()⃒⃒⃒⃒⃒ ≥ | out|; ⃒⃒⃒⃒⃒ ,⋃∈︁in − () ∩ − ()⃒⃒⃒⃒⃒ ≥ | in|.
Although apparently abstract, the property of strong quadrangularity provides deep, matrixtheoretical insights over the class of graphs of unitary matrices.
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. [
A broader version of the discussion involves the notion of line graph.
Definition 4 (Line Graph). Given a graph = (, ), the respective line graph i→s− =→(− →,− ) 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.
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. [
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 diferent path, Montanaro studied graphs of unitary
matrices from the perspective of graph reversibility [
Eulerian
→− Specular, strongly quadrangular
Graph of unitary matrix
Strongly quadrangular
Reversible
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 diferent disconnected strongly connected components.
The following result provides the main connection between graphs of unitary matrices and reversibility.
Theorem 3. [
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.
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 [
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 ′.
Theorem 4. A connected graph = (, ) is Eulerian if, 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.
notion of graph reversibility, Montanaro has also developed a procedure to edit irreversible
graphs so to satisfy this newly defined graph property [
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 efect of the removal is twofold: (i) is structured into diferent 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, ifnding 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.
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 afects graph topology, albeit in a somewhat softer way. In turn, these efects appear to produce phenomena of local bias in the resulting quantum walk.
A large part of quantum computing research focuses on the development of eficient quantum
algorithms and quantum programming languages that should allow to code such algorithms
(see, e.g., [
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 [
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 efects are avoided. We argue significant developments on this matter may come from joint eforts 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 efort 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 diferent techniques are under development to
optimize the task (see, e.g., [
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 dependency 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 efort in the same direction that we are proposing; our aim is to generalize it. Ideally, the investigations could set of 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 variables. 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.
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).