A Quantum Algorithm to Efficiently Sample from Interfering Binary Trees

Understand

Quantum computers provide an opportunity to efficiently sample from probability distributions that include non-trivial interference effects between amplitudes.

• Using a simple process wherein all possible state histories can be specified by a binary tree, we construct an explicit quantum algorithm that runs in polynomial time to sample from the process once.
• The corresponding naive Markov Chain algorithm does not produce the correct probability distribution and an explicit classical calculation of the full distribution requires exponentially many operations.
• However, the problem can be reduced to a system of two qubits with repeated measurements, shedding light on a quantum-inspired efficient classical algorithm.