



01355nas a2200181   4500008004100000245008400041210006900125260001400194520077500208100001800983700002301001700002401024700001601048700002401064700002501088700002301113856003701136       2024                        eng d00aEfficiently verifiable quantum advantage on near-term analog quantum simulators0 aEfficiently verifiable quantum advantage on nearterm analog quan  c3/13/20243 a<p>Existing schemes for demonstrating quantum computational advantage are subject to various practical restrictions, including the hardness of verification and challenges in experimental implementation. Meanwhile, analog quantum simulators have been realized in many experiments to study novel physics. In this work, we propose a quantum advantage protocol based on single-step Feynman-Kitaev verification of an analog quantum simulation, in which the verifier need only run an O(λ2)-time classical computation, and the prover need only prepare O(1) samples of a history state and perform O(λ2) single-qubit measurements, for a security parameter λ. We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations.</p>1 aLiu, Zhenning1 aDevulapalli, Dhruv1 aHangleiter, Dominik1 aLiu, Yi-Kai1 aKollár, Alicia, J.1 aGorshkov, Alexey, V.1 aChilds, Andrew, M.  uhttps://arxiv.org/abs/2403.0819501951nas a2200217   4500008004100000245008300041210006900124260001500193490000600208520129200214100002001506700002301526700001701549700002201566700002401588700002301612700001301635700002301648700002501671856003701696       2022                        eng d00aImplementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions0 aImplementing a Fast Unbounded Quantum Fanout Gate Using PowerLaw  c10/27/20220 v43 a<p>The standard circuit model for quantum computation presumes the ability to directly perform gates between arbitrary pairs of qubits, which is unlikely to be practical for large-scale experiments. Power-law interactions with strength decaying as 1/rα in the distance r provide an experimentally realizable resource for information processing, whilst still retaining long-range connectivity. We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets. Our implementation allows the quantum Fourier transform (QFT) and Shor&#39;s algorithm to be performed on a D-dimensional lattice in time logarithmic in the number of qubits for interactions with α&le;D. As a corollary, we show that power-law systems with α&le;D are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable. Complementarily, we develop a new technique to give a general lower bound, linear in the size of the system, on the time required to implement the QFT and the fanout gate in systems that are constrained by a linear light cone. This allows us to prove an asymptotically tighter lower bound for long-range systems than is possible with previously available techniques.&nbsp;</p>1 aGuo, Andrew, Y.1 aDeshpande, Abhinav1 aChu, Su-Kuan1 aEldredge, Zachary1 aBienias, Przemyslaw1 aDevulapalli, Dhruv1 aSu, Yuan1 aChilds, Andrew, M.1 aGorshkov, Alexey, V.  uhttps://arxiv.org/abs/2007.00662