Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.12344

Parallel Hadamard Test

Soichiro Imamura, Synge Todo

quant-phSubmitted Jul 14, 2026• Announced Jul 15, 2026• 0 citations
arXivHTMLPDF

Abstract

The Hadamard test is a fundamental building block widely used in many quantum computing algorithms. It estimates the real or imaginary part of $\langle ψ\vert U \vert ψ\rangle$, where $\vert ψ\rangle$ is a quantum state and $U$ is a unitary operator. In many algorithms, however, many such quantities must be estimated, leading to a large number of distinct circuit types, long computational times, and high financial costs. In this work, we propose the parallel Hadamard test, which combines multiple Hadamard tests into a single circuit type. We demonstrate how the parallel Hadamard test applies to three structural classes of workloads: arbitrary sets of unitary operators, prefix-product arrays, and Gram-matrix elements. For each class, we compare the cost of the parallel Hadamard test with that of the conventional one. Our unified approach significantly reduces the number of distinct circuit types, and can lower both computational time and financial costs in regimes where fixed per-circuit overheads dominate the total cost. In Gram-matrix workloads, it can also reduce the total number of shots when typical off-diagonal overlaps are small.

Comments
17 pages, 21 figures

Related papers

Quantum Matrix Arithmetics with Hamiltonian Evolution

Christopher Kang, Yuan Su

The efficient implementation of matrix arithmetic operations underpins the speedups of many quantum algorithms. We develop a suite of methods to perform matrix arithmetics—with the result encoded in the off-diagonal blocks of a Hamiltonian—using Hamiltonian evolutions of input operators. We show how to maintain this Hamiltonian block encoding , so that matrix operations can be composed one after another, and the entire quantum computation takes ≤ 2 ancilla qubits. We achieve this for matrix multiplication, matrix addition, matrix inversion, Hermitian conjugation, fractional scaling, integer scaling, complex phase scaling, as well as singular value transformation for both odd and even polynomials. We also present an overlap estimation algorithm to extract classical properties of Hamiltonian block encoded operators, analogous to the well known Hadamard test, at no extra cost of qubit. Our Hamiltonian matrix multiplication uses the Lie group commutator product formula and its higher-order generalizations due to Childs and Wiebe. Our Hamiltonian singular value transformation employs a dominated polynomial approximation, where the approximation holds within the domain of interest, while the constructed polynomial is upper bounded by the target function over the entire unit interval. We describe a circuit for simulating a class of sum-of-squares Hamiltonians, attaining a commutator scaling in step count, while leveraging the power of matrix arithmetics to reduce the cost of each simulation step. In particular, we apply this to the doubly factorized tensor hypercontracted Hamiltonians from recent studies of quantum chemistry, obtaining further improvements for initial states with a fixed number of particles. We achieve this with 1 ancilla qubit.

arXiv:2510.06316•ACM Transactions on Quantum Computing•Aug 8, 2026•0 citations

Fisher information based lower bounds on the cost of quantum phase estimation

Ryosuke Kimura, Kosuke Mitarai

Quantum phase estimation (QPE) is a cornerstone of quantum algorithms designed to estimate the eigenvalues of a unitary operator. QPE is typically implemented through two paradigms with distinct circuit structures: quantum Fourier transform-based QPE (QFT-QPE) and Hadamard test-based QPE (HT-QPE). Existing performance assessments fail to separate the statistical information inherent in the quantum circuit from the efficiency of classical post-processing, thereby obscuring the limits intrinsic to the circuit structure itself. In this study, we employ Fisher information and the Cramer-Rao lower bound to formulate the performance limits of circuit designs independent of the efficiency of classical post-processing. Defining the circuit depth as $T$ and the total runtime as $t_{\rm total}$, our results demonstrate that the achievable scaling is constrained by a non-trivial lower bound on their product $T\,t_{\rm total}$, although previous studies have typically treated the circuit depth $T$ and the total runtime $t_{\rm total}$ as separate resources. Notably, QFT-QPE possesses a more favorable scaling with respect to the overlap between the input state and the target eigenstate corresponding to the desired eigenvalue than HT-QPE. Numerical simulations confirm these theoretical findings, demonstrating a clear performance crossover between the two paradigms depending on the overlap. Furthermore, we verify that practical algorithms, specifically the quantum multiple eigenvalue Gaussian filtered search (QMEGS) and curve-fitted QPE, achieve performance levels closely approaching our derived limits. By elucidating the performance limits inherent in quantum circuit structures, this work concludes that the optimal choice of circuit configuration depends significantly on the overlap.

quant-pharXiv:2603.12706•Mar 16, 2026•0 citations

NNN-Party Hadamard Test for Distributed Quantum Computation

Kaoru Yamamoto, Yuichiro Matsuzaki, Yasunari Suzuki +2 more

Quantum computers promise computational advantages over classical computers, but hardware-imposed limitations remain a major obstacle. The Hadamard test mitigates these limitations by estimating expectation values associated with resource-intensive quantum operations using simple quantum circuits at the cost of additional classical sampling, and therefore underlies many quantum algorithms. However, in distributed quantum computing (DQC), which offers a promising route to scalability, its use is hindered by the need for nonlocal controlled operations. Here we introduce an $N$-party Hadamard test for DQC that estimates the same expectation values as the standard Hadamard test without implementing nonlocal controlled operations. The protocol instead uses pre-shared entanglement together with local operations and classical communication, which are standard resources in DQC settings. To demonstrate its utility, we apply it to unitary operations for clustered Hamiltonian simulation and to projectors for stabilizer-state preparation, showing lower sampling overheads than previous approaches by exploiting pre-shared entangled ancilla states. Moreover, we numerically demonstrate Bell-state preparation from Werner states to show favorable sampling efficiency and noise robustness relative to conventional purification, circuit knitting/cutting, and probabilistic error cancellation. Our work provides a general strategy for bringing Hadamard-test-based algorithms to DQC, facilitating practical and flexible quantum computation.

arXiv:2411.10024•Nov 15, 2024•0 citations

AQ-Stacker: An Adaptive Quantum Matrix Multiplication Algorithm with Scaling via Parallel Hadamard Stacking

Wladimir Silva

Matrix multiplication (MatMul) is the computational backbone of modern machine learning, yet its classical complexity remains a bottleneck for large scale data processing. We propose a hybrid quantum classical algorithm for matrix multiplication based on an adaptive configuration of Hadamard tests. By introducing classical memoization that caches state preparation blocks outside the main compilation loop, we reduce the total classical pre processing overhead for all N^2 element circuits to O(N^2). This decouples the heavy gate synthesis overhead from the core quantum processing loop, enabling execution complexities that strictly match classical input/output boundaries. We introduce an "Adaptive Stacking" framework that allows the algorithm to dynamically reconfigure its execution pattern - from sequential horizontal stacking to massive vertical parallelism - based on available qubit resources. This flexibility enables a tunable time complexity range, theoretically reaching O(N^2) on fault tolerant systems while maintaining compatibility with near term hardware. Our core theoretical contribution is the formalization of the "Entropy Dividend": an information theoretic concentration bound proving that the effective measurement variance sigma^2_eff <= (1/S) (1 - (1/2N) e^[H_max - H(psi)]) approaches its maximum. This makes AQ-Stacker uniquely suited for stabilizing the stochastic weight distributions of deep neural networks. We validate the numerical stability of our approach through Quantum Machine Learning (QML) Statevector simulations, achieving 96% accuracy on the MNIST handwritten digit dataset. Our results suggest that entropic noise suppression and parallel Hadamard stacking provide a scalable path toward super-classical efficiency in next-generation quantum-enhanced AI.

quant-pharXiv:2604.02530•Apr 6, 2026•0 citations

Sandwich test for Quantum Phase Estimation

Avatar Tulsi

Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications like finding better medicines, batteries, materials, catalysts etc. Many QPE algorithms use the Hadamard test to estimate $\langle ψ|U^{k}|ψ\rangle$ for a large integer $k$ for an efficiently preparable initial state $|ψ\rangle$ and an efficiently implementable unitary operator $U$. The Hadamard test is hard to implement because it requires controlled applications of $U^{k}$. Recently, a Sequential Hadamard test (SHT) was proposed (arXiv:2506.18765) which requires controlled application of $U$ only but its total run time $T_{\rm tot}$ scales as $\mathcal{O}(k^{3}/ε^{2}r_{\rm min}^{2})$ where $r_{\rm min}$ is the minimum value of $|\langle ψ|U^{k'}|ψ\rangle|$ among all integers $k' \leq k$. Typically $r_{\rm min}$ is exponentially low and SHT becomes too slow. We present a new algorithm, the SANDWICH test to address this bottleneck. Our algorithm uses efficient preparation of the initial state $|ψ\rangle$ to efficiently implement the SPROTIS operator $R_ψ^ϕ$ where SPROTIS stands for the Selective Phase Rotation of the Initial State. It sandwiches the SPROTIS operator between $U^{a}$ and $U^{b}$ for integers $\{a,b\} \leq k$ to estimate $\langle ψ|U^{k}|ψ\rangle$. The total run time $T_{\rm tot}$ is $\mathcal{O}(k^{2}\ln k/ ε^{2} s_{\rm min}^{6})$. Here $s_{\rm min}$ is the minimum value of $|\langle ψ|U^{\hat{k}}|ψ\rangle$ among all integers $\hat{k}$ which are values of the nodes of a random binary sum tree whose root node value is $k$ and leaf nodes' values are $1$ or $0$. It can be reasonably expected that $s_{\rm min} \not\ll 1$ in typical cases because there is wide freedom in choosing the random binary sum tree.

arXiv:2507.23716•Jul 31, 2025•0 citations

Quantum Circuit Implementation of Two Matrix Product Operations and Elementary Column Transformations

Yu-Hang Liu, Yuan-Hong Tao, Jing-Run Lan +1 more

This paper focuses on quantum algorithms for three key matrix operations: Hadamard (Schur) product, Kronecker (tensor) product, and elementary column transformations each. By designing specific unitary transformations and auxiliary quantum measurement, efficient quantum schemes with circuit diagrams are proposed. Their computational depths are: O(1) for Kronecker product; O(max(m,n)) for Hadamard product (linked to matrix dimensions); and O(m) for elementary column transformations of (2^n X 2^m) matrices (dependent only on column count).Notably, compared to traditional column transformation via matrix transposition and row transformations, this scheme reduces computation steps and quantum gate usage, lowering quantum computing energy costs.

quant-pharXiv:2511.02413•Nov 5, 2025•0 citations
The Hadamard test is a fundamental building block widely used in many quantum computing algorithms. It estimates the real or imaginary part of ⟨ψ∣U∣ψ⟩\langle ψ\vert U \vert ψ\rangle⟨ψ∣U∣ψ⟩, where ∣ψ⟩\vert ψ\rangle∣ψ⟩ is a quantum state and UUU is a unitary operator. In many algorithms, however, many such quantities must be estimated, leading to a large number of distinct circuit types, long computational times, and high financial costs. In this work, we propose the parallel Hadamard test, which combines multiple Hadamard tests into a single circuit type. We demonstrate how the parallel Hadamard test applies to three structural classes of workloads: arbitrary sets of unitary operators, prefix-product arrays, and Gram-matrix elements. For each class, we compare the cost of the parallel Hadamard test with that of the conventional one. Our unified approach significantly reduces the number of distinct circuit types, and can lower both computational time and financial costs in regimes where fixed per-circuit overheads dominate the total cost. In Gram-matrix workloads, it can also reduce the total number of shots when typical off-diagonal overlaps are small.
The efficient implementation of matrix arithmetic operations underpins the speedups of many quantum algorithms. We develop a suite of methods to perform matrix arithmetics—with the result encoded in the off-diagonal blocks of a Hamiltonian—using Hamiltonian evolutions of input operators. We show how to maintain this Hamiltonian block encoding , so that matrix operations can be composed one after another, and the entire quantum computation takes ≤ 2 ancilla qubits. We achieve this for matrix multiplication, matrix addition, matrix inversion, Hermitian conjugation, fractional scaling, integer scaling, complex phase scaling, as well as singular value transformation for both odd and even polynomials. We also present an overlap estimation algorithm to extract classical properties of Hamiltonian block encoded operators, analogous to the well known Hadamard test, at no extra cost of qubit. Our Hamiltonian matrix multiplication uses the Lie group commutator product formula and its higher-order generalizations due to Childs and Wiebe. Our Hamiltonian singular value transformation employs a dominated polynomial approximation, where the approximation holds within the domain of interest, while the constructed polynomial is upper bounded by the target function over the entire unit interval. We describe a circuit for simulating a class of sum-of-squares Hamiltonians, attaining a commutator scaling in step count, while leveraging the power of matrix arithmetics to reduce the cost of each simulation step. In particular, we apply this to the doubly factorized tensor hypercontracted Hamiltonians from recent studies of quantum chemistry, obtaining further improvements for initial states with a fixed number of particles. We achieve this with 1 ancilla qubit.
Quantum phase estimation (QPE) is a cornerstone of quantum algorithms designed to estimate the eigenvalues of a unitary operator. QPE is typically implemented through two paradigms with distinct circuit structures: quantum Fourier transform-based QPE (QFT-QPE) and Hadamard test-based QPE (HT-QPE). Existing performance assessments fail to separate the statistical information inherent in the quantum circuit from the efficiency of classical post-processing, thereby obscuring the limits intrinsic to the circuit structure itself. In this study, we employ Fisher information and the Cramer-Rao lower bound to formulate the performance limits of circuit designs independent of the efficiency of classical post-processing. Defining the circuit depth as TTT and the total runtime as ttotalt_{\rm total}ttotal​, our results demonstrate that the achievable scaling is constrained by a non-trivial lower bound on their product T ttotalT\,t_{\rm total}Tttotal​, although previous studies have typically treated the circuit depth TTT and the total runtime ttotalt_{\rm total}ttotal​ as separate resources. Notably, QFT-QPE possesses a more favorable scaling with respect to the overlap between the input state and the target eigenstate corresponding to the desired eigenvalue than HT-QPE. Numerical simulations confirm these theoretical findings, demonstrating a clear performance crossover between the two paradigms depending on the overlap. Furthermore, we verify that practical algorithms, specifically the quantum multiple eigenvalue Gaussian filtered search (QMEGS) and curve-fitted QPE, achieve performance levels closely approaching our derived limits. By elucidating the performance limits inherent in quantum circuit structures, this work concludes that the optimal choice of circuit configuration depends significantly on the overlap.
Quantum computers promise computational advantages over classical computers, but hardware-imposed limitations remain a major obstacle. The Hadamard test mitigates these limitations by estimating expectation values associated with resource-intensive quantum operations using simple quantum circuits at the cost of additional classical sampling, and therefore underlies many quantum algorithms. However, in distributed quantum computing (DQC), which offers a promising route to scalability, its use is hindered by the need for nonlocal controlled operations. Here we introduce an NNN-party Hadamard test for DQC that estimates the same expectation values as the standard Hadamard test without implementing nonlocal controlled operations. The protocol instead uses pre-shared entanglement together with local operations and classical communication, which are standard resources in DQC settings. To demonstrate its utility, we apply it to unitary operations for clustered Hamiltonian simulation and to projectors for stabilizer-state preparation, showing lower sampling overheads than previous approaches by exploiting pre-shared entangled ancilla states. Moreover, we numerically demonstrate Bell-state preparation from Werner states to show favorable sampling efficiency and noise robustness relative to conventional purification, circuit knitting/cutting, and probabilistic error cancellation. Our work provides a general strategy for bringing Hadamard-test-based algorithms to DQC, facilitating practical and flexible quantum computation.
Matrix multiplication (MatMul) is the computational backbone of modern machine learning, yet its classical complexity remains a bottleneck for large scale data processing. We propose a hybrid quantum classical algorithm for matrix multiplication based on an adaptive configuration of Hadamard tests. By introducing classical memoization that caches state preparation blocks outside the main compilation loop, we reduce the total classical pre processing overhead for all N^2 element circuits to O(N^2). This decouples the heavy gate synthesis overhead from the core quantum processing loop, enabling execution complexities that strictly match classical input/output boundaries. We introduce an "Adaptive Stacking" framework that allows the algorithm to dynamically reconfigure its execution pattern - from sequential horizontal stacking to massive vertical parallelism - based on available qubit resources. This flexibility enables a tunable time complexity range, theoretically reaching O(N^2) on fault tolerant systems while maintaining compatibility with near term hardware. Our core theoretical contribution is the formalization of the "Entropy Dividend": an information theoretic concentration bound proving that the effective measurement variance sigma^2_eff <= (1/S) (1 - (1/2N) e^[H_max - H(psi)]) approaches its maximum. This makes AQ-Stacker uniquely suited for stabilizing the stochastic weight distributions of deep neural networks. We validate the numerical stability of our approach through Quantum Machine Learning (QML) Statevector simulations, achieving 96% accuracy on the MNIST handwritten digit dataset. Our results suggest that entropic noise suppression and parallel Hadamard stacking provide a scalable path toward super-classical efficiency in next-generation quantum-enhanced AI.
Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications like finding better medicines, batteries, materials, catalysts etc. Many QPE algorithms use the Hadamard test to estimate ⟨ψ∣Uk∣ψ⟩\langle ψ|U^{k}|ψ\rangle⟨ψ∣Uk∣ψ⟩ for a large integer kkk for an efficiently preparable initial state ∣ψ⟩|ψ\rangle∣ψ⟩ and an efficiently implementable unitary operator UUU. The Hadamard test is hard to implement because it requires controlled applications of UkU^{k}Uk. Recently, a Sequential Hadamard test (SHT) was proposed (arXiv:2506.18765) which requires controlled application of UUU only but its total run time TtotT_{\rm tot}Ttot​ scales as O(k3/ε2rmin2)\mathcal{O}(k^{3}/ε^{2}r_{\rm min}^{2})O(k3/ε2rmin2​) where rminr_{\rm min}rmin​ is the minimum value of ∣⟨ψ∣Uk′∣ψ⟩∣|\langle ψ|U^{k'}|ψ\rangle|∣⟨ψ∣Uk′∣ψ⟩∣ among all integers k′≤kk' \leq kk′≤k. Typically rminr_{\rm min}rmin​ is exponentially low and SHT becomes too slow. We present a new algorithm, the SANDWICH test to address this bottleneck. Our algorithm uses efficient preparation of the initial state ∣ψ⟩|ψ\rangle∣ψ⟩ to efficiently implement the SPROTIS operator RψϕR_ψ^ϕRψϕ​ where SPROTIS stands for the Selective Phase Rotation of the Initial State. It sandwiches the SPROTIS operator between UaU^{a}Ua and UbU^{b}Ub for integers {a,b}≤k\{a,b\} \leq k{a,b}≤k to estimate ⟨ψ∣Uk∣ψ⟩\langle ψ|U^{k}|ψ\rangle⟨ψ∣Uk∣ψ⟩. The total run time TtotT_{\rm tot}Ttot​ is O(k2ln⁡k/ε2smin6)\mathcal{O}(k^{2}\ln k/ ε^{2} s_{\rm min}^{6})O(k2lnk/ε2smin6​). Here smins_{\rm min}smin​ is the minimum value of ∣⟨ψ∣Uk^∣ψ⟩|\langle ψ|U^{\hat{k}}|ψ\rangle∣⟨ψ∣Uk^∣ψ⟩ among all integers k^\hat{k}k^ which are values of the nodes of a random binary sum tree whose root node value is kkk and leaf nodes' values are 111 or 000. It can be reasonably expected that smin≪̸1s_{\rm min} \not\ll 1smin​≪1 in typical cases because there is wide freedom in choosing the random binary sum tree.
This paper focuses on quantum algorithms for three key matrix operations: Hadamard (Schur) product, Kronecker (tensor) product, and elementary column transformations each. By designing specific unitary transformations and auxiliary quantum measurement, efficient quantum schemes with circuit diagrams are proposed. Their computational depths are: O(1) for Kronecker product; O(max(m,n)) for Hadamard product (linked to matrix dimensions); and O(m) for elementary column transformations of (2^n X 2^m) matrices (dependent only on column count).Notably, compared to traditional column transformation via matrix transposition and row transformations, this scheme reduces computation steps and quantum gate usage, lowering quantum computing energy costs.