Berlin 2024 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

QI: Fachverband Quanteninformation

QI 9: Quantum Machine Learning and Classical Simulability

QI 9.13: Talk

Tuesday, March 19, 2024, 13:00–13:15, HFT-FT 101

The Mean King’s Problem as a learning task — •Niklas Rohling — Department of Physics, University of Konstanz

The Mean King’s Problem [1-5] is an early example of an advantage due to the availability of additional quantum resources. This original version of the problem is a single-shot measurement where Alice has to determine correctly the outcome of a measurement which was performed previously by the king’s men. The difficulty comes from the fact that the measurement basis used by the king’s men is revealed only after Alice has completed her measurement. The striking result is that Alice can find the correct answer with certainty if she is allowed to entangle the state initially with an additional quantum system. Here, we formulate the Mean King’s Problem as a learning task where several copies of the state after the king’s men’s measurement, sorted by their outcome, are available. We investigate how the number of copies required to determine the measurement outcome of the king’s men within desired error bounds ε and success probability 1−δ scales with system size when additional quantum resources are (or are not) allowed to be used. We compare to the exponential advantage of quantum-enhanced learning found recently for measurements in product bases [6].

[1] Vaidman, Aharonov, Albert, PRL 58, 1385 (1987)

[2] Aharonov, Englert, Z. Naturforsch. 56a, 16 (2001)

[3] Englert, Aharonov, Physics Letters A 84, 1 (2001)

[4] Aravind, Z. Naturforsch. 58a, 682 (2003)

[5] Durt, Int. J. Mod. Phys. B 20, 1742 (2006)

[6] Huang et al., Science 376, 1182 (2022)

Keywords: quantum-enhanced learning; quantum advantage; sample complexity; mutually unbiased bases; optimized quantum measurements