<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>The power of quantum circuits in sampling</title></titleStmt>
			<publicationStmt>
				<publisher>The Theory of Quantum Computation, Communication and Cryptography (TQC)</publisher>
				<date>08/31/2026</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10677372</idno>
					<idno type="doi"></idno>
					
					<author>Guy Blanc</author><author>Caleb Koch</author><author>Jane Lange</author><author>Carmen Strassle</author><author>Li-Yang Tan</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[We give new evidence that quantum circuits are substantially more powerful than classical circuits. We show, relative to a random oracle, that polynomial-size quantum circuits can sample distributions that subexponential-size classical circuits cannot approximate even to TV distance $1-o(1)$. Prior work of Aaronson and Arkhipov (2011) showed such a separation for the case of exact sampling (i.e.~TV distance $0$), but separations for approximate sampling were only known for uniform algorithms. A key ingredient in our proof is a new hardness amplification lemma for the classical query complexity of the Yamakawa--Zhandry (2022) search problem. We show that the probability that any family of query algorithms collectively finds $k$ distinct solutions decays exponentially in $k$.]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body><div/></body></text>
</TEI>
