Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHigh-performance parallel classical scheme for simulating shallow quantum circuits
167
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Recently, constant-depth quantum circuits are proved more powerful than their classical counterparts at solving certain problems, e.g., the two-dimensional (2D) hidden linear function (HLF) problem regarding a symmetric binary matrix. To further investigate the boundary between classical and quantum computing models, in this work we propose a high-performance two-stage classical scheme to solve a full-sampling variant of the 2D HLF problem, which combines traditional classical parallel algorithms and a gate-based classical circuit model together for exactly simulating the target shallow quantum circuits. Under reasonable parameter assumptions, a theoretical analysis reveals our classical simulator consumes less runtime than that of near-term quantum processors for most problem instances. Furthermore, we demonstrate the typical all-connected 2D grid instances by moderate FPGA circuits, and show our designed parallel scheme is a practically scalable, high-efficient and operationally convenient tool for simulating and verifying graph-state circuits performed by current quantum hardware.
rate research
Read More
In a recent breakthrough, Bravyi, Gosset and K{o}nig (BGK) [Science, 2018] proved that simulating constant depth quantum circuits takes classical circuits $Omega(log n)$ depth. In our paper, we first formalise their notion of simulation, which we call possibilistic simulation. Then, from well-known results, we deduce that their circuits can be simulated in depth $O(log^{2} n)$. Separately, we construct explicit classical circuits that can simulate any depth-$d$ quantum circuit with Clifford and $t$ $T$-gates in depth $O(d+t)$. Our classical circuits use ${text{NOT, AND, OR}}$ gates of fan-in $leq 2$.
Recently, Bravyi, Gosset, and K{o}nig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Relaxed Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem. As a step towards even stronger lower bounds, we present a search problem that we call the Parity Bending Problem, which is in QNC^0/qpoly (QNC^0 circuits that are allowed to start with a quantum state of their choice that is independent of the input), but is not even in AC^0[2] (the class AC^0 with unbounded fan-in XOR gates). All the quantum circuits in our paper are simple, and the main difficulty lies in proving the classical lower bounds. For this we employ a host of techniques, including a refinement of H{aa}stads switching lemmas for multi-output circuits that may be of independent interest, the Razborov-Smolensky AC^0[2] lower bound, Vaziranis XOR lemma, and lower bounds for non-local games.
As quantum computers of non-trivial size become available in the near future, it is imperative to develop tools to emulate small quantum computers. This allows for validation and debugging of algorithms as well as exploring hardware-software co-design to guide the development of quantum hardware and architectures. The simulation of quantum computers entails multiplications of sparse matrices with very large dense vectors of dimension $2^n$, where $n$ denotes the number of qubits, making this a memory-bound and network bandwidth-limited application. We introduce the concept of a quantum computer textit{emulator} as a component of a software framework for quantum computing, enabling a significant performance advantage over simulators by emulating quantum algorithms at a high level rather than simulating individual gate operations. We describe various optimization approaches and present benchmarking results, establishing the superiority of quantum computer emulators in terms of performance.
Most research in quantum computing today is performed against simulations of quantum computers rather than true quantum computers. Simulating a quantum computer entails implementing all of the unitary operators corresponding to the quantum gates as tensors. For high numbers of qubits, performing tensor multiplications for these simulations becomes quite expensive, since $N$-qubit gates correspond to $2^{N}$-dimensional tensors. One way to accelerate such a simulation is to use field programmable gate array (FPGA) hardware to efficiently compute the matrix multiplications. Though FPGAs can efficiently perform tensor multiplications, they are memory bound, having relatively small block random access memory. One way to potentially reduce the memory footprint of a quantum computing system is to represent it as a tensor network; tensor networks are a formalism for representing compositions of tensors wherein economical tensor contractions are readily identified. Thus we explore tensor networks as a means to reducing the memory footprint of quantum computing systems and broadly accelerating simulations of such systems.
Verification of NISQ era quantum devices demands fast classical simulation of large noisy quantum circuits. We present an algorithm based on the stabilizer formalism that can efficiently simulate noisy stabilizer circuits. Additionally, the protocol can efficiently simulate a large set of multi-qubit mixed states that are not mixtures of stabilizer states. The existence of these bound states was previously only known for odd-dimensional systems like qutrits. The algorithm also has the favorable property that circuits with depolarizing noise are simulated much faster than unitary circuits. This work builds upon a similar algorithm by Bennink et al. (Phys. Rev. A 95, 062337) and utilizes a framework by Pashayan et al. (Phys. Rev. Lett. 115, 070501).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
