Search

Quantum symmetrization is the task of transforming a non-strictly increasing list of $n$ integers into an equal superposition of all permutations of the list (or more generally, performing this operation coherently on a superposition of such lists). This task plays a key role in initial state preparation for first-quantized simulations. A weaker version of symmetrization in which the input list is \emph{strictly} increasing has been extensively studied due to its application to fermionic systems, but the general symmetrization problem with repetitions in the input list has not been solved previously. We present the first quantum algorithm for the general symmetrization problem. Our algorithm, based on (quantum) sorting networks, uses $O(\log n)$ depth and $O(n\log m)$ ancilla qubits where $m$ is the greatest possible value of the list, enabling efficient simulation of bosonic quantum systems in first quantization. Furthermore, our algorithm can prepare (superpositions of) Dicke states of any Hamming weight in $O(\log n)$ depth using $O(n\log n)$ ancilla qubits. We also propose an $O(\log^2 n)$-depth quantum algorithm to transform second-quantized states to first-quantized states. Using this algorithm, QFT-based quantum telescope arrays can image brighter photon sources, extending quantum interferometric imaging systems to a new regime., Comment: 22 pages, 7 figures

Modeling and simulating the protein folding process overall remains a grand challenge in computational biology. We systematically investigate end-to-end quantum algorithms for simulating various protein dynamics with effects, such as mechanical forces or stochastic noises. We offer efficient quantum simulation algorithms to produce quantum encoding of the final states, history states, or density matrices of inhomogeneous or stochastic harmonic oscillator models. For the read-in setting, we design (i) efficient quantum algorithms for initial state preparation, utilizing counter-based random number generator and rejection sampling, and (ii) depth-efficient approaches for molecular structure loading. Both are particularly important in handling large protein molecules. For the read-out setting, our algorithms estimate various classical observables, such as energy, low vibration modes, density of states, correlation of displacement, and optimal control of molecular dynamics. We also show classical numerical experiments focused on estimating the density of states and applying the optimal control to facilitate conformation changes to verify our arguments on potential quantum speedups. Overall, our study demonstrates that the quantum simulation of protein dynamics can be a solid end-to-end application in the era of early or fully fault-tolerant quantum computing., Comment: 61 pages, 10 figures

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(\lambda^2)$-time classical computation, and the prover need only prepare $O(1)$ samples of a history state and perform $O(\lambda^2)$ single-qubit measurements, for a security parameter $\lambda$. We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations., Comment: 20 pages, 6 figures

A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify the quantum advantage of an untrusted prover. That is, a quantum prover can correctly answer the verifier's challenges and be accepted, while any polynomial-time classical prover will be rejected with high probability, based on plausible computational assumptions. To answer the verifier's challenges, existing proofs of quantumness typically require the quantum prover to perform a combination of polynomial-size quantum circuits and measurements. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits (and measurements) together with log-depth classical computation. Our first construction is a generic compiler that allows us to translate all existing proofs of quantumness into constant quantum depth versions. Our second construction is based around the learning with rounding problem, and yields circuits with shorter depth and requiring fewer qubits than the generic construction. In addition, the second construction also has some robustness against noise., Comment: 49 pages, 8 figures. Published in Quantum

In this paper we report on an experimental test of Bertrand's question on the probability to find a random chord drawn inside a unit-radius circle with length greater than $\sqrt{3}$. In an experiment performed by tossing straws onto a circle, we confirm theoretical predictions that the answer depends on the ratio of the circle diameter, $2R$, to the straw length, $L$, and that the special case corresponding to Laplace's principle of indifference is only obtained in the experimentally unattainable limit of infinite straw length, $\tilde{d}=2R/L\rightarrow 0$. In addition, we observe a systematic discrepancy in the limit, $\tilde{d}=2R/L\rightarrow 1$, where a large number of events are rejected. We conclude that the experimental test of Bertrand's paradox provides a good illustration of the Duhem-Quine problem---that hypothesis testing is always conditional on a bundle of real auxiliary assumptions., Comment: 5 pages, 6 figures