Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSolving search problems by strongly simulating quantum circuits
219
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Simulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted families of quantum circuits and we develop an additional technique in this article. Further, we show that strong simulation algorithms perform another fundamental task: solving search problems. Efficient strong simulation techniques allow solutions to a class of search problems to be counted and found efficiently. This enhances the utility of strong simulation methods, known or yet to be discovered, and extends the class of search problems known to be efficiently simulable. Relating strong simulation to search problems also bounds the computational power of efficiently strongly simulable circuits; if they could solve all problems in $mathrm{P}$ this would imply the collapse of the complexity hierarchy $mathrm{P} subseteq mathrm{NP} subseteq # mathrm{P}$.
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$.
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).
Limited quantum memory is one of the most important constraints for near-term quantum devices. Understanding whether a small quantum computer can simulate a larger quantum system, or execute an algorithm requiring more qubits than available, is both of theoretical and practical importance. In this Letter, we introduce cluster parameters $K$ and $d$ of a quantum circuit. The tensor network of such a circuit can be decomposed into clusters of size at most $d$ with at most $K$ qubits of inter-cluster quantum communication. We propose a cluster simulation scheme that can simulate any $(K,d)$-clustered quantum circuit on a $d$-qubit machine in time roughly $2^{O(K)}$, with further speedups possible when taking more fine-grained circuit structure into account. We show how our scheme can be used to simulate clustered quantum systems -- such as large molecules -- that can be partitioned into multiple significantly smaller clusters with weak interactions among them. By using a suitable clustered ansatz, we also experimentally demonstrate that a quantum variational eigensolver can still achieve the desired performance for estimating the energy of the BeH$_2$ molecule while running on a physical quantum device with half the number of required qubits.
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.
We construct quantum circuits for solving one-dimensional Schrodinger equations. Simulations of three typical examples, i.e., harmonic oscillator, square-well and Coulomb potential, show that reasonable results can be obtained with eight qubits. Our simulations show that simple quantum circuits can solve the standard quantum mechanical problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
