DOE OSTI · 1572865
A quantum algorithm to efficiently sample from interfering binary trees
Abstract
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. Finally, the problem can be reduced to a system of two qubits with repeated measurements, shedding light on a quantum-inspired efficient classical algorithm.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Provasoli, Davide, Nachman, Benjamin, Bauer, Christian W., de Jong, Bert. 2020-05-05. A quantum algorithm to efficiently sample from interfering binary trees. https://doi.org/10.1088/2058-9565%2Fab8359. https://engineeringpapers.com/record/osti%3A1572865/a-quantum-algorithm-to-efficiently-sample-from-interfering-binary-trees
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Engineering Papers by Indiciae: BibTeX · RIS.