Quantum Measurement Selection as a Secretary Problem Variant

A Double-Threshold Algorithm for Entangled States

Abstract

Context: The secretary problem and its variants have been extensively studied in online decision-making. The Secretary Problem Variant Trading (SPVT) framework addresses scenarios where an intermediary must decide sequentially between buyers and a seller, aiming to maximize social welfare.
Objective: This paper introduces a novel application of SPVT to quantum measurement selection. We develop and analyze an algorithm that selects the optimal measurement basis for an entangled quantum state when measurement devices arrive in random order without prior knowledge of their quality.
Method: We adapt the double-threshold algorithm from SPVT to quantum information processing. Each measurement device is characterized by its Maximum Correct Outcome Probability (MCOP) relative to the true quantum state. We derive a closed-form expression for MCOP in terms of the entanglement strength and the measurement eigenvectors, provide a mathematical proof for this formula, and implement the algorithm numerically using Bell states (λ ∈ [0.1, 0.99]), seven measurement bases, and 1000 independent trials per configuration. We additionally track the fallback rate—the proportion of trials where no device satisfies the threshold conditions—to assess the genuine contribution of the double-threshold mechanism.
Results: Numerical simulations show that the algorithm achieves a 100% selection rate across all tested entanglement strengths. The empirical competitive ratio averages 1.039, well below the theoretical SPVT weak bound of 1.83683. The fallback rate averages 9.0% across configurations, confirming that the algorithm’s success is not entirely attributable to the fallback mechanism. MCOP increases linearly with entanglement strength following M ≈ 0.25 + 0.25λ.
Conclusion: This work establishes an exploratory bridge between optimal stopping theory and quantum information processing. We show that the restricted structure of quantum MCOP values—bounded domain and discrete correlation structure— explains why empirical performance exceeds worst-case SPVT bounds. Significant theoretical work remains to establish tight formal guarantees for this restricted setting