arXiv:2206.15405 · Quantum

Multivariate trace estimation in constant quantum depth

Yihui Quek, Eneet Kaur, Mark M. Wilde

Published Jan 10, 2024• 33 citations

Abstract

There is a folkloric belief that a depth- Θ ( m ) quantum circuit is needed to estimate the trace of the product of m density matrices (i.e., a multivariate trace), a subroutine crucial to applications in condensed matter and quantum information science. We prove that this belief is overly conservative by constructing a constant quantum-depth circuit for the task, inspired by the method of Shor error correction. Furthermore, our circuit demands only local gates in a two dimensional circuit – we show how to implement it in a highly parallelized way on an architecture similar to that of Google's S y c a m o r e processor. With these features, our algorithm brings the central task of multivariate trace estimation closer to the capabilities of near-term quantum processors. We instantiate the latter application with a theorem on estimating nonlinear functions of quantum states with "well-behaved" polynomial approximations.

DOI: 10.22331/q-2024-01-10-1220

Related papers

Unified multivariate trace estimation and quantum error mitigation

Jin‐Min Liang, Qiao-Qiao Lv, Zhi‐Xi Wang +1 more

arXiv:2301.12358Physical Review AJan 10, 20239 citations

Constant-depth global shadow estimation

Qingyue Zhang, Zhou You, Dayue Qin +3 more

quant-pharXiv:2609.10408Sep 10, 20260 citations

Multivariate trace estimation using quantum state space linear algebra

Liron Mor-Yosef, Shashanka Ubaru, Lior Horesh C +1 more

arXiv:2405.01098May 2, 20240 citations

Multivariate Trace Estimation Using Quantum State Space Linear Algebra

Liron Mor-Yosef, Shashanka Ubaru, Lior Horesh C +1 more

SIAM Journal on Matrix Analysis and ApplicationsJan 10, 20252 citations

Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits

Matthew Coudron, Michael J. Gullans, Jon Nelson +2 more

quant-pharXiv:2610.02146Oct 2, 20260 citations

Short-depth circuits for efficient expectation-value estimation

Alessandro Roggero, Alessandro Baroni

arXiv:1905.08383Physical Review AFeb 24, 202018 citations

arXiv:2206.15405 · Quantum

Multivariate trace estimation in constant quantum depth

Yihui Quek, Eneet Kaur, Mark M. Wilde

Published Jan 10, 2024• 33 citations

arXiv HTML PDF

Abstract

DOI: 10.22331/q-2024-01-10-1220

Related papers

Unified multivariate trace estimation and quantum error mitigation

Jin‐Min Liang, Qiao-Qiao Lv, Zhi‐Xi Wang +1 more

Calculating the trace of the product of $m\phantom{\rule{4pt}{0ex}}n$ -qubit density matrices (multivariate trace) is a crucial subroutine in quantum error mitigation and information measure estimation. We propose a unified multivariate trace estimation (UMT) which conceptually unifies the previous qubit-optimal and depth-optimal approaches with tunable quantum circuit depth and number of qubits. The constructed circuits have $\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ or $n\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ depth corresponding to $(s+m)n$ or $s+mn$ qubits for $s\ensuremath{\in}{1,\ensuremath{\cdots},\ensuremath{\lfloor}m/2\ensuremath{\rfloor}}$, respectively. Such flexible circuit structures enable people to choose suitable circuits for different hardware devices. We apply UMT to virtual distillation to achieve exponential error suppression and design a family of concrete circuits to calculate the trace of the product of eight and nine $n$ -qubit density matrices. A numerical example shows that the additional circuits still mitigate the noise expectation value under the global depolarizing channel.Calculating the trace of the product of $m\phantom{\rule{4pt}{0ex}}n$-qubit density matrices (multivariate trace) is a crucial subroutine in quantum error mitigation and information measure estimation. We propose a unified multivariate trace estimation (UMT) which conceptually unifies the previous qubit-optimal and depth-optimal approaches with tunable quantum circuit depth and number of qubits. The constructed circuits have $\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ or $n\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ depth corresponding to $(s+m)n$ or $s+mn$ qubits for $s\ensuremath{\in}{1,\ensuremath{\cdots},\ensuremath{\lfloor}m/2\ensuremath{\rfloor}}$, respectively. Such flexible circuit structures enable people to choose suitable circuits for different hardware devices. We apply UMT to virtual distillation to achieve exponential error suppression and design a family of concrete circuits to calculate the trace of the product of eight and nine $n$-qubit density matrices. A numerical example shows that the additional circuits still mitigate the noise expectation value under the global depolarizing channel.

arXiv:2301.12358Physical Review AJan 10, 20239 citations

Constant-depth global shadow estimation

Qingyue Zhang, Zhou You, Dayue Qin +3 more

Reliable and scalable readout strategies are essential for quantum technologies. As quantum processors grow, extracting useful information must remain feasible without measurement circuits becoming a dominant bottleneck. Randomized measurements and classical shadows provide a powerful route, but global estimation is conventionally associated with highly random ensembles that require increasing circuit depth and hence substantial experimental overhead. In this work, we show that substantially less randomness suffices when the readout is meaningfully adapted to the quantities being estimated. We introduce shallow phase shadows, based on a sparse Clifford-IQP ensemble, and prove efficient global estimation of stabilizer-state fidelities despite the ensemble not forming an approximate relative-error design. On all-to-all architectures, the protocol admits a constant-depth implementation using mid-circuit measurements and classical feedforward, or logarithmic depth without auxiliary systems. The protocol requires only controlled-phase entangling gates and offers a tunable trade-off between circuit resources and estimation accuracy, making it particularly amenable to experimentally relevant architectures with long-range connectivity. Our results show that scalable quantum readout need not reproduce generic randomness: task-adapted randomization can enable substantially shallower global characterization protocols.Reliable and scalable readout strategies are essential for quantum technologies. As quantum processors grow, extracting useful information must remain feasible without measurement circuits becoming a dominant bottleneck. Randomized measurements and classical shadows provide a powerful route, but global estimation is conventionally associated with highly random ensembles that require increasing circuit depth and hence substantial experimental overhead. In this work, we show that substantially less randomness suffices when the readout is meaningfully adapted to the quantities being estimated. We introduce shallow phase shadows, based on a sparse Clifford-IQP ensemble, and prove efficient global estimation of stabilizer-state fidelities despite the ensemble not forming an approximate relative-error design. On all-to-all architectures, the protocol admits a constant-depth implementation using mid-circuit measurements and classical feedforward, or logarithmic depth without auxiliary systems. The protocol requires only controlled-phase entangling gates and offers a tunable trade-off between circuit resources and estimation accuracy, making it particularly amenable to experimentally relevant architectures with long-range connectivity. Our results show that scalable quantum readout need not reproduce generic randomness: task-adapted randomization can enable substantially shallower global characterization protocols.

quant-pharXiv:2609.10408Sep 10, 20260 citations

Multivariate trace estimation using quantum state space linear algebra

Liron Mor-Yosef, Shashanka Ubaru, Lior Horesh C +1 more

In this paper, we present a quantum algorithm for approximating multivariate traces, i.e. the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce \emph{quantum Matrix States Linear Algebra} (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm's inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as Block Encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.In this paper, we present a quantum algorithm for approximating multivariate traces, i.e. the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce \emph{quantum Matrix States Linear Algebra} (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm's inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as Block Encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.

arXiv:2405.01098May 2, 20240 citations

Multivariate Trace Estimation Using Quantum State Space Linear Algebra

Liron Mor-Yosef, Shashanka Ubaru, Lior Horesh C +1 more

Abstract. In this paper, we present a quantum algorithm for approximating multivariate traces, i.e., the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce quantum matrix states linear algebra (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm’s inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as block encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.Abstract. In this paper, we present a quantum algorithm for approximating multivariate traces, i.e., the traces of matrix products. Our research is motivated by the extensive utility of multivariate traces in elucidating spectral characteristics of matrices, as well as by recent advancements in leveraging quantum computing for faster numerical linear algebra. Central to our approach is a direct translation of a multivariate trace formula into a quantum circuit, achieved through a sequence of low-level circuit construction operations. To facilitate this translation, we introduce quantum matrix states linear algebra (qMSLA), a framework tailored for the efficient generation of state preparation circuits via primitive matrix algebra operations. Our algorithm relies on sets of state preparation circuits for input matrices as its primary inputs and yields two state preparation circuits encoding the multivariate trace as output. These circuits are constructed utilizing qMSLA operations, which enact the aforementioned multivariate trace formula. We emphasize that our algorithm’s inputs consist solely of state preparation circuits, eschewing harder to synthesize constructs such as block encodings. Furthermore, our approach operates independently of the availability of specialized hardware like QRAM, underscoring its versatility and practicality.

SIAM Journal on Matrix Analysis and ApplicationsJan 10, 20252 citations

Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits

Matthew Coudron, Michael J. Gullans, Jon Nelson +2 more

We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and $x$ is an arbitrary $n$ -bit output string. This improves over prior state-of-the-art algorithms that takes $n^{O(log(n))}$ time for the same task, $n^{O(log(log(n))}$ when $U$ is geometrically local, and $n^{O(1)}$ for 2D geometrically-local circuits.We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ time, where $U$ is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and $x$ is an arbitrary $n$-bit output string. This improves over prior state-of-the-art algorithms that takes $n^{O(log(n))}$ time for the same task, $n^{O(log(log(n))}$ when $U$ is geometrically local, and $n^{O(1)}$ for 2D geometrically-local circuits.

quant-pharXiv:2610.02146Oct 2, 20260 citations

Short-depth circuits for efficient expectation-value estimation

Alessandro Roggero, Alessandro Baroni

The evaluation of expectation values $\text{Tr}\left[\ensuremath{\rho}\mathcal{O}\right]$ for some pure state $\ensuremath{\rho}$ and Hermitian operator $\mathcal{O}$ is of central importance in a variety of quantum algorithms. Near-optimal techniques have been developed in the past and require a number of measurements $N$ approaching the Heisenberg limit $N=O\left(1/\ensuremath{\epsilon}\right)$ as a function of target accuracy $\ensuremath{\epsilon}$. The use of quantum phase estimation (QPE) requires, however, long circuit depths $C=O\left(1/\ensuremath{\epsilon}\right)$ making its implementation difficult on near-term noisy devices. The more direct strategy of operator averaging is usually preferred as it can be performed using $N=O\left(1/{\ensuremath{\epsilon}}^{2}\right)$ measurements and no additional gates aside from those needed for the state preparation. In this work we use a simple but realistic model to describe the bound state of a neutron and a proton (the deuteron) to show that the latter strategy can require an overly large number of measurements in order to achieve a prefixed relative target accuracy ${\ensuremath{\epsilon}}_{r}$. We propose to overcome this problem using a single step of QPE and classical postprocessing. This approach leads to a circuit depth $C=O\left({\ensuremath{\epsilon}}^{\ensuremath{\mu}}\right)$ (with $\ensuremath{\mu}\ensuremath{\ge}0$) and to a number of measurements $N=O\left(1/{\ensuremath{\epsilon}}^{2+\ensuremath{\nu}}\right)$ for $0<\ensuremath{\nu}\ensuremath{\le}1$ and a much smaller prefactor. We provide detailed descriptions of two implementations of our strategy for $\ensuremath{\nu}=1$ and $\ensuremath{\nu}\ensuremath{\approx}0.5$ and derive appropriate conditions that a particular problem instance has to satisfy in order for our method to provide an advantage.The evaluation of expectation values $\text{Tr}\left[\ensuremath{\rho}\mathcal{O}\right]$ for some pure state $\ensuremath{\rho}$ and Hermitian operator $\mathcal{O}$ is of central importance in a variety of quantum algorithms. Near-optimal techniques have been developed in the past and require a number of measurements $N$ approaching the Heisenberg limit $N=O\left(1/\ensuremath{\epsilon}\right)$ as a function of target accuracy $\ensuremath{\epsilon}$. The use of quantum phase estimation (QPE) requires, however, long circuit depths $C=O\left(1/\ensuremath{\epsilon}\right)$ making its implementation difficult on near-term noisy devices. The more direct strategy of operator averaging is usually preferred as it can be performed using $N=O\left(1/{\ensuremath{\epsilon}}^{2}\right)$ measurements and no additional gates aside from those needed for the state preparation. In this work we use a simple but realistic model to describe the bound state of a neutron and a proton (the deuteron) to show that the latter strategy can require an overly large number of measurements in order to achieve a prefixed relative target accuracy ${\ensuremath{\epsilon}}_{r}$. We propose to overcome this problem using a single step of QPE and classical postprocessing. This approach leads to a circuit depth $C=O\left({\ensuremath{\epsilon}}^{\ensuremath{\mu}}\right)$ (with $\ensuremath{\mu}\ensuremath{\ge}0$) and to a number of measurements $N=O\left(1/{\ensuremath{\epsilon}}^{2+\ensuremath{\nu}}\right)$ for $0<\ensuremath{\nu}\ensuremath{\le}1$ and a much smaller prefactor. We provide detailed descriptions of two implementations of our strategy for $\ensuremath{\nu}=1$ and $\ensuremath{\nu}\ensuremath{\approx}0.5$ and derive appropriate conditions that a particular problem instance has to satisfy in order for our method to provide an advantage.

arXiv:1905.08383Physical Review AFeb 24, 202018 citations

Calculating the trace of the product of

m\phantom{\rule{4pt}{0ex}}n

-qubit density matrices (multivariate trace) is a crucial subroutine in quantum error mitigation and information measure estimation. We propose a unified multivariate trace estimation (UMT) which conceptually unifies the previous qubit-optimal and depth-optimal approaches with tunable quantum circuit depth and number of qubits. The constructed circuits have $\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ or $n\ensuremath{\lceil}(m\ensuremath{-}1)/s\ensuremath{\rceil}$ depth corresponding to

(s+m)n

s+mn

qubits for $s\ensuremath{\in}{1,\ensuremath{\cdots},\ensuremath{\lfloor}m/2\ensuremath{\rfloor}}$, respectively. Such flexible circuit structures enable people to choose suitable circuits for different hardware devices. We apply UMT to virtual distillation to achieve exponential error suppression and design a family of concrete circuits to calculate the trace of the product of eight and nine

n

-qubit density matrices. A numerical example shows that the additional circuits still mitigate the noise expectation value under the global depolarizing channel.

We give a deterministic classical algorithm that estimates

|\langle x|U|0^n\rangle|^2

to additive error

\varepsilon

\mathrm{poly}(n, 1/\varepsilon)

time, where

U

is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and

x

is an arbitrary

n

-bit output string. This improves over prior state-of-the-art algorithms that takes

n^{O(log(n))}

time for the same task,

n^{O(log(log(n))}

when

U

is geometrically local, and

n^{O(1)}

for 2D geometrically-local circuits.

The evaluation of expectation values $\text{Tr}\left[\ensuremath{\rho}\mathcal{O}\right]$ for some pure state $\ensuremath{\rho}$ and Hermitian operator

\mathcal{O}

is of central importance in a variety of quantum algorithms. Near-optimal techniques have been developed in the past and require a number of measurements

N

approaching the Heisenberg limit $N=O\left(1/\ensuremath{\epsilon}\right)$ as a function of target accuracy $\ensuremath{\epsilon}$. The use of quantum phase estimation (QPE) requires, however, long circuit depths $C=O\left(1/\ensuremath{\epsilon}\right)$ making its implementation difficult on near-term noisy devices. The more direct strategy of operator averaging is usually preferred as it can be performed using $N=O\left(1/{\ensuremath{\epsilon}}^{2}\right)$ measurements and no additional gates aside from those needed for the state preparation. In this work we use a simple but realistic model to describe the bound state of a neutron and a proton (the deuteron) to show that the latter strategy can require an overly large number of measurements in order to achieve a prefixed relative target accuracy ${\ensuremath{\epsilon}}_{r}$. We propose to overcome this problem using a single step of QPE and classical postprocessing. This approach leads to a circuit depth $C=O\left({\ensuremath{\epsilon}}^{\ensuremath{\mu}}\right)$ (with $\ensuremath{\mu}\ensuremath{\ge}0$) and to a number of measurements $N=O\left(1/{\ensuremath{\epsilon}}^{2+\ensuremath{\nu}}\right)$ for $0<\ensuremath{\nu}\ensuremath{\le}1$ and a much smaller prefactor. We provide detailed descriptions of two implementations of our strategy for $\ensuremath{\nu}=1$ and $\ensuremath{\nu}\ensuremath{\approx}0.5$ and derive appropriate conditions that a particular problem instance has to satisfy in order for our method to provide an advantage.