Every Classical Sampling Circuit is a Quantum Sampling Circuit

Abstract

This note introduces "Q-marginals", which are quantum states encoding some probability distribution in a manner suitable for use in Quantum Monte Carlo Integration (QMCI), and shows that these can be prepared directly from a classical circuit sampling for the probability distribution of interest. This result is important as the quantum advantage in Monte Carlo integration is in the form of a reduction in the number of uses of a quantum state encoding the probability distribution (in QMCI) relative to the number of samples that would be required in classical MCI -- hence it only translates into a computational advantage if the number of operations required to prepare this quantum state encoding the probability distribution is comparable to the number of operations required to generate a classical sample (as the Q-marginal construction achieves).

arXiv comment3 pages, 1 figure

References in corpus (5)

• Quantum random access memory
• Quantum speedup of Monte Carlo methods
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum Monte Carlo Integration: The Full Advantage in Minimal Circuit Depth
• The Problem with Grover-Rudolph State Preparation for Quantum Monte-Carlo