Estimating the eigenstate properties of quantum systems is a long-standing, challenging problem for both classical and quantum computing. Existing universal quantum algorithms typically rely on ideal and efficient query models (e.g., time evolution operator or block encoding of the Hamiltonian), which, however, become suboptimal for actual implementation at the quantum circuit level. Here, we present a full-stack design of quantum algorithms for estimating the eigenenergy and eigenstate properties, which can achieve high precision and good scaling with system size. The gate complexity per circuit for estimating generic Hamiltonians' eigenstate properties is [Formula: see text], which has a logarithmic dependence on the inverse precision ε. For lattice Hamiltonians, the circuit depth of our design achieves near-optimal system-size scaling, even with local qubit connectivity. Our full-stack algorithm has low overhead in circuit compilation, which thus results in a small actual gate count (cnot and non-Clifford gates) for lattice and molecular problems compared to advanced eigenstate algorithms. The algorithm is implemented on IBM quantum devices using up to 2000 two-qubit gates and 20,000 single-qubit gates and achieves high-precision eigenenergy estimation for Heisenberg-type Hamiltonians, demonstrating its noise robustness.
Estimating the eigenstate properties of quantum systems is a long-standing, challenging problem for both classical and quantum computing. Existing universal quantum algorithms typically rely on ideal and efficient query models (e.g., time evolution operator or block encoding of the Hamiltonian), which, however, become suboptimal for actual implementation at the quantum circuit level. Here, we present a full-stack design of quantum algorithms for estimating the eigenenergy and eigenstate properties, which can achieve high precision and good scaling with system size. The gate complexity per circuit for estimating generic Hamiltonians' eigenstate properties is [Formula: see text], which has a logarithmic dependence on the inverse precision ε. For lattice Hamiltonians, the circuit depth of our design achieves near-optimal system-size scaling, even with local qubit connectivity. Our full-stack algorithm has low overhead in circuit compilation, which thus results in a small actual gate count (cnot and non-Clifford gates) for lattice and molecular problems compared to advanced eigenstate algorithms. The algorithm is implemented on IBM quantum devices using up to 2000 two-qubit gates and 20,000 single-qubit gates and achieves high-precision eigenenergy estimation for Heisenberg-type Hamiltonians, demonstrating its noise robustness.
Abstract Quantum noise in real-world devices poses a significant challenge in achieving practical quantum advantage, since accurately compiled and executed circuits are typically deep and highly susceptible to decoherence. To facilitate the implementation of complex quantum algorithms on noisy hardware, we propose an approximate method for compiling target quantum circuits into brick-wall layouts. This new circuit design consists of two-qubit CNOT gates that can be directly implemented on real quantum computers, in conjunction with optimized one-qubit gates, to approximate the essential dynamics of the original circuit while significantly reducing its depth. Our approach is evaluated through numerical simulations of time-evolution circuits for the critical Ising model, quantum Fourier transformation, and Haar-random quantum circuits, as well as experiments on IBM quantum platforms. By accounting for compilation error and circuit noise, we demonstrate that time evolution and quantum Fourier transformation circuits achieve high compression rates, while random quantum circuits are less compressible. The degree of compression is related to the rate of entanglement accumulation in the target circuit. In particular, experiments on IBM platforms achieve a compression rate of 12.5 for N=12, significantly extending the application of current quantum devices. Furthermore, large-scale numerical simulations for system sizes up to N=30 reveal that the optimal depth dmax to achieve maximal overall fidelity is independent of system size N, suggesting the scalability of our method for large quantum devices in terms of quantum resources.
Noisy intermediate-scale quantum (NISQ) devices pave the way for implementing quantum algorithms that offer quantum advantages over their classical counterparts. Due to the intrinsic noise and decoherence in the physical system, NISQ machines are naturally modeled as large-scale, low-depth quantum circuits. In practice, executing such circuits requires sending program states that encode the relevant instructions to a programmable quantum computer, typically through a cloud service. Existing programming approaches designed for generic unitary transformations are computationally inefficient in the low-depth setting, and therefore remain unsatisfactory. As such, to realize NISQ algorithms, it is crucial to find an efficient way to program low-depth circuits as the number of qubits N increases. Here, we investigate the circuit complexity and the size of quantum memory, known as the program cost, required to program low-depth brickwork circuits. We establish a tight worst-case program cost of Θ ( N p o l y l o g N ) for universally programming low-depth brickwork circuits in the large- N regime. Moreover, we analyze the trade-off between the cost of describing the layout of local gates and the cost of programming them to implement the target unitaries via the light-cone argument. Our findings suggest that faithful gate-wise programming is essentially optimal in the low-depth regime.
Quantum computing faces challenges such as noise, short coherence time, and limited qubit connections. These challenges worsen as quantum circuits become more complex. One major issue is the increasing depth of quantum circuits. This research proposes an optimization framework targeting depth and gate count reduction in quantum circuits, specifically for Noisy Intermediate-Scale Quantum (NISQ) devices. The proposed approach combines unitary merging of single-qubit gates, CNOT cancellation, gate commuting, and rotation gate rewriting strategies. Consecutive gates acting on the same qubit, such asRx(θ1)⋅Rx(θ2), are algebraically merged into a single rotation, while pairs of redundant CNOT gates are eliminated based on gate identity relations. The technique is implemented using Qiskit and validated across five diverse circuits including complex, random, and multi-qubit configurations. Experimental results show an average depth reduction of 33.33% and gate count reduction of 32.14%, with runtime improvement of up to 25%. For instance, an input circuit with a depth of 7 and gate count of 11 was reduced to a depth of 2 and 4 gates. All optimized circuits preserve functional correctness with a fidelityF≥0.99. High-resolution circuit diagrams are presented to visually demonstrate improvements before and after optimization. Additionally, global phase shifts such aseiπ/4are preserved or analytically characterized where relevant. This work enhances the viability of quantum computations on near-term hardware and opens pathways for future AI-driven quantum optimizations.
In quantum chemistry, the "electronic structure problem" refers to the process of numerically solving Schrodinger's equation for a given molecular system. These calculations rank among the most CPU-intensive computations that are performed nowadays, yet they are also crucial to the design of new drugs and materials. The idea behind quantum simulation of quantum chemistry is that a quantum computer could perform such calculations in a manner that is exponentially more efficient than what a classical computer could accomplish. In fact, quantum simulation is quite possibly the application most naturally suited to a quantum computer. In this work we introduce novel algorithms for the simulation of quantum chemistry, algorithms that are exponentially more precise than previous algorithms in the literature. Previous algorithms are based on the Trotter-Suzuki decomposition and scale like the inverse of the desired precision, while our algorithms represent the first practical application of the recently developed truncated Taylor series approach, and they achieve scaling that is logarithmic in the inverse of the precision. We explore algorithms for both second-quantized and first-quantized encodings of the chemistry Hamiltonian, where the second-quantized encoding requires mathcalO(N) qubits for an N spin-orbital system, and the highly compressed first-quantized encoding requires mathcalO(eta) qubits, where eta<<N is the number of electrons in the system. We first introduce a second-quantized algorithm that uses pre-computed molecular integrals, resulting in a gate count that scales like widetildecalO(N8t). Next we introduce algorithms that compute molecular integrals on the fly by carefully discretizing these integrals. Indeed, figuring out how to evaluate the integrals in an efficient manner is one of the main challenges of applying the truncated Taylor series approach to the chemistry problem: the complexity of a general quantum algorithm is traditionally formulated in terms of the number of queries made to an oracle whose assumption we just assume, but in this case, we actually construct the oracle for our specific problem. The evaluation of the oracle itself requires evaluating molecular integrals, which adds additional complexity to an algorithm. We find that the gate count of the second-quantized on-the-fly algorithm scales like widetildecalO(N5t). We also find that the first-quantized on-the-fly algorithm, which uses the configuration interaction (CI) matrix representation of the Hamiltonian, requires at most widetildecalO(eta2N3t) gates. In general, the discovery of exponentially more precise algorithms will allow for the simulation of larger molecular systems than was previously possible under Trotter-based methods. In addition, the results here can be generalized to the simulation of other fermionic systems beyond the electronic structure problem.
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy ε, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an n-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time T≥1, with circuit depth O(Tlog(nT/ε)) and gate count O(nTlog(nT/ε)). This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization.
Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time T in the stated regime and sufficiently small fixed error ε, any nearest-neighbor quantum circuit simulating these dynamics requires depth Ω(logn/loglogn). This matches our O(logn) upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.
Recent breakthroughs have opened the possibility of intermediate-scale quantum computing with tens to hundreds of qubits, and shown the potential for solving classical challenging problems, such as in chemistry and condensed matter physics. However, the high accuracy needed to surpass classical computers poses a critical demand on the circuit depth, which is severely limited by the non-negligible gate infidelity, currently around 0.1%-1%. The limited circuit depth places restrictions on the performance of variational quantum algorithms (VQA) and prevents VQAs from exploring desired nontrivial quantum states. To resolve this problem, we propose a paradigm of Schrödinger-Heisenberg variational quantum algorithms (SHVQA). Using SHVQA, the expectation values of operators on states that require very deep circuits to prepare can now be efficiently measured by rather shallow circuits. The idea is to incorporate a virtual Heisenberg circuit, which acts effectively on the measurement observables, into a real shallow Schrödinger circuit, which is implemented realistically on the quantum hardware. We choose a Clifford virtual circuit, whose effect on the Hamiltonian can be seen as efficient classical processing. Yet, it greatly enlarges the state's expressivity, realizing much larger unitary t designs. Our method enables accurate quantum simulation and computation that otherwise are only achievable with much deeper circuits or more accurate operations conventionally. This has been verified in our numerical experiments for a better approximation of random states, higher-fidelity solutions to the XXZ model, and the electronic structure Hamiltonians of small molecules. Thus, together with effective quantum error mitigation, our work paves the way for realizing accurate quantum computing algorithms with near-term quantum devices.