Prediction-based sign placement using QA sampling

Abstract

We present a pedestrian-flow forecasting and sign-placement workflow that leverages quantum annealing (QA) not as an optimizer, but as a sampler of individual trajectories. To reconstruct latent crowd dynamics from sparse measurements, we formulate a quadratic unconstrained binary optimization (QUBO) model where the energy landscape encodes both physical validity (uniqueness) and transition preferences. By treating the annealer as a probabilistic sampler, we generate a diverse ensemble of feasible trajectories that are consistent with time-varying transition preferences derived from periodic headcounts. Aggregating these microscopic samples yields probabilistic macroscopic flow forecasts, which are then directly used to rank candidate links and guide the placement of temporary guidance signs. We evaluate this approach using simulated quantum annealing (SQA) and a physical D-Wave annealer. SQA results confirm the model’s validity, reproducing empirical congestion patterns with reasonable consistency and verifying that the QUBO formulation correctly captures crowd dynamics. In contrast, hardware QA exhibits a high rate (approximately 95%) of constraint violations. Crucially, we find that these violations occur despite a zero chain-break fraction, suggesting limits in the hardware’s effective dynamic range rather than connectivity failures. Although the repaired QA samples yielded an aggregate RMSE between observed and reconstructed proportions that is numerically close to the SQA baseline, the resulting flow structures were spatially incoherent. This near-equal RMSE conceals a qualitative breakdown. It arises because the randomized repair process statistically matches marginal densities while destroying the coherent flow structure that the QUBO’s transition preferences are designed to encode. A classical parallel-tempering sampler on the identical QUBO satisfies the same constraint essentially perfectly (violation rate \(<1\%\) ) at a slightly lower RMSE than SQA, indicating that the feasibility gap we observe is specific to the hardware rather than to the formulation. Our results indicate that simply increasing penalty strengths is insufficient due to hardware dynamic range limits; instead, a comprehensive recalibration of the penalty landscape is required.