Research ArticlePHYSICS

Implementing graph-theoretic quantum algorithms on a silicon photonic quantum walk processor

See allHide authors and affiliations

Science Advances  26 Feb 2021:
Vol. 7, no. 9, eabb8375
DOI: 10.1126/sciadv.abb8375
  • Fig. 1 Schematic of the multiparticle simulation scheme used, the photonic device, and experimental setup.

    (A) Left: Quantum interference of P particles launched into a network implementing unitary process U leads to quantum correlated detection events at the output. Right: An entanglement-based approach for simulating quantum interference by sharing P-particle entanglement across P copies of U. The simulated particle exchange symmetry and indistinguishability can be configured by controlling the symmetry of the entanglement state. (B) Schematic of the device with the external setup. EDFA, erbium-doped fiber amplifier; DAC, digital-to-analog converter; PC, polarization controller; OS, optical switch; SNSPD, superconducting nanowire single-photon detector; DWDM, dense wavelength division multiplexing; CC, counting logic. (C) The device includes two functional parts: (i) generating spatial-entangled photons and (ii) implementing universal five-dimensional unitary process (with fixed inputs) (see Materials and Methods and section S3 for details of the device and setup).

  • Fig. 2 Experimental simulation of quantum walks using correlated particles.

    (A) Example of quantum interference of two particles evolving in a CTQW on a four-vertex circle graph at the evolution time of π8, with different ϕ({0,π4,π2,3π4,π}) and γ({0,12,22,32,1}). For each case, Γr,qϕ,γ (refer to Eq. 1) is measured. The average fidelity between experimental and theoretical results is 98.11 ± 1.89%. (B and C) Experimental simulated probability distributions of a single-particle walk on a 6-vertex graph (B) via two-fermion CTQW and a 10-vertex graph (C) via two-boson CTQW. Both walks start from the vertex 1. The obtained average classical fidelities between experimental and theoretical distributions are 96.96 ± 0.03% and 97.33 ± 0.03%, respectively. All error bars represent the SD estimates from Poissonian statistics (see sections S4 and S5 for details).

  • Fig. 3 Experimental demonstration of quantum walk–based search.

    (A to C) Examples of graphs tested for search. Respectively, 5-vertex complete graph K5, constructed 6-vertex graph [C4(F)] via two-fermion CTQW on 4-vertex circle and 15-vertex graph [K5(B)] via two-boson CTQW on K5. (D to H) Experimental probability distributions of finding the marked vertices during the search. The marked vertices w, initial state ∣ψini⟩, and average fidelity F between experimental and theoretical distributions are listed for each case. (D) w={1} in K5, ∣ψini⟩ = ∣s⟩, F = 99.72 ± 0.01%. (E) w={2} in K5, ∣ψini⟩ = ∣ 1⟩, F = 99.35 ± 0.01%. (F) w={3,4} in K5, ψini=12(1+2), F = 99.64 ± 0.01%. Red (blue) bar chart depicts the probability to find vertex 3 (4). (G) w={1,3} in C4(F), ∣ψini⟩ = ∣ 5⟩, F = 96.43 ± 0.03%. Red (blue) bar chart depicts the probability to find vertex 1 (3). (H) w={1,6} in K5(B), ∣ψini⟩ = ∣2⟩, F = 94.95 ± 0.06%. Red (blue) bar chart depicts the probability to find 1 (6).

  • Fig. 4 Experimental demonstration of quantum walk–based GI algorithm.

    (A) Proposed CTQW-based GI algorithm. (B) Groups of SRGs numerically tested. All graphs in each group were compared pairwise. (n, d, λ, μ) defines a group of SRGs, representing the numbers of vertices, degree, and common neighbors between all adjacent and nonadjacent vertex pairs. (C) Examples of applying the GI algorithm to graph pairs. The experimentally obtained fidelities between certificates of two graphs are presented, with their theoretical value overlaid. Blue bars indicate isomorphic pairs, while red bars indicate nonisomorphic pairs. The tested 30 graph pairs range from 4- to 10-vertex. (D) Example of the similarity measure through graph certificates for comparing a five-vertex graph (embedded) with one weight edge and the original unweighted graph. With the weight p changing from 0.99 to 0.19, the experimentally obtained fidelity curves show obvious distinctions. (E and F) Examples of graphs tested on the device, respectively, pair 8 (isomorphic) and pair 20 (not isomorphic) (see section S7 for additional results).

Supplementary Materials

  • Supplementary Materials

    Implementing graph-theoretic quantum algorithms on a silicon photonic quantum walk processor

    Xiaogang Qiang, Yizhi Wang, Shichuan Xue, Renyou Ge, Lifeng Chen, Yingwen Liu, Anqi Huang, Xiang Fu, Ping Xu, Teng Yi, Fufang Xu, Mingtang Deng, Jingbo B. Wang, Jasmin D. A. Meinecke, Jonathan C. F. Matthews, Xinlun Cai, Xuejun Yang, Junjie Wu

    Download Supplement

    This PDF file includes:

    • Sections S1 to S7
    • Figs. S1 to S14
    • Tables S1 to S8
    • References

    Files in this Data Supplement:

Stay Connected to Science Advances

Navigate This Article