## Abstract

PageRank is an algorithm used by Google Search to rank web pages in their search engine results. An important step for quantum networks is to quantize the classical protocol as quantum mechanics provides computational resources that can be used to outperform classical algorithms. In this paper, we experimentally realize continuous-time quantum walks for directed graphs with non-Hermitian adjacency matrices by using linear optical circuits and single photons. We find that the node classical centrality in a directed graph is correlated with the maximum node probability resulting from a continuous-time quantum walk and then demonstrate PageRank. Our work opens up an avenue of applications of quantum information in real-life tasks.

© 2020 Optical Society of America under the terms of the OSA Open Access Publishing Agreement

## 1. INTRODUCTION

During the past two decades, significant experimental progress towards quantum computers [1], quantum cryptography [2,3] and quantum simulators [4] has spurred increased interest in quantum walks (QWs). Since most quantum simulators today are realized in finite-dimensional systems [5], single- and many-particle QWs on finite lattices [6] and their implications have become a subject of intense theoretical scrutiny and practical importance [7–11]. In particular, the progress in fabrication of coupled optical waveguides lattices and the development of single-photon sources has made it possible to experimentally investigate continuous-time quantum walks (CTQWs) of single and correlated photons on discrete lattices [12–14]. In these cases, the Hamiltonian of the quantum system determines the properties of the corresponding CTQW, either on a line or on a lattice [15,16]. CTQWs on a constant-degree graph can be used in search algorithms [17,18] and universal quantum computing [15,16], and the Hamiltonian is given by the corresponding adjacency matrix. This opens a door for novel applications of CTQWs in quantum information processing. Traditionally, CTQW have been confined to undirected graphs [19,20] with Hermitian adjacency matrices that give rise to unitary evolution. In this paper, we define CTQW on an arbitrary directed graph and experimentally implement it on two three-node graphs. We find that the node centrality in a directed graph is correlated with the maximum node probability resulting from the CTQW and then demonstrate PageRank.

The PageRank algorithm, introduced by Page and Brin [21], is the most prominent ranking measure using the query-independent hyperlink structure of the web. PageRank can be seen as the stationary distribution of a random walker on the web graph, which spends its time on each page in proportion to the relative importance of that page. To model this, one can define the transition matrix associated with the adjacency matrix of the directed graph. In general, the adjacency matrix of the directed graph is not Hermitian. We introduce the notion of a CTQW on a directed graph, with non-Hermitian adjacency matrices, and show that they can be simulated using a quantum simulator or a quantum circuit. For the few basic graphs that we consider, we show that the nonunitary continuous time evolution is related to the classical centrality of nodes in these graphs. Thus, CTQW on directed graphs may be used to assign the node ranking via QW-based centrality measures. We then demonstrate these ideas by simulating the time evolution on two directed three-node graphs. We realize such QWs by using linear optical circuits and single photons and experimentally demonstrate one of their applications—a page ranking algorithm. In light of the recent progress of practical applications of a noisy intermediate-scale quantum computer, such as a variational quantum eigensolver [22,23] and a full quantum eigensolver [24], our experiment reports the first successful experimental demonstration of a page ranking algorithm and provides new evidence for QWs’ applications in quantum algorithms and quantum information processing.

Searching or ranking a large database is an important, cross-disciplinary task with broad applications in everyday life. By exploiting the unique properties of quantum resources, various quantum search algorithms, such as Grover–Long algorithm [25], quantum PageRank [26], etc., have revealed an advantage with respect to the classical protocols. However, despite a lot of theoretical work demonstrating the advantages of applying QWs in search algorithms [27], the first experimental implementation (with a Grover walk) came much later [28]. Quantum search algorithms have been realized with 2 [28–32] or 3 qubits [33,34] corresponding to the database size of 4 or 8, respectively, in various physical systems. With the rapid development of quantum information science and technology, we would expect that QW-based algorithms such as quantum search and quantum PageRank can be put to test, across multiple platforms, for real application in the near future.

## 2. QUANTUM WALKS ON DIRECTED GRAPHS

A directed graph is characterized by an $N \times N$ non-Hermitian adjacency matrix $A \ne {A^\dagger}$. The time evolution $G(t) = \exp (- iAt)$ of such a system is nonunitary. The nonunitary evolution can be realized if the system possesses some symmetries, such as parity-time symmetry [35–51], time-reversal symmetry [52], or pseudo-Hermiticity [53,54]. In each case, either the Hamiltonian with a real spectrum is made self-adjoint by redefining the inner product or, more commonly, it is dilated into a Hermitian Hamiltonian [52]. Here we experimentally realize an arbitrary nonunitary evolution by using the unitary-dilation approach [55,56], i.e., we embed the nonunitary operator as a part of a larger unitary operator that is twice its size. The nonunitary time evolution of the directed graph is then obtained by restricting the output measurements to the graph. We note that this process is different from Hamiltonian dilation methods where the system is coupled to a two-level ancilla. As shown in Refs. [55,56], we can construct the $2N \times 2N$ unitary dilation of the $N \times N$, nonunitary time-evolution operator $G(t)$ as

An initial state $|{\psi _s}(0)\rangle$ on graph $A$ with $N$ nodes is embedded into a state $|\psi (0)\rangle = {({|{\psi _s}(0)\rangle ,|0\rangle})^T}$ on the graph with $2N$ nodes, and it is time evolved using the unitary operator ${U_A}(t)$:

We emphasize that the nonunitary time evolution on a directed graph via the operator $G(t)$ is mathematically straightforward. However, in practice, it cannot be realized using a Hermitian quantum system with the same number of degrees of freedom (nodes). Conversely, the unitary-dilation procedure discussed above enables the implementation of CTQW on arbitrary directed graphs using traditional quantum simulators or quantum circuits.

## 3. CONTINUOUS-TIME QUANTUM WALKS AND CENTRALITY ON DIRECTED GRAPHS

In this section, we investigate the relationship between the CTQW node probabilities $P(k,t)$ and the relative importance of each node in the directed graph, often termed its centrality or page rank. The main reason for Google being so successful lies in the page ranking algorithm developed by its founders, Larry Page and Sergey Brin [21]. Thus, it is of significant theoretical and practical interest to examine if a QW-based algorithm can be developed to analyze complex networks, typically characterized by non-Hermitian adjacency matrices, and to provide effective ranking strategies [19,57,58]. Earlier theoretical work on the centrality studies of undirected graphs [19,20] and directed graphs with parity-time (PT) symmetry [59] have demonstrated a close relationship between the maximum node probabilities obtained from a QW and the relative importance of corresponding nodes as characterized by centrality measures.

To quantify and extract the intrinsic relative importance of each node, we choose the initial state of the quantum walker as identically distributed over all $2N$ nodes, that of the system and the environment. This ensures that no bias is given towards any particular node. We evaluate the maximum system-node probabilities for CTQW on graph $A$ and compare them with the classical centrality measure that we evaluate using the *Mathematica* function PageRankCentrality for graph ${A^\dagger}$. The node probabilities $P(k,t)$ for the system nodes either oscillate or reach steady-state values, and they encode the symmetries of the underlying directed graph. Table 1 shows a comparison of the classical centrality of a graph ${A^\dagger}$ and the maximum node probability in the system graph $A$ for the directed graphs shown in Fig. 1. We note that the maximum system node probabilities ${P_{{\max}}}$ are not constrained by any sum rule, whereas the PageRank values sum to unity.

We show some examples. We start with the CTQW on graph ${A_1} = \left({\begin{array}{*{20}{c}}0&{- 1}&{- 1}\\{- 1}&0&0\\0&{- 1}&0\end{array}}\right)$. The adjacency matrix ${A_1}$ has one real and two complex-conjugate eigenvalues. We take another example: the complementary graph ${A_2} = \left({\begin{array}{*{20}{c}}0&{- 1}&{- 1}\\{- 1}&0&{- 1}\\0&0&0\end{array}}\right)$, which has two equivalent nodes 1 and 2, along with a “source” node 3.

We see from Table 1 that the node rankings obtained via CTQW on ${A_1}$ and ${A_2}$ are in good agreement with those obtained from the classical centrality measure for graphs $A_1^\dagger$ and $A_2^\dagger$ as examples. We observed higher maximum QW probability at nodes with higher influx than outflux, which reflects their network centrality.

## 4. EXPERIMENTAL IMPLEMENTATION

Universal linear optics [60,61] and the use of linear combination of unitaries [62] have been instrumental to experimental realizations of quantum photonic chips [14,63] that realize arbitrary unitaries. This approach enables the efficient implementation of an arbitrary unitary transformation on various degrees of freedoms of single photons [64,65]. Here we demonstrate these ideas by simulating CTQW on two directed, three-node graphs ${A_1}$ and ${A_2}$. We construct the $6 \times 6$ unitary operators ${U_A}(t)$ for ${A_1}$ and ${A_2}$, and we simulate the time evolution via linear optics and single photons.

Each $6 \times 6$ unitary transformation ${U_A}(t)$ can be decomposed as ${U_A}(t) = (1 \oplus {U^{\prime \prime} _4})({U^\prime _4} \oplus 1)(1 \oplus {U_4})$, where ${U_4}$, ${U^\prime _4}$, ${U^{\prime \prime} _4}$ are $4 \times 4$ unitary matrices, and $1$ is $2 \times 2$ identity matrix. Thus, ${U_A}(t)$ can be realized by applying ${U_4}$ (${U^\prime _4}$ or ${U^{\prime \prime} _4}$) on the corresponding four-dimensional subsystem with the remaining two-dimensional subsystem unchanged.

Each $4 \times 4$ matrix can be further decomposed using the cosine-sine decomposition method [20]. We use ${U_4}$ as an example, and it can be decomposed as ${U_4} = {\mathbb L}{\mathbb S}{\mathbb R}$, where

In this experiment, with three spatial modes and two polarizations of single photons, the basis states of a six-dimensional qudit are encoded as $\{|0\rangle = |u\rangle |H\rangle,\, |1\rangle = |u\rangle |V\rangle,\, |2\rangle = |m\rangle |H\rangle,\, |3\rangle = |m\rangle |V\rangle,\, |4\rangle = |l\rangle |H\rangle,\, |5\rangle = |l\rangle |V\rangle \}$, where $|u\rangle$, $|m\rangle$, and $|l\rangle$ represent the (upper, middle, and lower) spatial modes of the photons, and $|H\rangle$ and $|V\rangle$ represent the horizontal and vertical polarizations of the photons. With a polarizing beam splitter (PBS), wave plates (WPs), and two beam displacers (BDs), we can prepare an arbitrary six-dimensional qudit state. To demonstrate the page ranking algorithm, we need to prepare a symmetrically distributed initial state $|\psi (0)\rangle = \sum\nolimits_{j = 0}^5 |j\rangle /\sqrt 6$. First, after passing through a half-wave plate (${{\rm HWP}_a}$ at 17.6°), which rotates the polarization of single photons to $\sqrt {\frac{2}{3}} |H\rangle + \sqrt {\frac{1}{3}} |V\rangle$, the photons are split into two parallel paths by a BD. Second, two HWPs (${{\rm HWP}_b}$ at 90° and ${{\rm HWP}_c}$ at 22.5°) are inserted into the upper and lower modes, respectively. After going through a BD, the state of the single photons is $(|u\rangle |V\rangle + |m\rangle |V\rangle + |l\rangle |H\rangle)/\sqrt 3$. Finally, two HWPs (${{\rm HWP}_d}$ at 67.5° and ${{\rm HWP}_e}$ at 22.5°) are inserted into two upper modes and the lower modes, respectively, to flip the polarizations. Thus, the state of the single photons is prepared in $|\psi (0)\rangle$.

In order to implement a CTQW on a three-node graph [59] experimentally, we need to construct the $6 \times 6$ unitary transformation ${U_A}(t)$ and apply it on the initial states. In this basis $\{|i\rangle \}$ ($i = 0, \cdots ,5$), the $4 \times 4$ unitary transformations ${\mathbb L}$, ${\mathbb R}$, and ${\mathbb S}$ can be rewritten as

In Fig. 3(a), for the controlled two-qubit transformations ${\mathbb L}$ and ${\mathbb R}$, the spatial mode of photons serves as the control qubit and the polarization mode is the target qubit. In the middle and lower modes, the $2 \times 2$ unitary transformations $L$($R$) and ${L^\prime}$(${R^\prime}$) are applied to the polarization degrees of freedom, which can be realized by a sandwich-type set of HWPs and quarter-wave plates (QWPs), i.e., QWP-HWP-QWP.

The $4 \times 4$ unitary transformation ${\mathbb S}$ is also a controlled two-qubit operation, in which the polarizations of photons serve as the control qubit and spatial modes are the target one. Then transformation of basis

Actually, this decomposition method can be used to decompose any higher-dimensional unitary operations into series of two-dimensional unitary operations, and thus our technology can be used to realize, in principle, any dimensional unitary operations. However, it is noteworthy that the numbers of linear optical elements—BDs, used to prepare a $d$-dimensional state and to realize a $d$-dimensional unitary operation—are $d/2 - 1$ and ${2(2^{d/2}} - 2)$, respectively, where $d$ is an even positive integer. In other words, the number of optical elements grows exponentially with the dimension of the unitary operation.

In order to implement a CTQW on the two directed, three-node graphs experimentally in Fig. 4, we choose $t = \{0.2,0.4,2,3,4,5,9,15,25,35\}$ for ${U_{{A_1}}}(t)$ and $t = \{0.12,1.54,4.75,6.16,6.28\}$ for ${U_{{A_2}}}(t)$. After applying ${U_A}(t)$, the final state is measured via a two-qubit projective measurement. A PBS is used to perform the projective measurement on the photons with the basis $\{|i\rangle \}$ ($i = 0, \cdots ,5$). The photons are detected by avalanche photon diodes in coincidence with the trigger with a coincident window of 3 ns. The clicks of six detectors correspond to the probabilities of the final state projected onto the basis states. We record the clicks for 10 s, and more than 15,000 coincidence counts are detected in the overall measurement time. The probabilities distributions of the first three states $\{|0\rangle ,|1\rangle ,|2\rangle \}$ corresponding to the three nodes $k = 1,2,3$.

Figure 5 shows the experimental probability distributions of three nodes of graph ${A_1}$. Theoretical predictions are represented by curves, and the experimental results by symbols. The maximum probabilities for node 1 and 3 occur at $t = 0.2$ and are measured as ${P^{{\rm exp}}}(k = 1) = 0.291 \pm 0.005$ and ${P^{{\rm exp}}}(k = 3) = 0.234 \pm 0.005$, respectively, which agree with their theoretical predictions 0.277 and 0.239 very well. For node 2, the maximum probability happens at $t = 0.4$ with theoretical prediction 0.372 and ${P^{{\rm exp}}}(k = 2) = 0.375 \pm 0.006$ measured in our experiment.

Figure 6 shows the experimental probability distributions of three nodes of graph ${A_2}$. It also shows that the probability distributions undergo periodic oscillation with period $2\pi$ theoretically. In addition, the maximum probability for nodes 1 and 2 happens at $t = \{0.12,6.16\}$ with $P_{{\rm max}}^{{\rm th}}(k = 1,2) = 0.225$, and the corresponding experimental results are ${P^{{\rm exp}}}(k = 1,t = 0.12) = 0.228 \pm 0.005$, ${P^{{\rm exp}}}(k = 2,t = 0.12) = 0.219 \pm 0.005$, ${P^{{\rm exp}}}(k = 1,t = 6.16) = 0.221 \pm 0.005$, and ${P^{{\rm exp}}}(k = 2,t = 6.16) = 0.223 \pm 0.005$, respectively. We also find the maximum probability for node 3 at $t = 1.54$ and $t = 4.75$ with $P_{{\rm max}}^{{\rm th}}(k = 3) = 0.449$, in close agreement with the experimental measured results ${P^{{\rm exp}}}(k = 3,t = 1.54) = 0.435 \pm 0.007$ and ${P^{{\rm exp}}}(k = 3,t = 4.75) = 0.457 \pm 0.007$.

We use the norm-1 distance between the measured probabilities and their theoretical predictions $d(t) = \sum\nolimits_x |{P^{{\rm exp}}}(x) - {P^{{\rm th}}}(x)|$ to evaluate the quality of experimental demonstration. All the results $d(t)$ for different times of graphs ${A_1}$ and ${A_2}$ are all smaller than 0.083, which indicates the successful experimental demonstrations of the $6 \times 6$ unitary transformations.

As an application of CTQW on directed graphs, we compare the classical centrality measure with the maximum system-node probabilities for CTQW on graphs ${A_1}$ and ${A_2}$. Table 2 shows the comparison between the theoretical prediction and the experimental results of $P_{{\rm max}}^{{\rm exp}}$. The node rankings obtained via CTQW on graphs ${A_1}$ and ${A_2}$ are all in good agreement with those obtained from the classical centrality measure for graphs $A_1^\dagger$ and $A_2^\dagger$, which indicates that CTQW on directed graphs can be used in the page ranking algorithm.

## 5. CONCLUSIONS

In this paper, we have argued that CTQWs on directed graphs can be defined in a physically transparent manner that permits their experimental implementation. Such QW centrality would provide one of the practical measures for site ranking and network analysis. Furthermore, we experimentally realize CTQWs for directed graphs with non-Hermitian adjacency matrices by using linear optical circuits and single photons. We find that the node classical centrality in a directed graph is correlated with the maximum node probability resulting from a CTQW and then demonstrate PageRank. Our work opens up an avenue of applications of quantum information in real-life tasks.

## Funding

National Natural Science Foundation of China (11674056, U1930402); NSF (DMR-1054020); China Postdoctoral Science Foundation (2019M660016).

## Acknowledgment

YJ thanks Jeremy O’Brien and Anthony Laing for useful discussions. JBW thanks Jeremy O’Brien and Jonathan Matthews for discussions and hospitality during her visit in Bristol.

## Disclosures

The authors declare no conflicts of interest.

## REFERENCES

**1. **T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, and J. L. O’Brien, “Quantum computers,” Nature **464**, 45–53 (2010). [CrossRef]

**2. **Y. Shang, Y. Wang, M. Li, and R. Lu, “Quantum communication protocols by quantum walks with two coins,” Europhys. Lett. **124**, 60009 (2019). [CrossRef]

**3. **Y.-G. Yang, Y.-C. Zhang, G. Xu, X.-B. Chen, Y.-H. Zhou, and W.-M. Shi, “Improving the efficiency of quantum hash function by dense coding of coin operators in discrete-time quantum walk,” Sci. China-Phys. Mech. Astron. **61**, 030312 (2018). [CrossRef]

**4. **J. I. Cirac and P. Zoller, “Goals and opportunities in quantum simulation,” Nat. Phys. **8**, 264–266 (2012). [CrossRef]

**5. **M. A. Nielsen and I. L. Chuang, *Quantum Computation and Quantum Information* (Cambridge University, 2002).

**6. **P. Xue, B. C. Sanders, and D. Leibfreid, “Quantum walk on a line for a trapped ion,” Phys. Rev. Lett. **103**, 183602 (2009). [CrossRef]

**7. **K. Manouchehri and J. Wang, *Physical Implementation of Quantum Walks* (Springer, 2014).

**8. **S. D. Berry and J. B. Wang, “Two-particle quantum walks: entanglement and graph isomorphism testing,” Phys. Rev. A **83**, 042317 (2011). [CrossRef]

**9. **K. Manouchehri and J. B. Wang, “Quantum random walks without walking,” Phys. Rev. A **80**, 060304R (2009). [CrossRef]

**10. **B. L. Douglas and J. B. Wang, “Efficient quantum circuit implementation of quantum walks,” Phys. Rev. A **79**, 052335 (2009). [CrossRef]

**11. **T. Loke and J. B. Wang, “Efficient circuit implementation of quantum walks on non-degree-regular graphs,” Phys. Rev. A **86**, 042338 (2012). [CrossRef]

**12. **J. L. O’Brien, A. Furusawa, and J. Vuckovic, “Photonic quantum technologies,” Nat. Photonics **3**, 687–695 (2009). [CrossRef]

**13. **A. Peruzzo, M. Lobino, J. C. Matthews, N. Matsuda, A. Politi, K. Poulios, X.-Q. Zhou, Y. Lahini, N. Ismail, K. Wörhoff, and Y. Bromberg, “Quantum walks of correlated photons,” Science **329**, 1500–1503 (2010). [CrossRef]

**14. **X. Qiang, X. Zhou, J. Wang, C. M. Wilkes, T. Loke, S. O’Gara, L. Kling, G. D. Marshall, R. Santagati, T. C. Ralph, J. B. Wang, J. L. O’Brien, M. G. Thompson, and J. C. F. Matthews, “Large-scale silicon quantum photonics implementing arbitrary two-qubit processing,” Nat. Photonics **12**, 534–539 (2018). [CrossRef]

**15. **A. M. Childs, “Universal computation by quantum walk,” Phys. Rev. Lett. **102**, 180501 (2009). [CrossRef]

**16. **A. M. Childs, D. Gosset, and Z. Webb, “Universal computation by multiparticle quantum walk,” Science **339**, 791–794 (2013). [CrossRef]

**17. **D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, “Quantum walks on graphs,” in *33rd Annual ACM Symposium on Theory of Computing* (2001), p. 5059.

**18. **S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar, “Spatial search by quantum walk is optimal for almost all graphs,” Phys. Rev. Lett. **116**, 100501 (2016). [CrossRef]

**19. **S. D. Berry and J. B. Wang, “Quantum-walk-based search and centrality,” Phys. Rev. A **82**, 042333 (2010). [CrossRef]

**20. **J. A. Izaac, X. Zhan, Z. Bian, K. Wang, J. Li, J. B. Wang, and P. Xue, “Centrality measure based on continuous-time quantum walks and experimental realization,” Phys. Rev. A **95**, 032318 (2017). [CrossRef]

**21. **S. Brin and L. Page, *Computer Networks and ISDN Systems* (Elsevier Science, 1998), pp. 107–117.

**22. **A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, “A variational eigenvalue solver on a photonic quantum processor,” Nat. Commun. **5**, 4213 (2014). [CrossRef]

**23. **M.-H. Yung, J. Casanova, A. Mezzacapo, J. McClean, L. Lamata, A. Aspuru-Guzik, and E. Solano, “From transistor to trapped-ion computers for quantum chemistry,” Sci. Rep. **4**, 3589 (2015). [CrossRef]

**24. **S. Wei, H. Li, and G.-L. Long, “A full quantum eigensolver for quantum chemistry simulations,” Research **2020**, 1486935 (2020). [CrossRef]

**25. **G. L. Long, “Grover algorithm with zero theoretical failure rate,” Phys. Rev. A **64**, 022307 (2001). [CrossRef]

**26. **H. Tang, T.-S. He, R.-X. Shi, Y.-Y. Zhu, M. Lee, T.-Y. Wang, and X.-M. Jin, “TensorFlow solver for quantum PageRank in large-scale networks,” arXiv:2003.04930 (2020).

**27. **N. Shenvi, J. Kempe, and K. B. Whaley, “Quantum random-walk search algorithm,” Phys. Rev. A **67**, 052307 (2003). [CrossRef]

**28. **Y.-C. Jeong, C. D. Franco, H.-T. Lim, M. S. Kim, and Y.-H. Kim, “Experimental realization of a delayed-choice quantum walk,” Nat. Commun. **4**, 2471 (2013). [CrossRef]

**29. **I. L. Chuang, N. Gershenfeld, and M. Kubinec, “Experimental implementation of fast quantum searching,” Phys. Rev. Lett. **80**, 3408–3411 (1998). [CrossRef]

**30. **J. Jones, M. Mosca, and R. Hansen, “Implementation of a quantum search algorithm on a quantum computer,” Nature **393**, 344–346 (1998). [CrossRef]

**31. **S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsimons, A. Zeilinger, and P. Walther, “Demonstration of blind quantum computing,” Science **335**, 303–308 (2012). [CrossRef]

**32. **J. Zhang, S. S. Hegde, and D. Suter, “Efficient implementation of a quantum algorithm in a single nitrogen-vacancy center of diamond,” Phys. Rev. Lett. **125**, 030501 (2020). [CrossRef]

**33. **L. M. Vandersypen, M. Steffen, M. H. Sherwood, C. S. Yannoni, G. Breyta, and I. L. Chuang, “Implementation of a three-quantum-bit search algorithm,” Appl. Phys. Lett. **76**, 646–648 (2000). [CrossRef]

**34. **C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath, and C. Monroe, “Complete 3-qubit Grover search on a programmable quantum computer,” Nat. Commun. **8**, 1918 (2017). [CrossRef]

**35. **B. Peng, Ş. K. Özdemir, F. Lei, F. Monifi, M. Gianfreda, G.-L. Long, S. Fan, F. Nori, C. M. Bender, and L. Yang, “Parity–time-symmetric whispering-gallery microcavities,” Nat. Phys. **10**, 394–398 (2014). [CrossRef]

**36. **Y. N. Joglekar, C. E. Thompson, D. D. Scott, and G. Vemuri, “Optical waveguide arrays: quantum effects and PT symmetry breaking,” Eur. Phys. J. Appl. Phys. **63**, 30001 (2013). [CrossRef]

**37. **M. Serbyn and M. A. Skvortsov, “Onset of superconductivity in a voltage-biased normal-superconducting-normal microbridge,” Phys. Rev. B **87**, 020501 (2013). [CrossRef]

**38. **K. K. Wang, X. Qiu, L. Xiao, X. Zhan, Z. H. Bian, W. Yi, and P. Xue, “Simulating dynamic quantum phase transitions in photonic quantum walks,” Phys. Rev. Lett. **122**, 020501 (2019). [CrossRef]

**39. **K. K. Wang, X. Qiu, L. Xiao, X. Zhan, Z. H. Bian, B. C. Sanders, W. Yi, and P. Xue, “Observation of emergent momentum–time skyrmions in parity–time-symmetric non-unitary quench dynamics,” Nat. Commun. **10**, 2293 (2019). [CrossRef]

**40. **C. E. Ruter, K. G. Makris, R. El-Ganainy, D. N. Christodoulides, M. Segev, and D. Kip, “Observation of parity–time symmetry in optics,” Nat. Phys. **6**, 192–195 (2010). [CrossRef]

**41. **A. Regensburger, C. Bersch, M.-A. Miri, G. Onishchukov, D. N. Christodoulides, and U. Peschel, “Parity–time synthetic photonic lattices,” Nature **488**, 167–171 (2012). [CrossRef]

**42. **L. Feng, Y.-L. Xu, W. S. Fegadolli, M.-H. Lu, J. E. B. Oliveira, V. R. Almeida, Y.-F. Chen, and A. Scherer, “Experimental demonstration of a unidirectional reflectionless parity-time metamaterial at optical frequencies,” Nat. Mater. **12**, 108–113 (2013). [CrossRef]

**43. **L. Xiao, X. Zhan, Z. H. Bian, K. K. Wang, X. Zhang, X. P. Wang, J. Li, K. Mochizuki, D. Kim, N. Kawakami, W. Yi, H. Obuse, B. C. Sanders, and P. Xue, “Observation of topological edge states in parity–time-symmetric quantum walks,” Nat. Phys. **13**, 1117–1123 (2017). [CrossRef]

**44. **Y. Wu, W. Liu, J. Geng, X. Song, X. Ye, C.-K. Duan, X. Rong, and J. Du, “Observation of parity-time symmetry breaking in a single-spin system,” Science **364**, 878–880 (2019). [CrossRef]

**45. **J. Schindler, Z. Lin, J. M. Lee, H. Ramezani, F. M. Ellis, and T. Kottos, “PT-symmetric electronics,” J. Phys. A **45**, 444029 (2012). [CrossRef]

**46. **R. J. Leon-Montiel, M. A. Quiroz-Juarez, J. L. Dominguez-Juarez, R. Quintero-Torres, J. L. Aragon, A. K. Harter, and Y. N. Joglekar, “Observation of slowly decaying eigenmodes without exceptional points in Floquet dissipative synthetic circuits,” Commun. Phys. **1**, 88 (2018). [CrossRef]

**47. **J. Li, A. K. Harter, J. Liu, L. de Melo, Y. N. Joglekar, and L. Luo, “Observation of parity-time symmetry breaking transitions in a dissipative Floquet system of ultracold atoms,” Nat. Commun. **10**, 855 (2019). [CrossRef]

**48. **M. Nighaloo, M. Abbasi, Y. N. Joglekar, and K. W. Murch, “Quantum state tomography across the exceptional point in a single dissipative qubit,” Nat. Phys. **15**, 1232–1236 (2019). [CrossRef]

**49. **Y. N. Joglekar and A. Saxena, “Robust PT-symmetric chain and properties of its Hermitian counterpart,” Phys. Rev. A **83**, 050101 (2011). [CrossRef]

**50. **D. D. Scott and Y. N. Joglekar, “Degrees and signatures of broken PT-symmetry in nonuniform lattices,” Phys. Rev. A **83**, 050102 (2011). [CrossRef]

**51. **C. H. Liang, D. D. Scott, and Y. N. Joglekar, “PT restoration via increased loss and gain in the PT-symmetric Aubry-André model,” Phys. Rev. A **89**, 030102 (2014). [CrossRef]

**52. **L. Xiao, K. K. Wang, X. Zhan, Z. H. Bian, K. Kawabata, M. Ueda, W. Yi, and P. Xue, “Observation of critical phenomena in parity-time-symmetric quantum dynamics,” Phys. Rev. Lett. **123**, 230401 (2019). [CrossRef]

**53. **L. Xiao, T. S. Deng, K. K. Wang, G. Y. Zhu, Z. Wang, W. Yi, and P. Xue, “Non-Hermitian bulk–boundary correspondence in quantum dynamics,” Nat. Phys. **16**, 761–766 (2020). [CrossRef]

**54. **L. Xiao, X. Qiu, K. K. Wang, Z. H. Bian, X. Zhan, H. Obuse, B. C. Sanders, W. Yi, and P. Xue, “Higher winding number in a nonunitary photonic quantum walk,” Phys. Rev. A **98**, 063847 (2018). [CrossRef]

**55. **P. R. Halmos, “Normal dilations and extensions of operators,” Summ. Bras. Math. **2**, 125–134 (1950).

**56. **C. Sparrow, E. Martin-Lopez, N. Maraviglia, A. Neville, C. Harrold, J. Carolan, Y. N. Joglekar, T. Hashimoto, N. Matsuda, J. L. O’Brien, D. P. Tew, and A. Laing, “Simulating the vibrational quantum dynamics of molecules using photonics,” Nature **557**, 660–667 (2018). [CrossRef]

**57. **G. D. Paparo and M. A. Martin-Delgado, “Google in a quantum network,” Sci. Rep. **2**, 444 (2012). [CrossRef]

**58. **E. Sanchez-Burillo, J. Duch, J. Gomez-Gardenes, and D. Zueco, “Quantum navigation and ranking in complex networks,” Sci. Rep. **2**, 605 (2012). [CrossRef]

**59. **J. A. Izaac, J. B. Wang, P. C. Abbott, and X. S. Ma, “Quantum centrality testing on directed graphs via PT-symmetric quantum walks,” Phys. Rev. A **96**, 032305 (2017). [CrossRef]

**60. **E. Knill, R. Laflamme, and G. J. Milburn, “A scheme for efficient quantum computation with linear optics,” Nature **409**, 46–52 (2001). [CrossRef]

**61. **P. Kok, W. J. Munro, K. Nemoto, T. C. Ralph, J. P. Dowling, and G. J. Milburn, “Linear optical quantum computing with photonic bits,” Rev. Mod. Phys. **79**, 135–174 (2007). [CrossRef]

**62. **G.-L. Long, “General quantum interference principle and duality computer,” Commun. Theor. Phys. **45**, 825–844 (2006). [CrossRef]

**63. **J. Carolan, C. Harrold, C. Sparrow, E. Martin-Lopez, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Matsuda, M. Oguma, M. Itoh, G. D. Marshall, M. G. Thompson, J. C. F. Matthews, T. Hashimoto, J. L. O’Brien, and A. Laing, “Universal linear optics,” Science **349**, 711–716 (2015). [CrossRef]

**64. **P. Xue, R. Zhang, H. Qin, X. Zhan, Z. H. Bian, J. Li, and B. C. Sanders, “Experimental quantum-walk revival with a time-dependent coin,” Phys. Rev. Lett. **114**, 140502 (2015). [CrossRef]

**65. **Z. H. Bian, J. Li, H. Qin, X. Zhan, R. Zhang, B. C. Sanders, and P. Xue, “Realization of single-qubit positive-operator-valued measurement via a one-dimensional photonic quantum walk,” Phys. Rev. Lett. **114**, 203602 (2015). [CrossRef]