Quantum Complexity Theory
From MaRDI portal
Publication:4376183
DOI10.1137/S0097539796300921zbMATH Open0895.68042DBLPjournals/siamcomp/BernsteinV97WikidataQ55878430 ScholiaQ55878430MaRDI QIDQ4376183FDOQ4376183
Authors: Ethan Bernstein, Umesh V. Vazirani 
Publication date: 10 February 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
reversibilityquantum computationquantum Turing machinesFourier samplingquantum polynomial timeuniversal quantum Turing machine
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Cited In (only showing first 100 items - show all)
- On the impossibility of interaction-free quantum sensing for small I/O bandwidth
- Blind quantum machine learning based on quantum circuit model
- Mathematical models of quantum computation
- Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
- Martin-Löf random quantum states
- Complexity of operators generated by quantum mechanical Hamiltonians
- Simplified proof of the Fourier sampling theorem
- Quantum algorithm design: techniques and applications
- A full characterization of quantum advice
- Universality of quantum Turing machines with deterministic control
- An exact quantum algorithm for the 2-junta problem
- Necessary and sufficient condition for quantum computing
- Quantum communication based on an algorithm of determining a matrix
- Temporally unstructured quantum computation
- Classical simulation complexity of quantum machines.
- Quantum algorithm for determining a complex number string
- On a measurement-free quantum lambda calculus with classical control
- A quantum algorithm for a FULL adder operation based on registers of the CPU in a quantum-gated computer
- Quantum algorithm for the root-finding problem
- Kochen-Specker theorem as a precondition for quantum computing
- Hypercomputation with quantum adiabatic processes
- Computational Complexity of Quantum Satisfiability
- Almost-everywhere superiority for quantum polynomial time
- Creating very true quantum algorithms for quantum energy based computing
- Measurement-Based and Universal Blind Quantum Computation
- The space ``just above BQP
- Prefix-free quantum Kolmogorov complexity
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- An introduction to quantum annealing
- Human rationality challenges universal logic
- Nonadaptive quantum query complexity
- An introduction to quantum computing, without the physics
- Efficient quantum algorithm for the parity problem of a certain function
- Quantum machine learning: a classical perspective
- Quantum Hamiltonian Complexity
- An improved lower bound on query complexity for quantum PAC learning
- Title not available (Why is that?)
- Quantum arithmetic with the quantum Fourier transform
- The complexity of translationally invariant spin chains with low local dimension
- Architecture of a deterministic quantum central processing unit
- Towards quantum computing based community detection
- Multi-party quantum key agreement protocol for detection of collusive attacks in each sub-circle segment by headers
- Title not available (Why is that?)
- Revisiting the simulation of quantum Turing machines by quantum circuits
- Distributed Bernstein-Vazirani algorithm
- An improved filtering method for quantum color image in frequency domain
- Quantum matchgate computations and linear threshold gates
- A structured view on weighted counting with relations to counting, quantum computation and applications
- Quantum random access stored-program machines
- Quantum-walk speedup of backtracking algorithms
- A classical probability space exists for the measurement theory based on the truth values
- Nondeterministic finite automata based on quantum logic: language equivalence relation and robustness
- On using probabilistic Turing machines to model participants in cryptographic protocols
- Superiority of exact quantum automata for promise problems
- Quantum computing and quadratically signed weight enumerators
- The quantum ultimatum game
- Title not available (Why is that?)
- Polynomial time quantum computation with advice
- A search for quantum coin-flipping protocols using optimization techniques
- Quantum computing, postselection, and probabilistic polynomial-time
- A new universal and fault-tolerant quantum basis
- Unbounded-error quantum computation with small space bounds
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Quantum Boolean image denoising
- Trace monoids with idempotent generators and measure-only quantum automata
- On exact quantum query complexity
- Undecidability of the Spectral Gap
- Quantum simulations of classical random walks and undirected graph connectivity
- Classically controlled quantum computation
- Quantum Kolmogorov complexity
- The query complexity of order-finding
- A theoretical framework for quantum image representation and data loading scheme
- THE DEUTSCH–JOZSA ALGORITHM REVISITED IN THE DOMAIN OF CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS
- Quantum communication and complexity.
- Partial observation of quantum Turing machines and a weaker well-formedness condition
- Automata theory based on quantum logic: Some characterizations
- Complexity limitations on quantum computation
- Computational Depth Complexity of Measurement-Based Quantum Computation
- The quantum query complexity of learning multilinear polynomials
- Automata theory based on complete residuated lattice-valued logic: Turing machines
- An Optimal Separation of Randomized and Quantum Query Complexity
- Entropy and algorithmic complexity in quantum information theory
- Another approach to the equivalence of measure-many one-way quantum finite automata and its application
- Computational complexity and applications of quantum algorithm
- Exact results for accepting probabilities of quantum automata.
- Quantum algorithmic complexities and entropy
- Note on a universal quantum Turing machine
- The geometry of quantum learning
- Hierarchy and equivalence of multi-letter quantum finite automata
- Representation-theoretical properties of the approximate quantum Fourier transform
- Quantum branching programs and space-bounded nonuniform quantum complexity
- A note on quantum sequential machines
- Determination of equivalence between quantum sequential machines
- Determining the equivalence for one-way quantum finite automata
- Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
- Some formal tools for analyzing quantum automata.
- Computing spin networks
- Efficient discrete approximations of quantum gates
- Quantum computers that can be simulated classically in polynomial time
- Histogram-based segmentation of quantum images
This page was built for publication: Quantum Complexity Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376183)
