Modern science is more diverse than ever. Seemingly distant terms such as quantum, network, learning, neural, complex and cryptography are now combined into all-new scientific disciplines. While quantum cryptography is a present technology [1], the study of the structure and dynamics of complex quantum networks [2, 3] is at infancy. These networks are radically different from their classical counterpart [4, 5] due to quantum superposition and non-locality, and unique features of quantum dynamics and measurements [6]. Quantum networks exhibit non-classical clustering [7] and synchronization [8] and may undergo non-trivial phase transitions [9, 10].

The evaluation of controllability of quantum networks typically starts with the definition of the system Hamiltonian and the coupling [11,12,13]. In practice, some information about the network dynamics may be missing. Suppose we know just the structure of the network and that the connected vertices interact linearly. Having this very limited knowledge, is it still possible to make some conclusions about the network controllability? In classical network science, the answer is affirmative due to the Lin’s structural controllability theorem [14], which severely restricts our ability to gain control over a complex system. I show that this restriction is no longer valid for quantum networks, if we allow local operations and classical communication (LOCC) between the network vertices. Following general geometrical consideration, I show that a quantum network with an arbitrary structure can exhibit structural controllability with a single driving vertex, if modified with a polynomial number of LOCC.

In classical control theory, if a complex system \((\mathbf{A};\mathbf{B})\) can be described with a set of linear differential equations

$$\begin{aligned} \dot{\mathbf{x}}(t) = \mathbf{A} \, \mathbf{x}(t) + \mathbf{B} \, \mathbf{u}(t) \end{aligned}$$
(1)

at any time, it is called linear time-invariant system [15]. Here, \(\mathbf{x}(t)\) is the vector of system parameters; \(\mathbf{u}(t)\) is the input vector of independent driving signals; the state matrix \(\mathbf{A}\) describes which system components interact with each other and the direction of the interaction; and the input matrix \(\mathbf{B}\) identifies externally driven system parameters.

Such a system may be represented with a directed graph (digraph) \(G(\mathbf{A};\mathbf{B}) = (V_G;E)\), which structure does not change in time. The vertex set \(V_G = V \bigcup U \) includes both the state vertices V, corresponding to the N vertices of the network, and the driving vertices U, corresponding to the M input signals that are called the roots of the digraph \(G(\mathbf{A};\mathbf{B})\). The edge set \(E = E_V \bigcup E_U\) consists of the edges among state vertices \(E_V\), corresponding to the connections of the network, and the edges connecting driving vertices to state vertices \(E_U\). In this term, Lin’s theorem is given as: The system \((\mathbf{A};\mathbf{B})\) is not structurally controllable if and only if it has inaccessible nodes or dilations [14].

A state vertex is inaccessible if there are no directed paths reaching it from the input vertices. An inaccessible vertex cannot be influenced by driving signals, making the whole network uncontrollable. The digraph \(G(\mathbf{A};\mathbf{B})\) contains a dilation if there is a subset of vertices \(S \subset V\) such that the neighborhood set of S has fewer vertices than S itself. Roughly speaking, dilations are subgraphs in which a small subset of vertices attempts to rule a larger subset of vertices (see Fig. 1a).

This formulation is not practical, because does not tell us how many driving signals we should have in a given network to make it controllable. Alternatively, we may state that: An LTI system \((\mathbf{A} ; \mathbf{B} )\) is structurally controllable if and only if \(G(\mathbf{A};\mathbf{B})\) is spanned by cacti.

A graph is spanned by a subgraph if the subgraph and the graph have the same vertex set. For a digraph, a sequence of oriented edges \(\{v_1 \rightarrow v_2, \ldots , v_{k-1} \rightarrow v_k \}\), where vertices \(\{ v_1, v_2, \ldots , v_{k-1}, v_k \}\) are distinct, is called an elementary path C. When \(v_k\) coincides with \(v_1\), the sequence of edges is called an elementary cycle O. For the digraph \(G(\mathbf{A};\mathbf{B})\), let me define the following subgraphs: (i) A stem is an elementary path originating from an input vertex; (ii) a bud is an elementary cycle C with an additional edge e that ends, but does not begin, in a vertex of the cycle; and (iii) a cactus is defined recursively: A stem C is a cactus. Let C, O and e be, respectively, a cactus, an elementary cycle that is disjoint with C and an arc that connects C to O in \(G(\mathbf{A};\mathbf{B})\). Then, \(C \cup \{e\} \cup O\) is also a cactus. \(G(\mathbf{A};\mathbf{B})\) is spanned by cacti if there exists a set of disjoint cacti that covers all state vertices.

Fig. 1
figure 1

a A digraph with a single root. Network vertices and edges are shown in gray; driving vertices and edges, in blue. Vertex \(\{V_4\}\) is inaccessible from the driving vertex \(\{U_1\}\). Vertices \(\{V_1, V_3, V_2\}\) form a dilation. b Elementary path \(\{ V_6, V_3, V_1 \}\) and two elementary cycles \(\{ V_2, V_4\}\) and \(\{ V_5, V_7\}\) connected to the root \(\{U_1\}\) form a cactus. This network is structurally controllable by a single drive (Color figure online)

Full size image

A cactus is a minimal structure that contains neither inaccessible nodes nor dilations (see Fig. 1b). A complex network is unlikely to be spanned by a single cactus. But, it may be spanned by a few. Since the control of a single cactus requires a single root, to control a complex network we need as many driving signals as many cacti span the network. In practice, we want to find the minimal number of the driving signals to control a given network—the so-called minimum input problem [15]. Hence, we need to find the minimal number of cacti to span a given network. This combinatorial problem can be resolved in polynomial time with the maximum matching algorithm (see Fig. 2).

In a digraph, a matching is defined to be a set of directed edges that do not share common start or end vertices. A vertex is matched if it is the end vertex of a matching edge. Otherwise, it is unmatched. Maximum matching is a matching of the largest size. These definitions allow us to formulate the minimum input theorem: To fully control a system \(G(\mathbf{A};\mathbf{B})\), the minimum number of driver vertices is \(N_D = \mathrm{max} \{ N - M, 1 \}\), where M is the size of the maximum matching in \(G(\mathbf{A};\mathbf{B})\). In other words, the driver vertices correspond to the unmatched vertices. If all vertices are matched \(M=N\) (as in case of an elementary cycle), we need at least one input to control the network; hence, \(N_D = 1\). We can choose any vertex as our driver vertex in this case. Note that in general the maximum matching is not unique; i.e., the network may be controllable with different minimal sets of driver vertices. But, all these minimal sets are of the same size. The algorithm gives us the number and location of the drivers to apply to the network and hence concludes the study of the structural controllability.

Fig. 2
figure 2

a A graph to find a minimum driver set. b Maximum matching is shown in red. Only two vertices \(\{ V_6 \}\) and \(\{V_7\}\) are unmatched. The network requires two independent drives/roots to be controllable (Color figure online)

Full size image

In quantum networks, a vertex possesses a quantum system, such as atom, quantum dot or molecule. If two vertices are connected with an edge, they may communicate photons and classical information. An edge is directed according to the ability of a vertex to send photons to others. Classical information may be communicated between connected vertices both ways irrespective of edge directions. This setup fits most quantum communication protocols [6].

Because the quantum systems interact with each other and the environment that may be present in the vertices, the quantum network dynamics is the subject of open quantum system dynamics [16], which is in general nonlinear. However, there are few occasions, when the dynamics of an open quantum system may be described with linear differential equations as Eq. (1). For example, dissipative harmonic oscillator may be described with linear Master and Langevin equations [16]. This type of quantum dynamics of the vertices we must imply to ensure that the quantum network can be described with Eq. (1). Whenever the behavior of a quantum system cannot be correctly described with a system of linear differential equations (1), further considerations are invalid.

The difference between classical and quantum networks is that the latter are non-local. This leads to the fact that distant vertices may become entangled and display correlated dynamics, even so they are not connected with an edge. The entanglement may appear spontaneously as a result of the nonlinear dynamics [8] or may be created by LOCC [9]. The entanglement between distant vertices may be interpreted as a new edge of the network [9, 10]. The direction of this entanglement edge is defined by the order of local operations and the direction of the classical communication [16]. The LOCC may be used to loop all inaccessible vertices and dilations into elementary cycles, modifying the network so that it is spanned by a single cactus, i.e., all its vertices are matched.

To be specific, let us suppose that we have a connected quantum network represented by a digraph and of the same configuration as in Fig. 2a. We may investigate its classical structural controllability by executing the maximum matching algorithm to identify the minimal set of driving vertices. The network is spanned by two cacti, due to a dilation \(\{V_3, V_7, V_4\}\). Let us choose one of the two elementary paths, say \(\{V_6, V_5, V_4, V_2\}\) and loop it into an elementary cycle by LOCC.

The procedure can be exemplified as follows. Suppose we have a quantum network consisting of three vertices \(\{a, b, c\}\), so that a is connected to b and b is connected to c. The quantum system at the vertex a may be entangled with a quantum field mode, which is communicated to the vertex b. Subjected with the classical communication, vertex a is entangled with b; i.e., we created an entanglement edge. Through this edge, the quantum system at b may influence the system at a by performing local manipulation at b and communicating information classically to a [6]. In this case, the direction of the classical communication sets the direction of the entanglement edge. If a is entangled to b and b is entangled to c, we may apply entanglement swapping at b. This creates a non-local entanglement edge \(a-c\). The edge may be directed both ways depending on the classical information flow.

Similarly, we may get rid of inaccessible vertices, in case of their presence. If we have a subgraph of inaccessible vertices in our connected graph, then there is at least one border vertex of the subgraph that has an edge directed from it to an accessible vertex. The inaccessible vertex may become entangled with the accessible vertex by LOCC. Hence, these two vertices are looped into an elementary cycle consisting of just two vertices. Iteratively, all the subgraph of inaccessible vertices may become accessible. As a result, the modified network is spanned by a single cactus, thus controllable by a single root. In general, the whole procedure can be executed for arbitrary two distant vertices in a finite connected network of size N with at most \(N^3\) LOCC [17].

Fig. 3
figure 3

a By LOCC, we may loop the elementary path \(\{V_6, V_5, V_4, V_2\}\) into an elementary circle increasing maximal matching of the quantum digraph. b The modification of the quantum digraph with LOCC may be viewed as creation of a super-vertex \(\{ V_{2-6} \}\)

Full size image

I showed that the restrictions of the Lin’s theorem that are fundamental to classical networks do not apply to quantum networks. This is another radical difference between classical and quantum instances. The result is independent of the quantum network structure and is purely based on our ability to create non-local correlations with LOCC.

To make a conclusion about structural controllability of a network, we must be sure that the structure of the network does not change in time. This may be guaranteed if the network is described with a system of linear equations. But, do LOCC change linearity of the quantum dynamical equations? Under some reasonable assumptions, the initial entanglement between two systems leaves the dynamical equations linear adding an inhomogeneous term [18]. But, this is an exception rather than the rule. Can we still conclude about the structural controllability? Yes, if we consider the entangled vertices as single super-vertex (see Fig. 3). Then, we must ensure that the super-vertex is coupled linearly to the neighbors; i.e., the output field operators of the super-vertex and the input field operators of the neighboring vertices are linearly dependent [19]. In this case, the network remains linear, in spite of the nonlinear internal dynamics of the super-vertex.

Structural controllability analysis is the very first step to evaluate network controllability. Although a network may be structurally controllable, for some combination of the dynamical parameters, it may not be controllable [15]. Hence, we need to establish the so-called strong structural controllability; that is, the network is controllable for any combination of the dynamical parameters. This analysis requires full information about the network parameters and analytical tools to process this information. The Kalman’s criterion of controllability [15] is as fundamental as the Lin’s theorem for structural controllability and may also fail as the latter, if applied to quantum networks. This urges a revision of our knowledge and strategies to establish control over complex quantum networks.