Parallel Hadamard Test

The Hadamard test (HT) is a fundamental quantum primitive used to estimate the expectation value of a unitary operator, $\langle \psi | U | \psi \rangle$. While essential for variational quantum algorithms, quantum phase estimation, and kernel methods, executing these tests individually for a large number of operators creates a bottleneck. Each distinct circuit requires separate compilation, queuing, and execution, leading to high overheads in cloud-based quantum computing environments.

The authors propose the Parallel Hadamard Test (PHT), which consolidates multiple Hadamard tests into a single quantum circuit. By preparing a specific ancilla state—typically a W-state—the circuit creates a superposition of branches, where each branch applies a different unitary operator to the system register. By measuring the ancilla qubits, the user can extract the real or imaginary parts of multiple expectation values simultaneously.

The PHT framework is designed to handle three common structural workloads:

• Arbitrary Unitary Sets: Useful for gradient estimation in variational algorithms where many parameters must be updated.
• Prefix-Product Arrays: Applicable to algorithms like quantum complex exponential least squares (QCELS), which require sequential products of operators.
• Gram-Matrix Elements: Efficient for quantum kernel methods where the number of off-diagonal overlaps scales quadratically with the dataset size.

In regimes where fixed per-circuit overheads (such as compilation and queuing) dominate the total cost, PHT provides significant savings in both time and financial expense. Furthermore, for Gram-matrix workloads, the method can reduce the total number of shots required when off-diagonal overlaps are small.