ﻻ يوجد ملخص باللغة العربية
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.
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 cal
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
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-desig
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 t
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