An official website of the United States government
Classical simulation of quantum circuits is crucial for evaluating and validating the design of new quantum algorithms. However, the number of quantum state amplitudes increases exponentially with the number of qubits, leading to the exponential growth of the memory requirement for the simulations. In this paper, we present a new data reduction technique to reduce the memory requirement of quantum circuit simulations. We apply our amplitude-aware lossy compression technique to the quantum state amplitude vector to trade the computation time and fidelity for memory space. The experimental results show that our simulator only needs 1/16 of the original memory requirement to simulate Quantum Fourier Transform circuits with 99.95% fidelity. The reduction amount of memory requirement suggests that we could increase 4 qubits in the quantum circuit simulation comparing to the simulation without our technique. Additionally, for some specific circuits, like Grover’s search, we could increase the simulation size by 18 qubits.
more »
« less
Quantum Fourier Transform Has Small Entanglement
The Quantum Fourier Transform (QFT) is a key component of many important quantum algorithms, most famously as being the essential ingredient in Shor's algorithm for factoring products of primes. Given its remarkable capability, one would think it can introduce large entanglement to qubit systems and would be difficult to simulate classically. While early results showed QFT indeed has maximal operator entanglement, we show that this is entirely due to the bit reversal in the QFT. The core part of the QFT has Schmidt coefficients decaying exponentially quickly, and thus it can only generate a constant amount of entanglement regardless of the number of qubits. In addition, we show the entangling power of the QFT is the same as the time evolution of a Hamiltonian with exponentially decaying interactions, and thus a variant of the area law for dynamics can be used to understand the low entanglement intuitively. Using the low entanglement property of the QFT, we show that classical simulations of the QFT on a matrix product state with low bond dimension only take time linear in the number of qubits, providing a potential speedup over the classical fast Fourier transform (FFT) on many classes of functions. We demonstrate this speedup in test calculations on some simple functions. For data vectors of length 106 to 108, the speedup can be a few orders of magnitude.
more »
« less
- Award ID(s):
- 2110041
- PAR ID:
- 10544586
- Publisher / Repository:
- aps.org
- Date Published:
- Journal Name:
- PRX Quantum
- Volume:
- 4
- Issue:
- 4
- ISSN:
- 2691-3399
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Quantum computing utilizes superposition and entanglement to surpass classical computer capabilities. Central to this are qubits and their use to realize parallel quantum algorithms through circuits of simple one or two qubit gates. Controlling and measuring quantum systems is challenging. Here, we introduce a paradigm utilizing logical phi-bits, classical analogues of qubits using nonlinear acoustic waves, supported by an externally driven acoustic metastructure. These phi-bits bridge a low-dimensional linearly scaling physical space to a high-dimensional exponentially scaling Hilbert space in which parallel processing of information can be realized in the form of unitary operations. Here, we show the implementation of a nontrivial three-phi-bit unitary operation analogous to a quantum circuit but achieved via a single action on the metastructure, whereby the qubit-based equivalent requires sequences of qubit gates. A phi-bit-based approach might offer advantages over quantum systems, especially in tasks requiring large complex unitary operations. This breakthrough hints at a fascinating intersection of classical and quantum worlds, potentially redefining computational paradigms by harnessing nonlinear classical mechanical systems in quantum-analogous manners, blending the best of both domains.more » « less
-
null (Ed.)Abstract This paper builds upon two key principles behind the Bourgain–Dyatlov quantitative uniqueness theorem for functions with Fourier transform supported in an Ahlfors regular set. We first provide a characterization of when a quantitative uniqueness theorem holds for functions with very quickly decaying Fourier transform, thereby providing an extension of the classical Paneah–Logvinenko–Sereda theorem. Secondly, we derive a transference result which converts a quantitative uniqueness theorem for functions with fast decaying Fourier transform to one for functions with Fourier transform supported on a fractal set. In addition to recovering the result of Bourgain–Dyatlov, we obtain analogous uniqueness results for denser fractals.more » « less
-
In order to evaluate, validate, and refine the design of new quantum algorithms or quantum computers, researchers and developers need methods to assess their correctness and fidelity. This requires the capabilities of quantum circuit simulations. However, the number of quantum state amplitudes increases exponentially with the number of qubits, leading to the exponential growth of the memory requirement for the simulations. In this work, we present our memory-efficient quantum circuit simulation by using lossy data compression. Our empirical data shows that we reduce the memory requirement to 16.5% and 2.24E-06 of the original requirement for QFT and Grover’s search, respectively. This finding further suggests that we can simulate deep quantum circuits up to 63 qubits with 0.8 petabytes memory.more » « less
-
Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1103/PRXQuantum.4.040318
