An ultimate goal of quantum computing is to perform calculations beyond the reach of any classical computer. It is therefore imperative that useful quantum computers be very difficult to simulate classically, otherwise classical computers could be used for the applications envisioned for the quantum ones. Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits or the depth of the circuit. This difficulty has triggered recent experiments on deep, random circuits that aim to demonstrate that quantum devices may already perform tasks beyond the reach of classical computing. These real quantum computing devices, however, suffer from many sources of decoherence and imprecision which limit the degree of entanglement that can actually be reached to a fraction of its theoretical maximum. They are characterized by an exponentially decaying fidelity with an error rate per operation as small as for current devices with several dozen qubits or even smaller for smaller devices. In this work, we provide new insight on the computing capabilities of real quantum computers by demonstrating that they can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wave functions using matrix product states, which are able to capture states with low to moderate entanglement very accurately. This compression introduces a finite error rate so that the algorithms closely mimic the behavior of real quantum computing devices. The computing time of our algorithm increases only linearly with and in sharp contrast with exact simulation algorithms. We illustrate our algorithms with simulations of random circuits for qubits connected in both one- and two-dimensional lattices. We find that can be decreased at a polynomial cost in computing power down to a minimum error . Getting below requires computing resources that increase exponentially with . For a two-dimensional array of qubits and a circuit with control- gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours. For more complex gates such as a swap gate followed by a controlled rotation, the error rate increases by a factor 3 for similar computing time. Our results suggest that, despite the high fidelity reached by quantum devices, only a tiny fraction of the system Hilbert space is actually being exploited.
We develop a density-matrix renormalization group (DMRG) algorithm for the simulation of quantum circuits. This algorithm can be seen as the extension of the time-dependent DMRG from the usual situation of Hermitian Hamiltonian matrices to quantum circuits defined by unitary matrices. For small circuit depths, the technique is exact and equivalent to other matrix product state–based techniques. For larger depths, it becomes approximate in exchange for an exponential speed up in computational time. Like an actual quantum computer, the quality of the DMRG results is characterized by a finite fidelity. However, unlike a quantum computer, the fidelity depends strongly on the quantum circuit considered. For the most difficult possible circuit for this technique, the so-called “quantum supremacy” benchmark of Google LLC [Arute et al., Nature 574, 505 (2019)], we find that the DMRG algorithm can generate bit strings of the same quality as the seminal Google experiment on a single computing core. For a more structured circuit used for combinatorial optimization (quantum approximate optimization algorithm), we find a drastic improvement of the DMRG results with error rates dropping by a factor of compared with random quantum circuits. Our results suggest that the current bottleneck of quantum computers is their fidelities rather than the number of qubits.
Moiré systems provide a rich platform for studies of strong correlation physics. Recent experiments on heterobilayer transition metal dichalcogenide Moiré systems are exciting in that they manifest a relatively simple model system of an extended Hubbard model on a triangular lattice. Inspired by the prospect of the hetero-transition metal dichalcogenide Moiré system’s potential as a solid-state-based quantum simulator, we explore the extended Hubbard model on the triangular lattice using the density matrix renormalization group. Specifically, we explore the two-dimensional phase space spanned by the key tuning parameters in the extended Hubbard model, namely, the kinetic energy strength and the further-range Coulomb interaction strengths. We find competition between Fermi fluid, chiral spin liquid, spin density wave, and charge order. In particular, our finding of the optimal further-range interaction for the chiral correlation presents a tantalizing possibility.
We describe a new open-source Python-based package for high accuracy correlated electron calculations using quantum Monte Carlo (QMC) in real space: PyQMC. PyQMC implements modern versions of QMC algorithms in an accessible format, enabling algorithmic development and easy implementation of complex workflows. Tight integration with the PySCF environment allows for a simple comparison between QMC calculations and other many-body wave function techniques, as well as access to high accuracy trial wave functions.
The generalized Wigner crystal (GWC) is a novel quantum phase of matter driven by further-range interaction at fractional fillings of a lattice. The role of further-range interaction as the driver for the incompressible state is akin to the Wigner crystal. On the other hand, the significant role of commensurate filling is akin to the Mott insulator. Recent progress in simulator platforms presents unprecedented opportunities to investigate quantum melting in the strongly interacting regime through synergy between theory and experiments. However, the earlier theory literature presents diverging predictions. We study the quantum freezing of GWC through large-scale density matrix renormalization group simulations of a triangular lattice extended Hubbard model. We find a single first-order phase transition between the Fermi liquid and the sqrt[3]×sqrt[3] GWC state. The GWC state shows long-range antiferromagnetic 120° Néel order. Our results present the simplest answers to the question of the quantum phase transition into the GWC phase and the properties of the GWC phase.
Progress in fault-tolerant quantum computation (FTQC) has driven the pursuit of practical applications with early fault-tolerant quantum computers (EFTQC). These devices, limited in their qubit counts and fault-tolerance capabilities, require algorithms that can accommodate some degrees of error, which are known as EFTQC algorithms. To predict the onset of early quantum advantage, a comprehensive methodology is needed to develop and analyze EFTQC algorithms, drawing insights from both the methodologies of noisy intermediate-scale quantum and traditional FTQC. To address this need, we propose such a methodology for modeling algorithm performance on EFTQC devices under varying degrees of error. As a case study, we apply our methodology to analyze the performance of randomized Fourier estimation (RFE) [Kshirsagar, Katabarwa, and Johnson, arXiv:2209.11322], an EFTQC algorithm for phase estimation. We investigate the runtime performance and the fault-tolerant overhead of RFE in comparison to the traditional quantum phase estimation algorithm. Our analysis reveals that RFE achieves significant savings in physical qubit counts while having a much higher runtime upper bound. We anticipate even greater physical qubit savings when considering more realistic assumptions about the performance of EFTQC devices. By providing insights into the performance trade-offs and resource requirements of EFTQC algorithms, our work contributes to the development of practical and efficient quantum computing solutions on the path to quantum advantage.