Parallel Hadamard Test

Abstract

The Hadamard test is a fundamental building block widely used in many quantum computing algorithms. It estimates the real or imaginary part of $⟨\ddot{I}ˆ|U|\ddot{I}ˆ⟩$, where $|\ddot{I}ˆ⟩$ 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.

17 pages, 21 figures

Topics & keywords