scientific article; zbMATH DE number 1776257

A. Kh. Shen', Mikhail N. Vyalyi, Alexei Yu. Kitaev

Publication date: 5 August 2002

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

computational complexity quantum algorithms quantum computation complexity classes Boolean circuits quantum codes quantum circuits Abelian hidden subgroup problem quantum NP-completeness

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to quantum theory (81-02) Other types of codes (94B60) Complexity of computation (including implicit computational complexity) (03D15) 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)

Related Items

Calculable lower bounds on the efficiency of universal sets of quantum gates, Decay of quantum conditional mutual information for purely generated finitely correlated states, Ground State Connectivity of Local Hamiltonians, Quantum Locally Testable Codes, Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas, Derivation of the robustness from the concurrence, The tunable 0−π qubit: Dynamics and relaxation, On the Satisfiability of Quantum Circuits of Small Treewidth, Undecidability of the Spectral Gap, Classical Verification of Quantum Computations, Complexity limitations on one-turn quantum refereed games, An empirical study of quantum dynamics as a ground state problem with neural quantum states, On the universality and membership problems for quantum gates, Continuous theory of operator expansions of finite dimensional Hilbert spaces and decidability, Thermalization in Kitaev’s quantum double models via tensor network techniques, Quantum probability: a reliable tool for an agent or a reliable source of reality?, Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture, Quantity study on a novel quantum neural network with alternately controlled gates for binary image classification, Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability, Hay from the haystack: explicit examples of exponential quantum circuit complexity, Analytical complexity and signal coding, Geometric algebras of light cone projective graph geometries, Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates, Unnamed Item, The face lattice of the set of reduced density matrices and its coatoms, Unnamed Item, Structured filtering, Fidelity and Fisher information on quantum channels, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Approximation algorithms for quantum many-body problems, Preparation of an arbitrary two-qubit quantum gate on two spins with an anisotropic Heisenberg interaction, Topological quantum gate construction by iterative pseudogroup hashing, The BQP-hardness of approximating the Jones polynomial, Universal quantum computation by scattering in the Fermi–Hubbard model, Quantum-circuit design for efficient simulations of many-body quantum dynamics, Faster quantum chemistry simulation on fault-tolerant quantum computers, A Complete Characterization of Unitary Quantum Space, Simultaneous transmission of classical and quantum information under channel uncertainty and jamming attacks, Quantum circuit design for accurate simulation of qudit channels, Computational complexity of time-dependent density functional theory, Generalized Quantum Arthur--Merlin Games, Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians, RELATIVIZED GENERIC CLASSES P AND NP, Imaginary groups: lazy monoids and reversible computation, Realizable Hamiltonians for universal adiabatic quantum computers, Product formulas for exponentials of commutators, Revisiting the simulation of quantum Turing machines by quantum circuits, Vortex loops and Majoranas, DIAGONAL-UNITARY 2-DESIGN AND THEIR IMPLEMENTATIONS BY QUANTUM CIRCUITS, Unitary 2-designs from random X- and Z-diagonal unitaries, Unnamed Item, Unnamed Item, General Properties of Quantum Zero-Knowledge Proofs, Product-state approximations to quantum states, How does adiabatic quantum computation fit into quantum automata theory?, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, Krotov method for optimal control of closed quantum systems, Boolean satisfiability in quantum compilation, Ground state entanglement in one-dimensional translationally invariant quantum systems, Fast universal quantum computation with railroad-switch local Hamiltonians, Time independent universal computing with spin chains: quantum plinko machine, Optimal quantum networks and one-shot entropies, A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY, Unnamed Item, QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge, Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians, Hand-waving and interpretive dance: an introductory course on tensor networks, On the concurrent composition of quantum zero-knowledge, Quantum de Finetti theorems under local measurements with applications, Complete Problem for Perfect Zero-Knowledge Quantum Proof, Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete, Realizations of standard quantum computational circuits by adiabatic evolution, A Surprisingly Simple Way of Reversing Trace Distance via Entanglement, Quantum computation vs. firewalls, The power of quantum systems on a line, 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, Multiplicativity of completely bounded $p$-norms implies a new additivity result, Constant-round blind classical verification of quantum sampling, Universal qudit Hamiltonians, Optimal separation in exact query complexities for Simon's problem, Computational complexity of the landscape. I., Positivity, discontinuity, finite resources, and nonzero error for arbitrarily varying quantum channels, Commuting Pauli Hamiltonians as maps between free modules, On the satisfiability of quantum circuits of small treewidth, Complexity of quantum impurity problems, Cohering power of quantum operations, QMA with Subset State Witnesses, Erratum to: Quantum tasks in holography, The complexity of translationally invariant spin chains with low local dimension, Quantum computation with Turaev-Viro codes, Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete, Quantum capacity under adversarial quantum noise: arbitrarily varying quantum channels, On the universality of the quantum approximate optimization algorithm, Quantum algorithms for finding constant-sized sub-hypergraphs, Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes, A variational principle for ground spaces, Total functions in QMA, Additivity of decoherence measures for multiqubit quantum systems, An improved lower bound on query complexity for quantum PAC learning, On the hitting times of quantum versus random walks, Algebraic and quantum attacks on two digital signature schemes, Experimentally feasible measures of distance between quantum operations, Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness, 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, Book review of: Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Impossibility of local state transformation via hypercontractivity, Replica procedure for probabilistic algorithms as a model of gene duplication, On efficiently solvable cases of quantum $k$-SAT, Everything you always wanted to know about LOCC (but were afraid to ask), Selecting efficient phase estimation with constant-precision phase shift operators, Skein theory and topological quantum registers: Braiding matrices and topological entanglement entropy of non-Abelian quantum Hall states, Can a Quantum Computer Run the von Neumann Architecture?, Group theory on quantum Boltzmann machine, Epsilon-net method for optimizations over separable states, On the power of quantum, one round, two prover interactive proof systems, Local random quantum circuits are approximate polynomial-designs, On complexity of the quantum Ising model, Braiding flux-tubes in topological quantum and classical lattice models from class-D, Quantum Commitments from Complexity Assumptions, Simulation of a multidimensional input quantum perceptron, Shorter unentangled proofs for ground state connectivity, A model of discrete quantum computation, Ancilla dimension in quantum channel discrimination, Comparison between the Cramer-Rao and the mini-max approaches in quantum channel estimation, Remarks on geometric quantum mechanics, 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, Typing in reflective combinatory logic, Quantum branching programs and space-bounded nonuniform quantum complexity, How quantum are non-negative wavefunctions?, Zeno machines and hypercomputation, Adiabatic quantum counting by geometric phase estimation, Termination orders for three-dimensional rewriting, Complexity Classification of Local Hamiltonian Problems, Perturbation gadgets: arbitrary energy scales from a single strong interaction, Error bounds for approximations with deep ReLU networks, Universality and programmability of quantum computers, Prime witnesses in the Shor algorithm and the Miller-Rabin algorithm, Quantum algorithms for algebraic problems, Extended learning graphs for triangle finding, Quantum zero-error algorithms cannot be composed, Query complexity of generalized Simon's problem, Quantum 3-SAT Is QMA$_1$-Complete, Classical proofs of quantum knowledge, Programmable Hamiltonian for One-way Patterns, Verification of quantum computation: an overview of existing approaches, Towards quantum computing based community detection, Claw finding algorithms using quantum walk, Classical and quantum function reconstruction via character evaluation, The ghost in the radiation: robust encodings of the black hole interior, QPCF: higher-order languages and quantum circuits, Random quantum circuits are approximate 2-designs, Entanglement transmission and generation under channel uncertainty: universal quantum channel coding, Quantum generalizations of the polynomial hierarchy with applications to $\mathrm{QMA(2)}$, Canonical forms for single-qutrit Clifford+$T$ operators, Ergodic quantum computing, Quantum and classical tradeoffs, 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, Ground-state spaces of frustration-free Hamiltonians, Dynamical maps beyond Markovian regime, Quantum commitments from complexity assumptions