The number of measurements demanded by hybrid quantum-classical algorithms such as the variational quantum eigensolver (VQE) is prohibitively high for many problems of practical value.For such problems, realizing quantum advantage will require methods that dramatically reduce this cost.Previous quantum algorithms that reduce the measurement cost (e.g., quantum amplitude and phase estimation) require error rates that are too low for near-term implementation.Here we propose methods that take advantage of the available quantum coherence to maximally enhance the power of sampling on noisy quantum devices, reducing the measurement number and runtime compared to the standard sampling method of the VQE.Our scheme derives inspiration from quantum metrology, phase estimation, and the more recent "alpha-VQE" proposal, arriving at a general formulation that is robust to error and does not require ancilla qubits.The central object of this method is what we call the "engineered likelihood function" (ELF), used for carrying out Bayesian inference.We show how the ELF formalism enhances the rate of information gain in sampling as the physical hardware transitions from the regime of noisy intermediate-scale quantum computers to that of quantum error-corrected ones.This technique speeds up a central component of many quantum algorithms, with applications including chemistry, materials, finance, and beyond.Similar to the VQE, we expect small-scale implementations to be realizable on today's quantum devices.
The number of measurements demanded by hybrid quantum-classical algorithms such as the variational quantum eigensolver (VQE) is prohibitively high for many problems of practical value.For such problems, realizing quantum advantage will require methods that dramatically reduce this cost.Previous quantum algorithms that reduce the measurement cost (e.g., quantum amplitude and phase estimation) require error rates that are too low for near-term implementation.Here we propose methods that take advantage of the available quantum coherence to maximally enhance the power of sampling on noisy quantum devices, reducing the measurement number and runtime compared to the standard sampling method of the VQE.Our scheme derives inspiration from quantum metrology, phase estimation, and the more recent "alpha-VQE" proposal, arriving at a general formulation that is robust to error and does not require ancilla qubits.The central object of this method is what we call the "engineered likelihood function" (ELF), used for carrying out Bayesian inference.We show how the ELF formalism enhances the rate of information gain in sampling as the physical hardware transitions from the regime of noisy intermediate-scale quantum computers to that of quantum error-corrected ones.This technique speeds up a central component of many quantum algorithms, with applications including chemistry, materials, finance, and beyond.Similar to the VQE, we expect small-scale implementations to be realizable on today's quantum devices.
The number of measurements demanded by hybrid quantum-classical algorithms such as the variational quantum eigensolver (VQE) is prohibitively high for many problems of practical value. Quantum algorithms that reduce this cost (e.g. quantum amplitude and phase estimation) require error rates that are too low for near-term implementation. Here we propose methods that take advantage of the available quantum coherence to maximally enhance the power of sampling on noisy quantum devices, reducing measurement number and runtime compared to VQE. Our scheme derives inspiration from quantum metrology, phase estimation, and the more recent alpha-VQE proposal, arriving at a general formulation that is robust to error and does not require ancilla qubits. The central object of this method is what we call the engineered likelihood function (ELF), used for carrying out Bayesian inference. We show how the ELF formalism enhances the rate of information gain in sampling as the physical hardware transitions from the regime of noisy intermediate-scale quantum computers into that of quantum error corrected ones. This technique speeds up a central component of many quantum algorithms, with applications including chemistry, materials, finance, and beyond. Similar to VQE, we expect small-scale implementations to be realizable on today's quantum devices.
The rapid development of noisy intermediate-scale quantum (NISQ) devices has raised the question of whether or not these devices will find commercial use. Unfortunately, a major shortcoming of many proposed NISQ-amenable algorithms, such as the variational quantum eigensolver (VQE), is coming into view: the algorithms require too many independent quantum measurements to solve practical problems in a reasonable amount of time. This motivates the central question of our work: how might we speed up such algorithms in spite of the impact of error on NISQ computations? We demonstrate on quantum hardware that the estimation of expectation values, a core subroutine of many quantum algorithms including VQE, can be improved in terms of precision and accuracy by using a technique we call Robust Amplitude Estimation. Consequently, this method reduces the runtime to achieve the same mean-squared error compared to the standard prepare-and-measure estimation method. The surprising result is that by using deeper, and therefore more error-prone, quantum circuits, we realize more accurate quantum computations in less time. As the quality of quantum devices improves, this method will provide a proportional reduction in estimation runtime. This technique may be used to speed up quantum computations into the regime of early fault-tolerant quantum computation and aid in the realization of quantum advantage.
Quantum chemistry and materials is one of the most promising applications of quantum computing. Yet much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them. Most previous efforts have carried out resource estimations for quantum algorithms run on large-scale fault-tolerant architectures, which include the quantum phase estimation algorithm. In contrast, few have assessed the performance of near-term quantum algorithms, which include the variational quantum eigensolver (VQE) algorithm. Recently, a large-scale benchmark study [Gonthier et al. 2020] found evidence that the performance of the variational quantum eigensolver for a set of industry-relevant molecules may be too inefficient to be of practical use. This motivates the need for developing and assessing methods that improve the efficiency of VQE. In this work, we predict the runtime of the energy estimation subroutine of VQE when using robust amplitude estimation (RAE) to estimate Pauli expectation values. Under conservative assumptions, our resource estimation predicts that RAE can reduce the runtime over the standard estimation method in VQE by one to two orders of magnitude. Despite this improvement, we find that the runtimes are still too large to be practical. These findings motivate two complementary efforts towards quantum advantage: 1) the investigation of more efficient near-term methods for ground state energy estimation and 2) the development of problem instances that are of industrial value and classically challenging, but better suited to quantum computation.
We present mathematical and conceptual foundations for the task of robust amplitude estimation using engineered likelihood functions (ELFs), a framework introduced by Wang et al. [PRX Quantum 2, 010346 (2021)] that uses Bayesian inference to enhance the rate of information gain in quantum sampling. These ELFs, which are obtained by choosing tunable parameters in a parametrized quantum circuit to minimize the expected posterior variance of an estimated parameter, play an important role in estimating the expectation values of quantum observables. We give a thorough characterization and analysis of likelihood functions arising from certain classes of quantum circuits and combine this with the tools of Bayesian inference to give a procedure for picking optimal ELF tunable parameters. Finally, we present numerical results to demonstrate the performance of ELFs.
Measurement overhead and hardware noise present fundamental obstacles to the practical realization of quantum algorithms on near-term quantum devices. In many quantum applications, the dominant computational cost arises from repeated measurements needed to extract accurate information and from handling noise effects. This dissertation develops a unified framework for efficient measurement and error mitigation in quantum algorithms.In this work, measurement is treated as a controllable and designable component across hardware, algorithmic, and statistical levels, rather than as a fixed final step. By tailoring measurement schemes and estimators, we show that substantial reductions in measurement cost can be achieved without sacrificing accuracy. This approach is developed and validated across multiple settings, from hardware-level randomized measurement implementations to algorithm-level molecular energy estimation.At the hardware level, we investigate randomized measurement schemes based on photonic metasurfaces. We find that the device itself naturally realizes the required family of measurement bases without repeated active optical reconfiguration, providing an efficient platform for randomized measurements. We analyze the effect of realistic measurement noise and develop calibration-based error mitigation techniques that suppress noise-induced bias. Numerical studies show that this approach enables accurate estimation of state properties under realistic measurement noise.At the algorithmic level, we investigate measurement-efficient quantum eigen solvers through the Non-Orthogonal Quantum Eigensolver (NOQE). We develop a detailed implementation framework for NOQE, including circuit construction and simplification, analysis of measurement complexity, and resource estimation. Building on this understanding, we incorporate randomized measurements as an alternative to standard Hadamard-test-based schemes and develop shadow-tomography-enhanced variants of NOQE that significantly reduce circuit complexity and qubit requirements while maintaining favorable sample complexity. Shadow-based error mitigation methods, including shadow distillation, further improve robustness against noise.Finally, we investigate a more fundamental redesign of the NOQE measurement task by reformulating matrix-element estimation as a quantum amplitude estimation problem. By integrating iterative quantum amplitude estimation into the NOQE framework, we replace the original incoherent sampling-based estimation with coherent information accumulation through amplitude amplification and achieve near-Heisenberg scaling in measurement complexity, improving on the standard sampling-based methods. Numerical results for molecular energy estimation demonstrate that this approach reaches chemical accuracy with fewer queries than the original NOQE.Overall, this dissertation shows that measurement overhead is not a fixed limitation, but a resource bottleneck that can be identified and reduced at multiple levels in quantum applications. Across the settings studied here, improvements are achieved at different layers, including hardware-aware randomized measurements, algorithm-level redesign of measurement protocols, estimator-level error mitigation, and statistical improvements based on coherent information accumulation. Taken together, these results provide a unified framework for understanding and reducing measurement cost under realistic noise, and offer practical guidance for the design of quantum algorithms on near-term quantum devices.
Combinatorial optimization on near-term quantum devices is a promising path to demonstrating quantum advantage. However, the capabilities of these devices are constrained by high noise or error rates. In this article, inspired by the variational quantum eigensolver (VQE), we propose an iterative layer VQE (L-VQE) approach. We present a large-scale numerical study, simulating circuits with up to 40 qubits and 352 parameters, that demonstrates the potential of the proposed approach. We evaluate quantum optimization heuristics on the problem of detecting multiple communities in networks, for which we introduce a novel qubit-frugal formulation. We numerically compare L-VQE with the quantum approximate optimization algorithm (QAOA) and demonstrate that QAOA achieves lower approximation ratios while requiring significantly deeper circuits. We show that L-VQE is more robust to finite sampling errors and has a higher chance of finding the solution as compared with standard VQE approaches. Our simulation results show that L-VQE performs well under realistic hardware noise.