Efficiently estimating large numbers of non-commuting observables is an important subroutine of many quantum science tasks. We present the derandomized shallow shadows (DSS) algorithm for efficiently learning a large set of non-commuting observables, using shallow circuits to rotate into measurement bases. Exploiting tensor network techniques to ensure polynomial scaling of classical resources, our algorithm outputs a set of shallow measurement circuits that approximately minimizes the sample complexity of estimating a given set of Pauli strings. We numerically demonstrate systematic improvement, in comparison with state-of-the-art techniques, for energy estimation of quantum chemistry benchmarks and verification of quantum many-body systems, and we observe DSS's performance consistently improves as one allows deeper measurement circuits. These results indicate that in addition to being an efficient, low-depth, stand-alone algorithm, DSS can also benefit many larger quantum algorithms requiring estimation of multiple non-commuting observables.Efficiently estimating large numbers of non-commuting observables is an important subroutine of many quantum science tasks. We present the derandomized shallow shadows (DSS) algorithm for efficiently learning a large set of non-commuting observables, using shallow circuits to rotate into measurement bases. Exploiting tensor network techniques to ensure polynomial scaling of classical resources, our algorithm outputs a set of shallow measurement circuits that approximately minimizes the sample complexity of estimating a given set of Pauli strings. We numerically demonstrate systematic improvement, in comparison with state-of-the-art techniques, for energy estimation of quantum chemistry benchmarks and verification of quantum many-body systems, and we observe DSS's performance consistently improves as one allows deeper measurement circuits. These results indicate that in addition to being an efficient, low-depth, stand-alone algorithm, DSS can also benefit many larger quantum algorithms requiring estimation of multiple non-commuting observables.

arXiv:2412.18973Dec 25, 20240 citations

Generalizing and derandomizing Gurvits's approximation algorithm for the permanent

Scott Aaronson, Travis Hance

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an $n\times n$ matrix A. The algorithm runs in $O( n^{2}/\varepsilon^{2})$ time, and approximates $\operatorname*{Per}( A)$ to within $\pm\varepsilon\left\Vert A\right\Vert ^{n}$ additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. \ This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role. (In particular, $n\times n$ permanents arise as the transition amplitudes for $n$ identical photons.) Indeed, the existence of Gurvits's algorithm is why, in their recent work on the \textit{hardness} of quantum optics, Aaronson and Arkhipov (AA) had to talk about sampling problems rather than ordinary decision problems. In this paper, we improve Gurvits's algorithm in two ways. First, using an idea from quantum optics, we generalize the algorithm so that it yields a better approximation when the matrix A has either repeated rows or repeated columns. Translating back to quantum optics, this lets us classically estimate the probability of any outcome of an AA-type experiment -- even an outcome involving multiple photons "bunched" in the same mode -- at least as well as that probability can be estimated by the experiment itself. It also yields a general upper bound on the probabilities of "bunched" outcomes, which resolves a conjecture of Gurvits and might be of independent physical interest. Second, we use $\varepsilon$ -biased sets to derandomize Gurvits's algorithm, in the special case where the matrix A is nonnegative. More interestingly, we generalize the notion of $\varepsilon$ -biased sets to the complex numbers, construct "complex $\varepsilon$ -biased sets", then use those sets to derandomize even our generalization of Gurvits's algorithm to the case (again for nonnegative A) where some rows or columns are identical. Whether Gurvits's algorithm can be derandomized for general A remains an outstanding problem.Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an $n\times n$ matrix A. The algorithm runs in $O( n^{2}/\varepsilon^{2})$ time, and approximates $\operatorname*{Per}( A)$ to within $\pm\varepsilon\left\Vert A\right\Vert ^{n}$ additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. \ This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role. (In particular, $n\times n$ permanents arise as the transition amplitudes for $n$ identical photons.) Indeed, the existence of Gurvits's algorithm is why, in their recent work on the \textit{hardness} of quantum optics, Aaronson and Arkhipov (AA) had to talk about sampling problems rather than ordinary decision problems. In this paper, we improve Gurvits's algorithm in two ways. First, using an idea from quantum optics, we generalize the algorithm so that it yields a better approximation when the matrix A has either repeated rows or repeated columns. Translating back to quantum optics, this lets us classically estimate the probability of any outcome of an AA-type experiment -- even an outcome involving multiple photons "bunched" in the same mode -- at least as well as that probability can be estimated by the experiment itself. It also yields a general upper bound on the probabilities of "bunched" outcomes, which resolves a conjecture of Gurvits and might be of independent physical interest. Second, we use $\varepsilon$-biased sets to derandomize Gurvits's algorithm, in the special case where the matrix A is nonnegative. More interestingly, we generalize the notion of $\varepsilon$-biased sets to the complex numbers, construct "complex $\varepsilon$-biased sets", then use those sets to derandomize even our generalization of Gurvits's algorithm to the case (again for nonnegative A) where some rows or columns are identical. Whether Gurvits's algorithm can be derandomized for general A remains an outstanding problem.

Quantum Information and ComputationMay 1, 201420 citations

Quantum Algorithms for Triangle Cut Sparsification

Shan Jiang, Pan Peng

Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale, we study the problem of triangle cut sparsification, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate quantum algorithms for this problem, using triangle listing as our main technical ingredient. In particular, we present a quantum algorithm for triangle listing that, for a graph with $n$ vertices, $m$ edges, and $t$ triangles, runs in time $T_{\mathrm{q\text{-}list}} =$ $\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},$ $n^{3/2}t^{1/2})\bigr)$ , improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy-light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing $\varepsilon$ -triangle cut sparsifiers of size $\widetilde{O}(n/\varepsilon^2)$ in time $\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)$ . Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of $Ω(n/\varepsilon^2)$ on the size of any $\varepsilon$ -triangle cut sparsifiers.Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale, we study the problem of triangle cut sparsification, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate quantum algorithms for this problem, using triangle listing as our main technical ingredient. In particular, we present a quantum algorithm for triangle listing that, for a graph with $n$ vertices, $m$ edges, and $t$ triangles, runs in time $T_{\mathrm{q\text{-}list}} =$ $\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},$ $n^{3/2}t^{1/2})\bigr)$, improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy-light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing $\varepsilon$-triangle cut sparsifiers of size $\widetilde{O}(n/\varepsilon^2)$ in time $\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)$. Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of $Ω(n/\varepsilon^2)$ on the size of any $\varepsilon$-triangle cut sparsifiers.

quant-pharXiv:2606.06287Jun 5, 20260 citations

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an

n\times n

matrix A. The algorithm runs in

O( n^{2}/\varepsilon^{2})

time, and approximates

\operatorname*{Per}( A)

to within

\pm\varepsilon\left\Vert A\right\Vert ^{n}

additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. \ This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role. (In particular,

n\times n

permanents arise as the transition amplitudes for

n

identical photons.) Indeed, the existence of Gurvits's algorithm is why, in their recent work on the \textit{hardness} of quantum optics, Aaronson and Arkhipov (AA) had to talk about sampling problems rather than ordinary decision problems. In this paper, we improve Gurvits's algorithm in two ways. First, using an idea from quantum optics, we generalize the algorithm so that it yields a better approximation when the matrix A has either repeated rows or repeated columns. Translating back to quantum optics, this lets us classically estimate the probability of any outcome of an AA-type experiment -- even an outcome involving multiple photons "bunched" in the same mode -- at least as well as that probability can be estimated by the experiment itself. It also yields a general upper bound on the probabilities of "bunched" outcomes, which resolves a conjecture of Gurvits and might be of independent physical interest. Second, we use

\varepsilon

-biased sets to derandomize Gurvits's algorithm, in the special case where the matrix A is nonnegative. More interestingly, we generalize the notion of

\varepsilon

-biased sets to the complex numbers, construct "complex

\varepsilon

-biased sets", then use those sets to derandomize even our generalization of Gurvits's algorithm to the case (again for nonnegative A) where some rows or columns are identical. Whether Gurvits's algorithm can be derandomized for general A remains an outstanding problem.

n

vertices,

m

edges, and

t

triangles, runs in time

T_{\mathrm{q\text{-}list}} =

\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},

n^{3/2}t^{1/2})\bigr)

, improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy-light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing

\varepsilon

-triangle cut sparsifiers of size

\widetilde{O}(n/\varepsilon^2)

in time

\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)

. Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of

Ω(n/\varepsilon^2)

on the size of any

\varepsilon

-triangle cut sparsifiers.