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
-
Fault-tolerant syndrome extraction is a key ingredient in implementing fault-tolerant quantum computation. While conventional methods use a number of extra qubits that are linear in the weight of the syndrome, several improvements have been introduced using flag gadgets. In this work, we develop a framework to design flag gadgets using classical codes. Using this framework, we show how to perform fault-tolerant syndrome extraction for any stabilizer code with arbitrary distance using exponentially fewer qubits than conventional methods when qubit measurement and reset are relatively slow compared to a round of error correction. In particular, our method requires only ?? flag qubits to fault-tolerantly measure a weight ? stabilizer. We further take advantage of the saving provided by our construction to fault-tolerantly measure multiple stabilizers using a single gadget and show that it maintains the same exponential advantage when it is used to fault-tolerantly extract the syndromes of quantum low-density parity-check codes. Using the developed framework, we perform computer-assisted search to find several small examples where our constructions reduce the number of qubits required. These small examples may be relevant to near-term experiments on small-scale quantum computers.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1103/PRXQuantum.4.040318
