scientific article; zbMATH DE number 1776257
Abelian hidden subgroup problemBoolean circuitscomplexity classescomputational complexityquantum algorithmsquantum circuitsquantum codesquantum computationquantum NP-completeness
Complexity of computation (including implicit computational complexity) (03D15) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to quantum theory (81-01) Research exposition (monographs, survey articles) pertaining to quantum theory (81-02) Other types of codes (94B60)
The main text is divided into two parts about classical computation (40 pages) and quantum computation (120 pages), followed by a part with solutions to selected exercises (70 pages) and an appendix on elementary number theory (10 pages). The first part on classical computation gives an introduction to computational complexity that covers deterministic, nondeterministic and probabilistic Turing machines and corresponding complexity classes defined in terms of time or space bounds, as well as Boolean circuits, reducibilities, the theory of NP-completeness, the hierarchy of complexity classes between P and PSPACE, including a couple of more advanced results like the containment of BPP in the second level of the polynomial hierarchy. This part is well readable and understandable, the treatment is elegant and essentially self-contained; the exposition is slightly terse and can probably only be used for an introductory course when occasionally adding technical details. The second part on quantum computation covers quantum circuits, quantum computation and the class BQP, quantum algorithms for the Abelian hidden subgroup problem, quantum NP-completeness, and quantum codes. \textit{R. De Wolf} points out in his review of the book [Quantum Inf. Comp. 1, 95-96 (2003)] that the part on quantum computation focusses on issues that are related to Kitaev's work in this area, giving a not fully self-contained but detailed and insightful exposition of these topics, which ``will provide the researcher with invaluable insights and tools for new research, while, on the other hand, a considerable amount of more recent results and even some standard material in computer science aspects of quantum computation are missing, e.g., neither the Deutsch-Jozsa algorithm nor certain applications of Grover's algorithm are discussed.
- Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm
- Quantum zero-error algorithms cannot be composed
- Claw finding algorithms using quantum walk
- Random quantum circuits are approximate 2-designs
- Entanglement transmission and generation under channel uncertainty: universal quantum channel coding
- Optimal separation in exact query complexities for Simon's problem
- Cohering power of quantum operations
- The complexity of translationally invariant spin chains with low local dimension
- Quantum branching programs and space-bounded nonuniform quantum complexity
- Classical and quantum function reconstruction via character evaluation
- Quantum capacity under adversarial quantum noise: arbitrarily varying quantum channels
- An improved lower bound on query complexity for quantum PAC learning
- An introduction to quantum computing algorithms
- Braiding flux-tubes in topological quantum and classical lattice models from class-D
- Simulation of a multidimensional input quantum perceptron
- Shorter unentangled proofs for ground state connectivity
- A model of discrete quantum computation
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
- Quantum control robust with respect to coupling with an external environment
- Query complexity of generalized Simon's problem
- Classical proofs of quantum knowledge
- Towards quantum computing based community detection
- Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)
- Characterising the intersection of QMA and coQMA
- Quantum path computing: computing architecture with propagation paths in multiple plane diffraction of classical sources of fermion and boson particles
- Dynamical maps beyond Markovian regime
- On the concurrent composition of quantum zero-knowledge
- Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete
- A linear-algebraic and lattice-theoretical look at the Cleaning Lemma of quantum coding theory
- Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)
- Towards a multi target quantum computational logic
- Constant-round blind classical verification of quantum sampling
- A variational principle for ground spaces
- On efficiently solvable cases of quantum \(k\)-SAT
- Group theory on quantum Boltzmann machine
- Perturbation gadgets: arbitrary energy scales from a single strong interaction
- Error bounds for approximations with deep ReLU networks
- Extended learning graphs for triangle finding
- Verification of quantum computation: an overview of existing approaches
- QPCF: higher-order languages and quantum circuits
- Canonical forms for single-qutrit Clifford+\(T\) operators
- Quantum de Finetti theorems under local measurements with applications
- Realizations of standard quantum computational circuits by adiabatic evolution
- On the satisfiability of quantum circuits of small treewidth
- Complexity of quantum impurity problems
- Additivity of decoherence measures for multiqubit quantum systems
- On the hitting times of quantum versus random walks
- Everything you always wanted to know about LOCC (but were afraid to ask)
- Selecting efficient phase estimation with constant-precision phase shift operators
- On the power of quantum, one round, two prover interactive proof systems
- Typing in reflective combinatory logic
- Zeno machines and hypercomputation
- Termination orders for three-dimensional rewriting
- Universality and programmability of quantum computers
- Ergodic quantum computing
- Quantum and classical tradeoffs
- Quantum commitments from complexity assumptions
- Universal qudit Hamiltonians
- On the universality of the quantum approximate optimization algorithm
- Total functions in QMA
- Algebraic and quantum attacks on two digital signature schemes
- Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness
- Classical and quantum computing with C++ and Java simulations
- How quantum are non-negative wave functions?
- Complexity classification of local Hamiltonian problems
- Quantum 3-SAT Is QMA₁-complete
- Programmable Hamiltonian for one-way patterns
- Classically-controlled quantum computation
- Ground-state spaces of frustration-free Hamiltonians
- Complete Problem for Perfect Zero-Knowledge Quantum Proof
- A Surprisingly Simple Way of Reversing Trace Distance via Entanglement
- Positivity, discontinuity, finite resources, and nonzero error for arbitrarily varying quantum channels
- QMA with subset state witnesses
- Stronger methods of making quantum interactive proofs perfectly complete
- On quantum lambda calculi: a foundational perspective
- A short survey of quantum computing
- Quantum computing and second quantization
- Entanglement versus gap for one-dimensional spin systems
- Can a quantum computer run the von Neumann architecture?
- Quantum commitments from complexity assumptions
- Quantum computation vs. firewalls
- Quantum algorithms for algebraic problems
- scientific article; zbMATH DE number 1808097 (Why is no real title available?)
- On the satisfiability of quantum circuits of small treewidth
- Quantum locally testable codes
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- Commuting Pauli Hamiltonians as maps between free modules
- Book review of: Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing
- Impossibility of local state transformation via hypercontractivity
- Preparation of an arbitrary two-qubit quantum gate on two spins with an anisotropic Heisenberg interaction
- Simultaneous transmission of classical and quantum information under channel uncertainty and jamming attacks
- Generalized quantum Arthur-Merlin games
- scientific article; zbMATH DE number 6866233 (Why is no real title available?)
- Realizable Hamiltonians for universal adiabatic quantum computers
- Epsilon-net method for optimizations over separable states
- A complete characterization of unitary quantum space
- Boolean satisfiability in quantum compilation
- Approximate low-weight check codes and circuit lower bounds for noisy ground states
- On efficiently solvable cases of quantum k-SAT
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4544834)
