Source-linked AI summary
Experimentally finding dense subgraphs using a time-bin encoded Gaussian boson sampling device
S. Sempere-Llagostera, R. B. Patel, I. A. Walmsley, W. S. Kolthammer
TL;DR
GBS has been proposed for applications such as graph features, while implementing and scaling optical interferometers presents practical challenges. This paper implements GBS with a time-bin interferometer and uses its samples to search for dense subgraphs. The experiments show enhanced search over uniform random sampling, while numerical work identifies a squeezing–loss trade-off affecting algorithm speed.
Problem
Scaling optical interferometers while maintaining low loss and reconfigurability remains a technical challenge for GBS.
Source: §I · p. 1Method
The authors implement time-bin GBS and use device samples in a dense-subgraph search, examining circuit imperfections numerically.
Source: §IV · p. 6, §VI · p. 9Results
Experimental GBS samples enhance dense-subgraph search over uniform random sampling techniques.
Source: §IV · p. 6, §VI · p. 9Takeaways & Limitations
Measurements from a realistic GBS device can enhance dense-subgraph search over uniform random sampling techniques.
Source: §VI · p. 9Detector reset time of 60 ns exceeds the 12.5 ns time-bin spacing, making spatially multiplexed detection necessary to resolve consecutive-bin detections and affecting output detection probability.
Source: §III · p. 5
Abstract
from arXiv · showhide
Gaussian Boson Sampling (GBS) is a quantum computing concept based on drawing samples from a multimode nonclassical Gaussian state using photon-number resolving detectors. It was initially posed as a near-term approach aiming to achieve quantum advantage, but several applications have been proposed ever since, such as the calculation of graph features or molecular vibronic spectra, among others. For the first time, we use a time-bin encoded interferometer to implement GBS experimentally and extract samples to enhance the search for dense subgraphs in a graph. Our results indicate an improvement over classical methods for subgraphs of sizes three and four in a graph containing ten nodes. In addition, we numerically explore the role of imperfections in the optical circuit and on the performance of the algorithm.
I. INTRODUCTION
GBS offers a route to sampling-based quantum applications, but demonstrating practical applications and scaling optical interferometers remain challenges. This work implements GBS in a time-bin interferometer and uses it to search experimentally for dense subgraphs.
I. INTRODUCTION
- GBS has applications including molecular vibronic spectra and graph features, but a practical application had not yet been demonstrated in the cited work.The classical simulation involves computing the hafnian, a #P-hard function.Source: §I · p. 1
- Scaling optical interferometers to many modes while maintaining low loss and reconfigurability is a technical challenge for GBS.Source: §I · p. 1
- The authors implement a 20-mode time-bin GBS interferometer and demonstrate enhanced dense-subgraph search for size-three and size-four subgraphs in a ten-node graph.They describe this as the first experimental time-bin implementation of GBS and the first GBS application to improve dense-subgraph search.Source: §I · p. 1
A. Gaussian boson sampling
GBS transforms multimode Gaussian inputs and samples photon-number patterns at the output. The pattern probabilities are expressed using hafnians, with a simpler form for pure, undisplaced states.
A. Gaussian boson sampling
- For an m-mode Gaussian input transformed by a linear-optical interferometer, the output is described by covariance matrix Σ and displacement vector α, and zero-displacement pattern probabilities use a hafnian.The output pattern is n = (n1, n2, …, nm).Source: A. Gaussian boson sampling · p. 2
- The submatrix A_n is formed by selecting rows and columns according to each mode's photon count, so its size grows with the total detected photons N.The matrix A is derived from the covariance matrix; the hafnian sums over perfect-matching permutations.Source: A. Gaussian boson sampling · p. 2
- For a pure Gaussian state with zero displacement, A reduces to B ⊕ B*, and the relevant B_n is N × N, requiring even N.With no loss, squeezed-vacuum photons occur in pairs, so an odd total detection is not possible.Source: A. Gaussian boson sampling · p. 2
B. Time-bin interferometer
The time-bin architecture uses pulsed temporal modes and storage and processing loops to implement interferometer operations. Its design supports scaling and universality, while detector reset time can affect output statistics.
B. Time-bin interferometer
- A single source generates pulses whose separation defines the time-bin modes; increasing the problem size requires sending more pulses through the interferometer.This avoids requiring many sources or demultiplexing techniques.Source: B. Time-bin interferometer · p. 2
- The snowman architecture uses a storage loop to retain modes and a processing loop to interfere consecutive modes, with loop coupling set by a variable beam splitter.The storage loop must accommodate all m modes, with τ_s ≥ mτ_p.Source: B. Time-bin interferometer · pp. 2–3
- A series of m − 1 storage-loop round trips implements the Reck decomposition, making the snowman structure universal for linear optics.Limited beam-splitting values can still achieve universality, but require additional round trips and corresponding optical loss.Source: B. Time-bin interferometer · p. 3
- Temporal encoding can reduce detection to one detector, but a reset time longer than the time-bin spacing can skew output statistics.The figure contrasts spatial-mode detection with the time-bin architecture's single output detector.Source: B. Time-bin interferometer · p. 3, Figure 2 · p. 3
C. Finding dense subgraphs using a GBS device
The section connects GBS outcome probabilities to graph connectivity and describes a procedure for using GBS samples to search for dense subgraphs. Loss changes the sampled distribution in GBS, unlike uniform loss in standard boson sampling under photon-number postselection.
C. Finding dense subgraphs using a GBS device
- For an undirected graph, the symmetric adjacency matrix records edge weights, and the target subgraph density is defined from its edges and node count.The density of an unweighted graph ranges from 0 for an unconnected graph to 1 for a complete graph.Source: C. Finding dense subgraphs using a GBS… · p. 3
- The hafnian links GBS outcome probabilities to perfect matchings, which are related to graph density and make samples useful for searching dense subgraphs.The proposed strategy is reported to enhance search over uniform random searches and can also seed algorithms such as simulated annealing.Source: C. Finding dense subgraphs using a GBS… · pp. 3–4
- The GBS search recipe decomposes the target matrix into an interferometer unitary and squeezing parameters, compiles the unitary, then rescales squeezing for the desired coincidence size.The rescaling can maximize the probability of an n-fold coincidence without changing its relative probability distribution.Source: C. Finding dense subgraphs using a GBS… · p. 4
- Loss makes the GBS output state mixed and changes its sampling distribution, so loss can affect dense-subgraph search rather than only detection rates.The section contrasts this with standard boson sampling, where uniform loss can be neglected by post-selecting the input photon number.Source: C. Finding dense subgraphs using a GBS… · p. 4
III. EXPERIMENT
The experiment generates squeezed-vacuum inputs and sends time-bin modes through a single-loop interferometer, with pulse picking and spatially multiplexed photon detection. The implementation measures the source and accounts for optical loss and detector deadtime.
IV. EXPERIMENT
- The source uses SPDC and a fibre beam splitter to produce approximate single-mode squeezed-vacuum inputs, with measured HOM visibility of 95.3(2)%.The output-state purity is reported as 98%, and the squeezing values used are λ = {0.22, 0.31, 0.43}.Source: §III · pp. 4–5
- The pulse picker schedules ten vacuum pulses, ten occupied pulses, then ten vacuum pulses, restricting the experiment to an effective 5% duty cycle.The selected final 20 time-bins span 250 ns.Source: §III · pp. 4–5
- Fibre coupling is 40%, with estimated mode mismatch of 60–70%; the variable coupler and optical delay line have throughputs of 90% and 80%.Detection efficiency is reported as 80% on average.Source: §III · p. 5
- The single-loop interferometer applies beam-splitting operations between consecutive time-bins, with a transfer matrix that is upper-diagonal and adjustable through the variable coupler.The loop phase can be actively controlled with a piezoelectric actuator; setting it to zero makes the modeled unitary and A matrix real-valued.Source: §III · p. 5, Figure 4 · p. 5
- The output-state model shows a non-pure Gaussian state, and detector reset time exceeds time-bin spacing, motivating spatial multiplexing across eight detectors.The reset time is 60 ns, compared with 12.5 ns between bins; the authors say the high detector count allows them to neglect the resulting effect.Source: Figure 4 · p. 5, §III · p. 5
IV. RESULTS
The results section first models measured photon statistics, then reports enhanced dense-subgraph search using experimental samples compared with uniform random samples.
IV. RESULTS
- Experimental-device samples enhance dense-subgraph search compared with uniform random samples.The results section first analyzes measured photon statistics using a theoretical model of the experiment.Source: §IV · p. 6
- The reported search comparison uses samples produced by the experimental device and uniform random samples as the baseline.The passage reports the direction of the comparison but gives no numerical improvement.Source: §IV · p. 6
- Measured photon statistics are analyzed using a theoretical model before the device samples are used in the search comparison.Source: §IV · p. 6
A. GBS output statistics
The optical model uses independently measured or manufacturer-provided losses and assumes perfect SMSV inputs. At λ = 0.31, modeled and experimental twofold and threefold distributions agree closely.
A. GBS output statistics
- The model uses losses measured independently or supplied by the manufacturer and assumes perfect SMSV input states.Source: A. GBS output statistics · p. 6
- Total variation distance ranges from 0 for identical distributions to 1 for completely non-overlapping distributions.Source: A. GBS output statistics · p. 6
- At λ = 0.31, model-to-experiment total variation distances are 0.0758(3) for twofold and 0.081(1) for threefold coincidences.The distributions show good agreement, and the model displays the periodic pattern characteristic of the single-loop transformation.Source: A. GBS output statistics · p. 6
B. Finding dense subgraphs
The experiment searches a fully positive ten-node subgraph using nondegenerate GBS samples and a classical random-search procedure. GBS-enhanced sampling outperforms uniform sampling for three- and four-node subgraphs, including with experimental samples despite optical loss.
B. Finding dense subgraphs
- The search targets the fully positive subgraph on nodes 1–10 and keeps only nondegenerate k-fold detections.Postselection leaves 107, 312, and 1802 nondegenerate fourfold samples for λ = 0.22, 0.31, and 0.43, respectively.Source: B. Finding dense subgraphs · p. 6
- The random-search procedure draws k-node samples, selects the densest, and repeats the search 400 times per sample count to average out statistical fluctuations.Source: B. Finding dense subgraphs · p. 6
- GBS-enhanced protocols outperform uniform sampling for three- and four-node subgraph searches, with the improvement more prominent for four nodes.The comparison plots mean density against the number of samples drawn.Source: B. Finding dense subgraphs · p. 6
- The search comparison reports samples needed to reach a mean density of 95% and mean density achieved with 50 samples.Table I summarizes performance for different sources of random-search seeds.Source: B. Finding dense subgraphs · p. 7, Table I · p. 7
- Despite significant optical loss, experimental samples still notably surpass uniform sampling, while loss-free ideal samples perform best.For threefold detections, the ideal curve uses the fourfold distribution with one detection removed at random.Source: B. Finding dense subgraphs · p. 7
V. LOSS AND SQUEEZING TRADE-OFF
This section models uniform channel loss in a 26-node graph search and examines how loss and squeezing affect GBS sampling and dense-subgraph performance. Higher squeezing increases loss sensitivity, creating a trade-off between sampling speed and search performance.
V. LOSS AND SQUEEZING TRADE-OFF
- The analysis isolates uniform channel loss; deviations from the expected unitary and mode-dependent losses are left for future work.The authors note that error mitigation may be challenging for larger systems.Source: §V · pp. 7–8
- The simulation constructs a graph, encodes it in a GBS model, applies identical loss to each mode, then searches using samples from that model.The graph combines a small, high-edge-probability Erdős-Rényi graph and a larger, low-edge-probability one, joined at random; squeezing is rescaled to vary output mean photon number.Source: §V · p. 7
- The model studies a 26-node graph formed by joining a 6-node graph with edge probability 0.875 to a 20-node graph with edge probability 0.3.The random search is repeated for 1000 iterations to estimate mean performance.Source: §V · p. 8
- Increasing loss drives the conditioned output distribution farther from the lossless case, particularly at high squeezing; the deviation vanishes in the low-squeezing limit.The section measures deviation with total variation distance (TVD) and relates it to the probability of generating more photons than are detected.Source: §V · p. 8, Figure 7 · p. 8
- At high squeezing, input loss slows attainment of 75% mean density, while GBS still outperforms uniform sampling.At small squeezing, search speed remains unaffected by loss; the comparison uses the number of samples and experimental runs needed to reach the target density.Source: §V · p. 8, Figure 7 · p. 8
VI. CONCLUSIONS
The paper concludes that realistic time-bin GBS measurements can improve dense-subgraph search over uniform sampling, while loss and squeezing affect performance. It also reports pulse-picker and source-characterization details in the appendices.
VI. CONCLUSIONS
- GBS measurements enhance dense-subgraph search over uniform random sampling, with outcome probabilities dependent on subgraph density.The demonstration uses a time-bin implementation with one SMSV source and considers up to four-photon detection events over twenty modes.Source: §VI · p. 9
- Higher squeezing degrades search performance; numerical results link this to increased TVD under loss and a trade-off between squeezing and algorithm speed at high input loss.The numerical trend agrees with the experimental observations.Source: §VI · p. 9
- Time-bin GBS is presented as a first experimental demonstration and a route toward quantum advantage in a relevant application, while further study of imperfections is needed.The authors identify scaling this application and considering imperfections in near-term GBS applications as next steps.Source: §VI · p. 9
Appendix A: Pulse picker
- The pulse picker uses a double-pass arrangement and achieves an observed extinction ratio of 1 : 10^5, with 70% overall transmission.Time tags are gated to the [0, 250] ns region to reduce analysis time.Source: Appendix A · p. 9
Appendix B: Source characterization
- Source characterization reports an effective mode number of 1.02 and Hong-Ou-Mandel visibility of 95.3(2)%.The visibility is defined as (Cmax − Cmin)/Cmax.Source: Appendix B · p. 9
Appendix C: Phase locking
The appendix describes tuning the interferometer loop phase and compares coincidence counts for locked and freely running phase conditions.
Appendix C: Phase locking
- The loop round-trip phase is adjusted by piezoelectric control of a mirror position.The piezoelectric stack has a no-load maximum displacement of 12 μm.Source: Appendix C · p. 9
- The phase-locking characterization compares twofold coincidences after the interferometer for freely running and locked loop phase.The figure distinguishes the freely running condition in orange from the locked condition in blue.Source: Figure 8 · p. 10
- The coincidence histogram's black line indicates fluctuations due to Poissonian statistics.Source: Figure 8 · p. 10