Supplementary_Materials.pdf

Quantum computers have long been the anchor of hope for outperforming classical computers on a number of tasks [1, 2]. Recently in bulk optics [3, 4], quantum computational advantages have been demonstrated on a classically intractable problem, i.e., boson sampling. Besides, integrated photonics also showed the potential for implementing boson sampling [5]. The standard boson sampling that constitutes multiple indistinguishable bosons undergoing coherent evolution in a Haar-random linear network can be viewed as an instance of quantum walks (QWs), while QWs define quantum dynamics of various particles on general graphs [6]. QWs become promising quantum computation primitives since problem instances can be encoded into and further solved via the evolution dynamics of QWs with the properly chosen particle property and graph structure. Many QW-based algorithms have shown quantum-enhanced performances in applications of practical interests, such as searching, analyzing, and learning complex networks [7]. QWs on designed networks can also model quantum dynamics in the fields of physics [8], chemistry [9], and biology [10], and even realize universal quantum computation [11].

To exploit the potentials of QWs, physical apparatus with multiple particles and large-scale evolution graphs are essential. Moreover, the full programmability of particle properties and graph geometry is imperative to tackle different applications. QWs have been experimentally demonstrated on various platforms, such as photons [12, 13, 14, 15], superconducting qubits [16], trapped ions [17], neutral atoms [18], and nuclear magnetic resonance systems [19]. It remains challenging to simultaneously combine all the capabilities for realizing the large-scale and full-programmable quantum walks. In 2021, we reported a preliminary silicon photonic device capable of simulating QW dynamics in a 25-dimensional Hilbert space with all parameter programmability [20]. Here, as shown in Fig.1A, we now present a full-stack photonic computing system, YH QUANTA QW2020 (银河鲲腾QW2020 in Chinese). The system can implement full-programmable QWs in a 400-dimensional Hilbert space with improved accuracy and also take complete control over QW parameters, including the particle property, initial state, graph structure, and evolution time.

Now consider the continuous-time QWs (CTQWs) of a single particle on an $N$-vertex graph $G$ with adjacency matrix $\bm{A}$. The system can be described by the Hamiltonian $H=\bm{A}$. The single-particle CTQW evolution follows

where $H$ is the Hamiltonian on graph $G$, $\ket{\psi_{ini}}$ is the initial state and $\ket{\psi(t)}$ is the evolved state at time $t$. When multiple particles get involved, the dimension of the corresponding Hilbert space can grow exponentially with the number of particles. A multiple-particle CTQW can be applied to simulate single-particle CTQW on an exponentially large graph, with the geometry of the large graph determined by the particle indistinguishability and exchange symmetry [20]. For example, the single-particle CTQW on an $N^{P}$-vertex Cartesian product graph $G^{(P)}_{D}$, of which the adjacency matrix is $\bm{A}^{(P)}_{D}=\bm{A}^{\oplus P}$, can be simulated by $P$ fully distinguishable particles evolution on graph $G$ [21]. When the particles are fully indistinguishable, the dimensions of the simulated larger graph for $P$ bosons (denoted as $G^{(P)}_{B}$) and $P$ fermions (denoted as $G^{(P)}_{F}$) are ${N+P-1\choose P}$ and ${N\choose P}$, respectively [22]. The explicit representation of the constructed large graph can be found in the supplementary materials [23]. These schemes make it possible that instead of directly implementing single-particle CTQW evolution on exponentially sized graph $G^{(P)}\in\{G^{(P)}_{D},G^{(P)}_{B},G^{(P)}_{F}\}$, we can simulate its dynamics via a multi-particle CTQW on a $N$-vertex graph $G$ with only polynomial resource cost [23].

Experimentally, following our previous design [20], we simulated two-particle CTQWs by sending each particle of the entangled two photons through identical copies of a single-particle CTQW evolution $U=\mathrm{e}^{-iHt}$. The core of the system is one of the largest-scale programmable silicon quantum photonic chips. The chip monolithically integrates two spontaneous four-wave mixing photon-pair sources and two 20-mode universal linear optical circuits with fixed inputs. By tuning the generated entangled two-photon state, particles can be controlled with covering the entire spectrum from distinguishable to fully indistinguishable and from bosonic to fermionic exchange symmetry. Each of the two linear optical circuits can be configured to implement arbitrary state preparation and CTQW evolution in a Hilbert space with up to 20 dimensions. The whole chip enables the simulations of single-particle CTQWs on $G^{(2)}$ graphs with up to 400 vertices and has full control over all QW parameters, including particle property, initial state, graph structure, and evolution time.

As shown in Fig.1B, the system is built following a hierarchical quantum computing stack [24] that matches QW-based applications to physical hardware operations. At the top levels, quantum algorithms are expected to be modeled as QWs with various particle properties and evolution graphs. At the middle level, the quantum walk interface translates algorithms to the corresponding parameters of QWs, and then compiles QW parameters into hardware operations. The device driver level interacts with the programmable photonic chip to perform configuration and output detection of the chip. At the bottom of the stack, we have a packaged photonic chip module engineering two-photon states in a 400-dimensional Hilbert space, in which the embedded photonic chip is optically, electronically, and thermally packaged. A small single-board computer mastered all these distributed subsystems. We verify the high-precision of our system with one thousand randomized entangled quantum states in a 400-dimensional Hilbert space, which are generated by applying Haar-random unitary transformations to the programmable entangled two-photon. The average fidelity between the obtained and theoretical probability distributions of the evolved quantum states reaches $94.29\pm 1.28\%$. Once assembled and calibrated, the system has been in continuous operation for over twenty months.

Before attempting to implement quantum algorithms based on QWs, it is first of profound importance to study their dynamics features. Once the underlying graphs of QWs increase to hundreds of vertices, quantum speedups could be obviously demonstrated in experiments. One of the most prominent QWs’ features is the fast hitting ability on graphs, that is, to propagate from one vertex to another remote one more efficiently than classical random walks (CRWs) and even any known classical algorithms [25]. On a hexagonal structure, quadratic speedups have been demonstrated [26]. However, the dynamics of exponentially fast hitting remain unexplored in experiments due to the need for complicated arrangements of exponentially increasing vertices. With the capabilities to access the exponentially expanded Hilbert space, our system is able to carry out the first experimental observation of the hitting dynamics on eRGTs (that are extended-RGTs generated via two-boson CTQW on RGTs) with up to 105 vertices and eCube (extended-Cubes generated via two-boson CTQW on Hypercubes) with up to 136 vertices. In Fig.2A and Fig.2B, we compared the optimal hitting distribution and efficiency of CTQWs and CRWs. Nearly two orders of magnitude of enhancement in the hitting efficiency of CTQW experiments (0.7059, 0.9582) over CRWs (0.0095, 0.0073) are demonstrated on the 10-layer eRGT and 8-layer eCube, during which processes the average of the fidelities between the experimental and theoretical probability distributions are $96.28\pm 1.86\%$ and $97.98\pm 1.06\%$, respectively. The optimal hitting occurs at a polynomial time both for CTQWs and CRWs. However, the optimal hitting efficiency of CRWs falls exponentially with layer depth, in contrast with the polynomial decrease tendency of CTQWs, verifying an exponential quantum speedup over the hitting performance by CRWs. We also demonstrated quadratically fast hitting performance on nets and grids with up to 210 vertices, which are the largest-scale experimental demonstrations of fast hitting dynamics up to now [23].

Another essential feature of QW dynamics is known as mixing [27]. Although unitary QWs hardly converge to stationary distributions as CRWs, one can capture a dynamically stabilized situation by observing the long-time average distribution of quantum walkers on the graphs. Of much significance to the heart of quantum speedups for many QW-based algorithms [28] is quantum mixing time [29], that is, the minimum time required for a QW to converge close to its average limiting distribution. However, the demands for long-time stability and intensively repeated measurements remain challenges for the experimental investigation. From the overall mixing process depicted by our system, we observed nearly quadratic speedups of CTQW mixing over CRW on eNets (Fig.2C) and eGrids (Fig.2D). Compared to CRWs, CTQWs on the 20-layer net and the 36-layer grid almost halve in the evolution time for mixing. For the mixing on the largest-scale net, the average of the fidelities between the experimental and theoretical probability distributions is $96.28\pm 1.86\%$, and the similarity between measured and theoretical limiting distribution reaches $99.76\%$. See more details in the supplementary materials [23]. As far as we know, these are the first experimental demonstrations of QW mixing dynamics.

Additionally, we implemented four QW-based applications on large-scale graphs using our system. (1) Centrality measure. Based on QWs, quantum-enhanced algorithms were proposed for ranking the vertex centrality of graphs and further used for large-scale network analysis [30]. We performed a CTQW-based centrality measure algorithm on eScale-free random networks. Fig.3A presents the experimentally obtained CTQW-based centrality results of a 55-vertex eScale-free network, which correlates well with its eigenvector centrality (similarity = 95.68%). This is the largest-scale experimental realization of CTQW-based centrality measure to date that validates the potential of the QW in large-scale network analysis. (2) Search on networks. Finding marked vertices in a graph can be solved in the framework of QWs. It has been proved that CTQWs can search on almost all graphs of size $N$ in time $\mathcal{O}(\sqrt{N})$ and thus provide quadratic speedup over classical algorithms [31]. We benchmarked the performance of a CTQW-based search algorithm [20] on 1,000 randomly eErdös-Rényi networks with sizes ranging from 15 to 210. With the experimental data statistics, we show the optimal search time starting from three vertices to find the other three marked vertices scales as $0.8026\sqrt{N}+4.06895$ (Fig.3B) and experimentally demonstrate the quadratic speedup for the first time. (3) Graph isomorphism test. Another application of QWs is to tackle the graph isomorphism problem, that is, determining whether two given graphs are isomorphic (two graphs are isomorphic if one can be obtained from the other by relabeling the vertices). To demonstrate a CTQW-based algorithm [20] on graphs with 210 vertices, we constructed the graph certificates from experimentally obtained CTQW evolution results. By comparing the total variance distance of graph certificates between graphs, their isomorphism is distinguished. As shown in Fig.3C, the experimental and theoretical results are highly consistent. For the isomorphic graph pair, the average distance of graph certificates is close to 0, while non-isomorphic graphs achieve a much larger distance. (4) Topological phase simulation. By encoding the property of particles and geometry of graphs, QWs can be used to model a wide variety of physical systems and processes. As shown in Fig.3, we demonstrated the topological invariants of two typical higher-order topological insulators, the 2D Su-Schrieffer-Hegger (SSH) model [32] and Benalcazar-Bernevig-Hughes (BBH) model [33], by probing the long-time averaged values of extended mean chiral displacement (AMCD) [34] and mean chiral quadrupole moment (AMCQM) [35] in single-particle and two-fermion CTQWs, respectively. The bulk topology of the 2D SSH model should be characterized by two topological invariants along the $x$ and $y$ dimensions. The experimental asymptotic values of AMCD in topological phases of the 2D SSH model are $(0.470\pm 0.002,0.498\pm 0.001)$, which are obviously distinct from the values in trivial phases, $(-0.046\pm 0.004,0.013\pm 0.003)$. In Fig.3, we present the results along the $y$ dimension as an example. Similarly, the experimental asymptotic values of AMCQM of the BBH model are $0.513\pm 0.002$ in topological phases and $0.014\pm 0.003$ in trivial phases. All these demonstrations of applications showcased the potential of our system for practical large-scale network analysis and the field of many-body system quantum simulations.

In conclusion, we have designed and realized a full-stack photonic quantum computing system for simulating universal large-scale QWs and their applications. It allows investigating unique QW dynamics features on large-scale graphs, where we experimentally demonstrated the exponential quantum speedup in hitting and the quadratically quantum speedup in mixing for the first time. Using the system, we also demonstrated versatile applications in high precision, from graph-theoretic applications and quantum simulations of topological phases. Our work shows that the dedicated integrated photonic system with particular QW models paves a viable path to bring quantum photonics to fruition in practical applications. With the rapid development of integrated quantum photonics [36, 37, 38], such quantum photonics-enabled computers would be accelerated to achieve practical quantum advantages.

See pages 1, of Supplementary_Materials.pdf See pages 0, of Supplementary_Materials.pdf