This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Quantum computation:
Efficient network partitioning for large scale critical infrastructures

Saikat Ray Majumder GE Research, 1 Research Circle, Niskayuna, NY 12309, USA    Annarita Giani GE Research, 1 Research Circle, Niskayuna, NY 12309, USA    Weiwei Shen GE Research, 1 Research Circle, Niskayuna, NY 12309, USA    Bogdan Neculaes GE Research, 1 Research Circle, Niskayuna, NY 12309, USA    Daiwei Zhu IonQ Inc, 4505 Campus Dr, College Park, MD 20740, USA    Sonika Johri IonQ Inc, 4505 Campus Dr, College Park, MD 20740, USA
Abstract

Quantum computers are emerging as a viable alternative to tackle certain computational problems that are challenging for classical computers. With the rapid development of quantum hardware such as those based on trapped ions, there is practical motivation for identifying risk management problems that are efficiently solvable with these systems. Here we focus on network partitioning as a means for analyzing risk in critical infrastructures and present a quantum approach for its implementation. It is based on the potential speedup quantum computers can provide in the identification of eigenvalues and eigenvectors of sparse graph Laplacians, a procedure which is constrained by time and memory on classical computers.

preprint: APS/123-QED

I Introduction

Complex networks are ubiquitous. Systems like power grids, the World Wide Web, social interactions, locomotive and airline networks, cellular networks, food webs, and sensor networks can all be modeled as complex networks. Additionally, in this current era of Industrial Internet of Things, more and more assets are continuously getting connected to each other resulting in large, complex and dynamic networks. The heightened connectivity leads to increased efficiency but often comes at the cost of increased vulnerability. Therefore, it is, important to closely monitor these networks, anticipate and prepare for disruptions and quickly identify efficient mitigation strategies. However, given the size and dynamic nature of these networks, traditional approaches based on discrete optimizations and statistical predictions often face significant limitations. To circumvent some of the limitations in the current modeling techniques, it turns out one can leverage the community structure of the networks. In addition, these network communities also provide a low dimensional graph embedding which can be used in many machine learning applications.

A traditional method used for community detection is network partitioning. There are existing classical algorithms for network partitioning but the computational and time complexity of such algorithms can grow significantly for large graphs. In this work, we briefly discuss how the rapidly developing technology of quantum computing may provide an edge over classical methods.

II Networks in the real world

Networks in the real world, such as power grids, supply delivery networks and social networks exhibit a high level of order and organization. The degree distribution in such networks often follows a power law in the tail, denoting the fact that many vertices with low degrees coexist with a few vertices with large degrees. These networks exhibit many interesting structural properties, especially when they are large scale and grow in a decentralized and independent fashion, thus not the result of a global, but rather of many local autonomous designs. We briefly describe here two examples of such critical infrastructures, where network analysis can provide significant benefits: supply chain and power grid.

II.1 Supply Chain Risk and Resilience

Suppliers in a supply chain are divided according to the distance to the final product. Tier 1 suppliers provide product to the manufacturer directly. Tier 3 suppliers are two steps down in the chain. Traditional supply chain risk management focuses on Tier 1 suppliers of “critical” goods; however, risk can lie in any tier or echelon of a supply chain [1]. Suppose a lesser-known supplier, several tiers deep in the supply chain, goes out of business due to a lack of working capital availability (red nodes in Fig. 1). This bankruptcy then leads to a cascading disruption in the supply chain due to this company’s structural position in the extended network, ultimately disrupting or shutting down the manufacturing facility of a major OEM (Original Equipment Manufacturer).

Refer to caption
Figure 1: A multi-echelon supply chain

One such example is Evonik Industries, a little-known raw materials supplier, whose plant explosion in 2012 caused major disruptions in the production of automobiles throughout the global automotive industry [2]. Identifying and mitigating these types of disruption risks is difficult since many such critical suppliers can be several tiers deep in the supply chain and hence not visible to risk managers until the disruption is already occurring. In recent years, techniques from the domains of graph theory and complex network analysis (CN) have been adapted to address such problems and quantify systemic risks and resilience of the supply network in a scalable fashion. This approach may enable risk managers to understand the indirect effects that interventions in one part of the supply chain can have on another part [3].

Graph analytics exploit network topology to define properties such as centrality measures, clusters, critical nodes, tipping points and resilience. Risk managers can use these features to gain insights into the nature of the network and be proactive in taking early mitigation steps to address risks at their nascent stages. For instance, this framework can rank suppliers who are more central to the network and should be monitored more closely. These well-connected suppliers play a major role in the network by controlling the overall performance of the network and ensuring a system wide coordination to drive greater efficiency. Due to their high connectivity, these hub firms have an outsized influence over the network, which leads to better self-coordination, less duplications and lower transaction costs. One can measure the impact that a supplier has on the efficiency of a network by calculating the supplier’s contribution to the characteristic path of the network. A network with short characteristic path length will ensure quick diffusion of new information enabling more efficient material and financial flows throughout the network. If suppliers default and are removed from a network, the characteristic path lengths will increase, and ultimately vertex pairs will become disconnected and communication between them through the network will become impossible. One can develop metrics of rapid change to signal that the supply network is approaching a tipping point. In many networks tipping points exist at which dynamics of the network abruptly changes. War, riots, pandemic, natural disaster, or economic downturn are obvious triggers of such tipping points. Yet, not all networks succumb to such exogenous shocks. One can investigate how stronger financial health of the suppliers can make the network more resilient to external risks.

II.2 Power Grid

Power grid is a highly complex cyber-physical system with lots of interconnected components. Physical measurement data are delivered from remote technical units (RTUs) to supervisory control and data acquisition (SCADA) systems and then to Advanced Energy Management System (AEMS) applications responsible for controlling and monitoring the power system. This gives rise to a significant challenge in maintaining and operating the grid while ensuring high level of resiliency against normal disruptions and cyber attacks.

Graph theory provides a mathematical object that naturally encodes relationships and hence provides a robust framework to build such applications  [4, 5, 6, 7]. For instance, with the data cast as a graph, the problem often boils down to identifying a small subset of nodes with much higher volume of network traffic, than is typical for those nodes, indicating the onset of some malicious activity. Essentially the goal it to identify network interactions which do not fit the model of typical, normal behavior and thereby detect and counter malicious activity. But identifying graph patterns from within the vast and complex network is a classic subgraph isomorphism problem and is known to be computationally expensive and NP-complete  [8, 9]. Additional complexity is the requirement to detect the pattern before it is fully instantiated. This introduces new algorithmic challenges because one cannot afford to index a dynamic graph frequently enough for applications with real-time constraints.

III Classical approach

In both of the above use cases (and, also in similar other application domains) the primary challenge is the scalability of the traditional methodologies. These networks are dynamic complex systems with non-linear interactions and often need to be analyzed at a system level. However, the networks can comprise of tens of thousand of nodes and that is where many traditional methods run into computational challenges. One potential solution is to find appropriate clusters, or communities in these networks and thereby reduce the dimensionality of the problem by partitioning the large graph into smaller sub-graphs.

III.1 Community Detection

Large networks exhibit lack of homogeneity both globally and locally. The local inhomogeneities give rise to a dense concentration of edges within groups of vertices and very sparse connections between groups. This feature of a network is called its community structure or clustering. Communities reveal the hierarchical organization of the network and mark groups of nodes which share common properties, exchange more transactions or information or have similar functions [10, 11]. Community detection is therefore a very important task in network analysis.

The presence of communities in real world networks is quite intuitive. However, the task of detecting these communities is often very challenging. One problem is that the definitions of a community and a partition are not rigorous. Classical techniques for data clustering, like hierarchical, partitional and spectral clustering have been adopted for graph clustering. Other methods include neural network clustering and multi dimensional scaling techniques, such as singular value decomposition and principal component analysis. Many of these clustering techniques are NP-hard.

Spectral clustering uses the graph Lapalacian. Normal graph Lapalacian is defined as follows:

L(G)=D(G)A(G)L(G)=D(G)-A(G) (1)

where, AA is the adjacency matrix of the graph GG and DD is the degree matrix. The Laplacian is positive semidefinite, that is, all eigenvalues are non-negative. Eigenvector decomposition of the Laplacian is closely related to the clustering problem. The number of zero eigenvalues correspond to the number of connected components in the graph. Eigenvalues close to zero denote that there is almost a separation into two components. Hence, if there are NcN_{c} clusters in a network, in spectral clustering it is required to find the eigenvectors of the Laplacian corresponding to the smallest NcN_{c} eigenvalues. The second smallest eigenvalue of the Lapalacian is called the Fiedler eigenvalue and the corresponding eigenvector is called the Fiedler vector. Fiedler value indicates how well connected the graph is and Fiedler vector can be used to bisect the graph based on the sign of the corresponding element in the vector.

For large graphs with NN vertices it is however impossible to have exact diagonalization solutions as the time complexity is O(N3)O(N^{3}). In such cases approximate algorithms are used [11]. As outlined in [11], approximate algorithms, including those for sparse graphs cannot scale faster than O(N)O(N) or O(M)O(M) (where MM is the number of edges in the graph). Of even more serious concern may be the memory requirements for diagonalization which also scale as O(N)O(N). Hence, for large graphs, even approximate algorithms on classical computers may be insufficient to diagonalize the graph Laplacian as they will scale at least linearly in the number of vertices and edges of the graph. In these cases, the rapidly developing technology of quantum computing may provide an edge over classical methods.

IV Quantum approach

Quantum computers work with quantum bits, or ‘qubits’, which differ from classical bits in that they can be in a superposition of 0 and 1 at the same time. Further, qubits can be entangled, so that a system of nn qubits can be in a superposition of 2n2^{n} classical states (bit strings) kk described by the quantum state |ϕ=kak|k|\phi\rangle=\sum_{k}a_{k}|k\rangle. Here aka_{k} are complex numbers which satisfy the rule k|ak|2=1\sum_{k}|a_{k}|^{2}=1.

On quantum computers, the problem of finding eigenvalues of a Hermitian matrix can be tackled using the quantum phase estimation algorithm, which proceeds as follows: given a unitary matrix UU and a quantum state |ψ|\psi\rangle defined on n=log2(N)n=\log_{2}(N) qubits such that U|ψ=ei2πθ|ψU|\psi\rangle=e^{i2\pi\theta}|\psi\rangle, phase estimation allows one to determine θ\theta with precision δ\delta using O(log(1/δ)+log(N))O(\log(1/\delta)+\log(N)) qubits with O(1/δ)O(1/\delta) controlled applications of the unitary matrix UU. UU can be expressed as the ‘time-evolution’ under the Hermitian matrix. In the problem of (undirected) graph partitioning, the Laplacian LL being real and symmetric is Hermitian, so we can write U=eiLtU=e^{iLt}. Let’s assume that LL is normalized such that its maximum eigenvalue is 1 and we set t=2πt=2\pi. Then δ\delta is chosen such that it is the smaller of the distance between the eigenvalues of interest and the precision to which an eigenvalue needs to be known. For quantum phase estimation to be effectively applied, one must then find an efficient implementation of UU, as well as an efficient way to prepare the quantum state ψ\psi.

We first outline the task of implementing U=eiLtU=e^{iLt}. A technique for this is given in Ref. [12]. According to this method, given a dd-sparse Hermitian matrix LL (which is normalized such that LdLmax=1\frac{||L||}{d||L||_{max}}=1), one can implement the operator eiLte^{iLt} (up to an error ϵ\epsilon) with O(t+log(1/ϵ))O(t+\log(1/\epsilon)) calls to an oracle that returns the matrix element given the row and column, and an oracle that returns a sequence of column indices in a particular row. These oracles will typically be implemented in time O(log(N))O(\log(N)). If LL is sparse, as is typical for practical cases of interest, the application of LL with sparsity dd will have time complexity to leading order of O(dlog(N))O(d\log(N)), giving an overall runtime that scales as O(dlog(N)/δ)O(d\log(N)/\delta). Thus, the quantum algorithm provides exponential speed-up in the size of the matrix for both time and memory.

More speculatively, the time complexity may be further reduced if as a preprocessing step, a variational quantum algorithm is used to learn a quantum circuit which encodes time-evolution under the graph Laplacian. While this is a heuristic procedure for which time-complexity scaling is not guaranteed, it can presumably lead to finding a more efficient implementation of the time-evolution operator. This should form an area of research for risk management on near-term quantum computers.

Next, we turn to the task of preparing the initial state |ψ0|\psi_{0}\rangle on which UU will act. Since we don’t know the eigenvectors in advance, it is not possible to prepare an exact version of |ψ|\psi\rangle even if we knew how to do it efficiently. Therefore, our goal is to prepare |ψ0|\psi_{0}\rangle as close to |ψ|\psi\rangle as possible. On repeating the phase estimation procedure several times, a distribution over the eigenvalues will be obtained, where the probability of obtaining a particular value is equal to |ψj|ψ0|2|\langle\psi_{j}|\psi_{0}\rangle|^{2}. In principle, starting with a random input state will give some non-zero overlap with the desired largest eigenvectors, but these may be too small to be practically useful. Hence a few different strategies can be adopted:

1. Using matrix product states which scale as log(n)\log(n) to prepare a bounded-entanglement approximation of the largest eigenvalue state, and converting this to a quantum circuit.

2. Adiabatic approach: This involves starting in a quantum state that is a product state of the qubits, or one that can be prepared with a low-depth circuit. This starting state is the ground state of a known Hamiltonian whose time-evolution is easily implementable. Then a discretized adiabatic evolution which slowly changes the time-evolution from the starting Hamiltonian to that under LL can be used to prepare an approximation of the ground states of LL. The time for this approach scales as 1/δ1/\delta.

3. Variational approach: A heuristic approach which uses a variational quantum circuit whose parameters are tuned according to a cost function based on LL

In addition to the eigenvalues, eigenvectors can also be determined by sampling the output eigenstate. The probability of measuring a particular basis state kk is |ak|2|a_{k}|^{2}, where aka_{k} is the eigenvector element. Therefore, the largest elements of the eigenvector can be determined efficiently. More precisely, the eigenvector elements can be determined to a precision 1/Nsamples1/\sqrt{N_{\text{samples}}}, where NsamplesN_{\text{samples}} is the number of times the procedure is repeated.

The number of 0 eigenvalues can be determined by preparing multiple copies of |ψ0|\psi_{0}\rangle starting from orthogonal initializations of the qubits and then projecting them into a state which gives 0 eigenvalue after phase estimation. The number of unique states that can be so prepared then gives the degeneracy of the eigenvalue.

V Realization on Quantum Hardware

Quantum hardware, while still in a nascent stage, is rapidly advancing to be powerful enough to demonstrate algorithms like the ones described above. Leading quantum hardware platforms include trapped ions, superconducting qubits, neutral atoms, and photonic qubits. With the rapid development of quantum computing hardware, proposals for benchmarking performance in an application-oriented manner have been put forth [13]. One such example is Algorithmic Qubits (AQ) 111https://ionq.com/posts/february-23-2022-algorithmic-qubits. Under this definition, quantum hardware from IonQ has advanced from AQ 6 to AQ 23 in 2 years, and is projected to reach AQ 64 by 2025, at which point it will be beyond the simulation capabilities of classical computers.

Small scale demonstrations of quantum phase estimation algorithms discussed in this white paper include one on a silicon photonic chip [15] and using machine learning to enhance the measurement of eigenvalues [16].

VI Conclusions and Proposed Future Work

Large scale complex networks are key for today’s world, with multiple national security implications. However, the large sizes of these networks often limit the use of standard algorithms and approaches to analyze them. Community structure of the networks provides a powerful feature to circumvent some of these challenges. Since there is an expected low level of interdependence between the communities, the ensuing analysis more naturally renders to parallel computation thereby making it scalable and more efficient. For instance, identifying clusters of suppliers based on industrial sectors or regions enables a supply chain risk manager to better understand the risk dynamics and their inter-dependencies while simultaneously reducing the computational burden of analysing the full supply delivery network.

Network partitioning is a popular technique in community detection and can be done by diagonalizing the graph Laplacian. However, this approach is constrained by time and memory on classical computers. Quantum computing can identify eigenvalues and eigenvectors for sparse matrices exponentially faster in the size of the matrix compared to classical computers and thus has applications in risk management of networks.

While quantum computing is a nascent technology, the quality and robustness of quantum computers is improving rapidly. We propose the following research strategy for pursuing this approach:
- Identify examples of networks that are relevant for critical infrastructure
- Develop concrete quantum algorithms customized for these networks and implement them in a quantum software framework
- Carry out resource estimates for the number of qubits and fidelity required to analyze real-life networks
- Test the algorithms on simulators to verify correctness and robustness to noise
- Test simplified versions of these algorithms on available quantum hardware

At the conclusion of the vision detailed above, one would be able to quantify the impact of quantum computing on network partitioning, a computing problem with dramatic civilian and national security implications. In addition, the effort will lay out the hardware timeline for practical implementation of quantum solutions to this problem.

References

  • Yan et al. [2015] T. Yan, T. Choi, Y. Kim, and Y. Yang, A theory of the nexus supplier: A critical supplier from a network perspective, J Supply Chain Manag 51, 52 (2015).
  • evo [2012] Explosion at evonik factory may have serious knock-on effect for global car production, Automotive Industries AI. 192, 4 (2012).
  • Ritter et al. [2004] T. Ritter, I. Wilkinson, and W. Johnston, Managing in complex business networks, Industrial Marketing Management 33, 175 (2004).
  • Kaiser and Witthaut [2021] F. Kaiser and D. Witthaut, Topological theory of resilience and failure spreading in flow networks, Phys. Rev. Research 3, 023161 (2021).
  • Guo et al. [2019] H. Guo, S. S. Yu, H. H. C. Iu, T. Fernando, and C. Zheng, A complex network theory analytical approach to power system cascading failure—from a cyber-physical perspective, Chaos: An Interdisciplinary Journal of Nonlinear Science 29, 053111 (2019)https://doi.org/10.1063/1.5092629 .
  • Szoplik [2010a] J. Szoplik, Quantitative analysis of the heterogeneity for gas flow in the pipeline system., Gaz, Woda i Technika Sanitarna 1 (2010a).
  • Szoplik [2010b] J. Szoplik, The application of the graph theory to the analysis of gas flow in a pipeline network., 37th International Conference of SSCHE CD-ROM (2010b).
  • Cook [1971] S. A. Cook, The complexity of theorem-proving procedures, Proc. 3rd ACM Symposium on Theory of Computing  (1971).
  • T. H. Cormen and Rivest [1990] C. E. L. T. H. Cormen and R. L. Rivest, Introduction to Algorithms (Cambridge, Mass.: MIT Press, 1990).
  • Lu et al. [2018] Z. Lu, J. Wahlström, and A. Nehorai, Community detection in complex networks via clique conductance, Scientific Reports 8 (2018).
  • Fortunato [2010] S. Fortunato, Community detection in graphs, Physics Reports 486, 75 (2010).
  • Low and Chuang [2019] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, Quantum 3 (2019).
  • Lubinski et al. [2021] T. Lubinski, S. Johri, P. Varosy, J. Coleman, L. Zhao, J. Necaise, C. H. Baldwin, K. Mayer, and T. Proctor, Application-oriented performance benchmarks for quantum computing (2021).
  • Note [1] https://ionq.com/posts/february-23-2022-algorithmic-qubits.
  • Paesani et al. [2017] S. Paesani, A. A. Gentile, R. Santagati, J. Wang, N. Wiebe, D. P. Tew, J. L. O’Brien, and M. G. Thompson, Experimental bayesian quantum phase estimation on a silicon photonic chip, Phys. Rev. Lett. 118, 100503 (2017).
  • Lumino et al. [2018] A. Lumino, E. Polino, A. S. Rab, G. Milani, N. Spagnolo, N. Wiebe, and F. Sciarrino, Experimental phase estimation enhanced by machine learning, Phys. Rev. Applied 10, 044033 (2018).