Strengths and Weaknesses of Quantum Computing
From MaRDI portal
Publication:4376184
DOI10.1137/S0097539796300933zbMath0895.68044arXivquant-ph/9701001OpenAlexW2006290558WikidataQ29544927 ScholiaQ29544927MaRDI QIDQ4376184
Gilles Brassard, Ethan Bernstein, Umesh V. Vazirani, Charles H. Bennett
Publication date: 10 February 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/9701001
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)
Related Items
Challenges of adiabatic quantum evaluation of NAND trees, Dynamical analysis of Grover's search algorithm in arbitrarily high-dimensional search spaces, New approaches for quantum copy-protection, Quantum de Finetti theorems under local measurements with applications, A lower bound on the quantum query complexity of read-once functions, Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics, On the quantum query complexity of local search in two and three dimensions, On the black-box complexity of Sperner's Lemma, Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup, Quest for fast partial search algorithm, The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries, An \(R||C_{\max}\) quantum scheduling algorithm, Progress in quantum algorithms, Robust quantum spatial search, Layering quantum-resistance into classical digital signature algorithms, Improving quantum query complexity of Boolean matrix multiplication using graph collision, Quantum search with certainty based on modified Grover algorithms: optimum choice of parameters, Multi-party quantum key agreement protocol for detection of collusive attacks in each sub-circle segment by headers, PKP-based signature scheme, Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device, Quantum entanglement and the communication complexity of the inner product function, Approximate span programs, Finding shortest lattice vectors faster using quantum search, An oracle builder's toolkit, On the simulation of quantum Turing machines., Quantum multi-prover interactive proof systems with limited prior entanglement., A review on quantum search algorithms, Quantum speed-up for unsupervised learning, Quantum search in a possible three-dimensional complex subspace, Can quantum entanglement detection schemes improve search?, Tree search and quantum computation, A new sure-success generalization of Grover iteration and its application to weight decision problem of Boolean functions, Intricacies of quantum computational paths, Evolutionary algorithms for quantum computers, Is Hilbert space discrete?, New quantum algorithm for studying NP-complete problems, Complexity limitations on quantum computation, Noise-based logic hyperspace with the superposition of \(2^N\) states in a single wire, Quantum algorithm for SAT problem andquantum mutual entropy, Using quantum key distribution for cryptographic purposes: a survey, The Python's lunch: geometric obstructions to decoding Hawking radiation, A universal quantum circuit scheme for finding complex eigenvalues, Quantum algorithm design: techniques and applications, The quadratic speedup in Grover's search algorithm from the entanglement perspective, A new hybrid classical-quantum algorithm for continuous global optimization problems, Entanglement in the Grover search algorithm, Oracles and query lower bounds in generalised probabilistic theories, Quantum partial search of a database with several target items, An exact quantum search algorithm with arbitrary database, On the obfuscatability of quantum point functions, A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function, Quantum mechanical search and harmonic perturbation, A modified quantum search algorithm, Coloring invariants of knots and links are often intractable, Quantum pattern matching fast on average, Szegedy's quantum walk with queries, Quantum finite automata: advances on Bertoni's ideas, Quantum partial search for uneven distribution of multiple target items, On the role of dealing with quantum coherence in amplitude amplification, Controlled quantum search, Quantum certificate complexity, New quantum algorithm solving the NP complete problem, Spatial search using the discrete time quantum walk, Quantum and classical complexity classes: Separations, collapses, and closure properties, A desired state can not be found with certainty for Grover's algorithm in a possible three-dimensional complex subspace, \texttt{QUCON}: a fast Krylov-Newton code for dipole quantum control problems, Polynomial degree vs. quantum query complexity, Improved bounds on quantum learning algorithms, On the complexity of searching for a maximum of a function on a quantum computer, An optical model of computation, A quantum computer only needs one universe, The geometry of quantum learning, A relational time-symmetric framework for analyzing the quantum computational speedup, On the solution of trivalent decision problems by quantum state identification, Quantum approaches to graph colouring, A new connection between quantum circuits, graphs and the Ising partition function, Quantum-access-secure message authentication via blind-unforgeability, On the compressed-oracle technique, and post-quantum security of proofs of sequential work, Towards quantum computing based community detection, Key establishment à la Merkle in a quantum world, Diagonalization of diffusion matrix in Grover's algorithm, Quantum search on structured problems, Quantum lower bounds for the Goldreich-Levin problem, Quantum computers and unstructured search: finding and counting items with an arbitrarily entangled initial state, Quantum branch-and-bound algorithm and its application to the travelling salesman problem, Discrete quantum walks hit exponentially faster, Dynamic multi-party quantum key agreement protocol based on commutative encryption, The Landauer resistance and band spectra for the counting quantum Turing machine., The variational quantum eigensolver: a review of methods and best practices, Computing with quanta -- impacts of quantum theory on computation., Quantum communication and complexity., Searching a database under decoherence, Evaluation of exact quantum query complexities by semidefinite programming, Entanglement measures of a pentapartite W-class state in the noninertial frame, Quantum search degeneration under amplitude noise in queries to the oracle, Mathematical models of quantum computation, Computational complexity of uniform quantum circuit families and quantum Turing machines, One complexity theorist's view of quantum computing, Quantum commitments from complexity assumptions, Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms, A Quantum Parallel Markov Chain Monte Carlo, Quantum linear key-recovery attacks using the QFT, Distributed Grover's algorithm, An approach to the classification of finite semifields by quantum computing, A public key cryptosystem based on data complexity under quantum environment, Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas, Fast Discretized Gaussian Sampling and Post-quantum TLS Ciphersuite, Approximate Degree in Classical and Quantum Computing, QUANTUM SEARCH ALGORITHMS, Quantum machine learning: a classical perspective, QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS, Quantum simulation from the bottom up: the case of rebits, Forrelation: A Problem That Optimally Separates Quantum from Classical Computing, A fast algorithm for approximating the ground state energy on a quantum computer, Quantum lightning never strikes the same state twice. Or: quantum money from cryptographic assumptions, Quantum Distributed Computing Applied to Grover’s Search Algorithm, On a neural network approach for solving potential control problem of the semiclassical Schrödinger equation, Quantum Walk Based Search Algorithms, Rapid solution of problems by quantum computation, Classical and quantum algorithms for constructing text from dictionary problem, Borel complexity and Ramsey largeness of sets of oracles separating complexity classes, Super-quantum discord in ferromagnetic and antiferromagnetic materials, Quantum bounds for 2D-grid and Dyck language, On the feasibility of unclonable encryption, and more, Phase shift and multi-controlled \(Z\)-type gates, N-partite entanglement measures of GHZ states in a non-inertial frame, Quantum impossible differential attacks: applications to AES and SKINNY, Total functions in QMA, Abnormal Quantum State Search Based on Parallel Phase Comparison, Black-box separations for non-interactive classical commitments in a quantum world, VERIFIER-BASED ALGORITHM FOR UNSORTED DATABASE SEARCH PROBLEM, Quantum algorithm for lexicographically minimal string rotation, Redeeming reset indifferentiability and applications to post-quantum security, QCB: efficient quantum-secure authenticated encryption, Optimal fixed-point quantum search in an interacting Ising spin system, Quantum counterfactuality with identical particles, The parallel reversible pebbling game: analyzing the post-quantum security of iMHFs, Near-optimal quantum algorithms for string problems, Non-Boolean quantum amplitude amplification and quantum mean estimation, Implementation of efficient quantum search algorithms on NISQ computers, Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness, Improved classical and quantum algorithms for subset-sum, Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems, Unnamed Item, HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL, Unnamed Item, The quantum walk search algorithm: factors affecting efficiency, Effects of dissipation on an adiabatic quantum search algorithm, Quantum Query Algorithms are Completely Bounded Forms., A classical limit of Grover’s algorithm induced by dephasing: Coherence versus entanglement, An Introduction to Quantum Computing, without the Physics, ANALYSIS OF QUANTUM FUNCTIONS, QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES, Fault-ignorant quantum search, Computational complexity of time-dependent density functional theory, A geometric approach to quantum state separation, Quantum Query Algorithms Are Completely Bounded Forms, Quantum lower bounds by quantum arguments, Quantum and classical query complexities of local search are polynomially related, Search on a hypercubic lattice using a quantum random walk. I.<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mrow><mml:mi>d</mml:mi><mml:mo>></mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math>, Faster quantum-walk algorithm for the two-dimensional spatial search, Exact quantum search by parallel unitary discrimination schemes, Product formulas for exponentials of commutators, Language Classes Defined by Generalized Quantum Turing Machine, Microstate distinguishability, quantum complexity, and the eigenstate thermalization hypothesis, ON THE GAP OF HAMILTONIANS FOR THE ADIABATIC SIMULATION OF QUANTUM CIRCUITS, QUANTUM SEARCH ALGORITHM CAN BE IMPROVED, Counting by quantum eigenvalue estimation, Quantum simulations of classical random walks and undirected graph connectivity, Quantum associative memory with distributed queries, Decoherence in quantum walks – a review, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Spatial search on a honeycomb network, Analogies and differences between quantum and stochastic automata, Post-Quantum Cryptography: State of the Art, Quantum algorithms for algebraic problems, Information and computation: Classical and quantum aspects, The role of relative entropy in quantum information theory, Quantum computation and quantum information†, Theory of Quantum Computation and Philosophy of Mathematics. Part II, Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer, Random matrix model of adiabatic quantum computing, Lower bound for quantum phase estimation, Algebraic analysis of quantum search with pure and mixed states, Quantum computing and hidden variables, Spatial search and the Dirac equation, Multiobjective Optimization Grover Adaptive Search, Unnamed Item, RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC, Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure, Quantum Algorithms for Evaluating Min-Max Trees, Cryptography Based on Quadratic Forms: Complexity Considerations, Deriving Grover's lower bound from simple physical principles, Quantum and classical tradeoffs, Universal test for quantum one-way permutations, SIMULATION OF QUANTUM ADIABATIC SEARCH IN THE PRESENCE OF NOISE, On the efficiency of Hamiltonian-based quantum computation for low-rank matrices, An upper bound on the rate of information transfer by Grover's oracle, First-order quantum phase transitions as condensations in the space of states, Computation in a general physical setting
