The quantum advantage, a key goal in quantum computation, is achieved when a quantum computer’s computational capability surpasses classical means. A recent study introduced a type of Instantaneous Quantum Polynomial-Time (IQP) computation, which was challenged by IBM Quantum and IonQ researchers who developed a faster classical simulation algorithm. IQP circuits are beneficial due to their simplicity and moderate hardware requirements, but they also allow for classical simulation. The IQP circuit, known as the HarvardQuEra circuit, is built over n 3m 32k inputs. There are two types of simulation for quantum computations: noiseless weak/direct and noisy.
What is the Quantum Advantage, and How is it Achieved?
The quantum advantage is a key goal for the quantum computation community. It is achieved when a quantum computer’s computational capability becomes so complex that it cannot be reproduced by classical means. This ongoing negotiation between classical simulations and quantum computational experiments is a significant focus in the field.
A recent publication by Bluvstein et al. introduced a type of Instantaneous Quantum Polynomial-Time (IQP) computation, complemented by a 48-qubit logical experimental demonstration using quantum hardware. The authors projected the simulation time to grow rapidly with the number of CNOT layers added. However, researchers from IBM Quantum and IonQ reported a classical simulation algorithm that computes an amplitude for the 48-qubit computation in only 0.00257947 seconds, which is roughly 10^3 times faster than that reported by the original authors. This algorithm is not subject to a significant decline in performance due to the additional CNOT layers.
What are the Benefits and Limitations of IQP Circuits?
IQP circuits offer several benefits, including conceptual simplicity, moderate hardware requirements, and suitability for demonstration using early fault-tolerant quantum computers. However, the relative simplicity of the IQP circuits, including the layered structure of the IQP transformation, enables classical simulation of 50-qubit IQP circuits in a few minutes on a laptop computer. As a result, a higher number of qubits may be required to participate in an IQP computation before it is no longer possible to simulate classically.
How are IQP Circuits Defined and Simulated?
An n-qubit IQP circuit can be defined as a three-stage computation. While the function in the IQP computation can be arbitrary, it suffices to consider it computed by the EXOR polynomials of degree 3, which offers a problem whose complexity was shown to be P-hard. The algorithm reported by the IBM Quantum and IonQ researchers beats the lower bound of simulation complexity, but this does not contradict the fact that the HQ circuit is well-structured and does not correspond to the hardest instance of an IQP computation.
What is the Structure of the HarvardQuEra Circuit?
The IQP circuit, known as the HarvardQuEra circuit, is built over n 3m 32k inputs. Between the two layers of Hadamard gates, it implements a combination of linear Boolean transformation and phase computation. The qubits are grouped into blocks of three to reduce computational errors. The blocks are broken into two non-overlapping sets such that the graph distance over the Boolean cube in each set is 2. This circuit introduces an asymmetry in the application of the third diagonal Z-axis layer.
What are the Types of Simulation for Quantum Computations?
There are two types of simulation for quantum computations. The first, noiseless weak or noiseless direct, is a classical simulation that allows sampling bitstrings computed by a given quantum circuit. This simulation is directly comparable to a noiseless quantum computer. Since no current prototype quantum computer is noiseless, the weak/direct simulation is at least as powerful as the quantum computer.
The article titled “Fast classical simulation of Harvard/QuEra IQP circuits” was published on February 5, 2024. The authors of this article are Dmitri Maslov, Sergey Bravyi, Felix Tripier, Andrii O. Maksymov, and Joe Latone. The article was sourced from arXiv, a repository managed by Cornell University. The article can be accessed through its DOI reference https://doi.org/10.48550/arxiv.2402.03211.
