Time-space efficient simulations of quantum computations

DOI10.4086/TOC.2012.V008A001MaRDI QIDQ2913801zbMATH OpenOpenAlexFDO

Authors Dieter Van Melkebeek, Thomas Watson

Publication date 27 September 2012

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2012.v008a001

zbMATH Keywords

quantum computingsatisfiabilitysimulationsSolovay-Kitaevtime-space lower bounds

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Recommendations

• Space-bounded quantum complexity
• Quantum computers that can be simulated classically in polynomial time
• On the complexity of simulating space-bounded quantum computations
• scientific article; zbMATH DE number 1335895
• Quantum Complexity Theory

Cites work

• Classically controlled quantum computation
• Implementation of the semiclassical quantum Fourier transform in a scalable system
• Inductive time-space lower bounds for SAT and related problems
• Time-space tradeoffs for counting NP solutions modulo integers
• Time-space tradeoffs for satisfiability

Cited in

(15)

• On the complexity of simulating space-bounded quantum computations
• Qsimulation V2.0: an optimized quantum simulator
• Quantum circuits with classical channels and the principle of deferred measurements
• A structured view on weighted counting with relations to counting, quantum computation and applications
• Quantum alternation
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• Efficient Algorithms for Universal Quantum Simulation
• scientific article; zbMATH DE number 5320194 (Why is no real title available?)
• On the efficiency of quantum algorithms for Hamiltonian simulation
• scientific article; zbMATH DE number 1839460 (Why is no real title available?)
• A complete characterization of unitary quantum space
• The space-time cost of purifying quantum computations
• Lower bounds on the running time of two-way quantum finite automata and sublogarithmic-space quantum Turing machines
• Time-space lower bounds for simulating proof systems with quantum and randomized verifiers
• Quantum logspace algorithm for powering matrices with bounded norm

This page was built for publication: Time-space efficient simulations of quantum computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913801)