Solving search problems by strongly simulating quantum circuits
arXiv:1209.6010 · doi:10.1038/srep01235
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 this would imply the collapse of the complexity hierarchy $\mathrm{P} \subseteq \mathrm{NP} \subseteq # \mathrm{P}$.
9 pages, 3 figures
References in corpus (25)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Efficient classical simulation of slightly entangled quantum computations
- Improved Simulation of Stabilizer Circuits
- A Theory of Fault-Tolerant Quantum Computation
- On the role of entanglement in quantum computational speed-up
- Classical simulation of quantum many-body systems with a tree tensor network
- Simulating quantum computation by contracting tensor networks
- From density-matrix renormalization group to matrix product states
- Classical simulation of noninteracting-fermion quantum circuits
- Synthesis and Optimization of Reversible Circuits - A Survey
- Matchgates and classical simulation of quantum circuits
- Fast simulation of stabilizer circuits using a graph state representation
- Classical simulation versus universality in measurement based quantum computation
- On measurement-based quantum computation with the toric code states
- Fermionic Linear Optics and Matchgates
- Efficient classical simulation of the semi-classical Quantum Fourier Transform
- Efficient classical simulation of the approximate quantum Fourier transform
- Exact matrix product solutions in the Heisenberg picture of an open quantum spin chain
- On the simulation of quantum circuits
- Dynamical simulations of classical stochastic systems using matrix product states
- Fermionic Linear Optics Revisited
- Quantum algorithms for spin models and simulable gate sets for quantum computation
- Categorical Tensor Network States
- Classical simulation of limited-width cluster-state quantum computation
- Quantum matchgate computations and linear threshold gates
Cited by in corpus (13)
- Lecture Notes of Tensor Network Contractions
- Variational Quantum Eigensolver with Fewer Qubits
- Tensor Networks in a Nutshell
- Encoding Hypergraphs into Quantum States
- Tensor Network Contractions for #SAT
- Probabilistic Nonunitary Gate in Imaginary Time Evolution
- Lectures on Quantum Tensor Networks
- A tree tensor network approach to simulating Shor's algorithm
- Quantum Compressed Sensing with Unsupervised Tensor-Network Machine Learning
- Ab initio optimization principle for the ground states of translationally invariant strongly correlated quantum lattice models
- Tensor network non-zero testing
- A multiprecision C++ library for matrix-product-state simulation of quantum computing: Evaluation of numerical errors
- Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics