Rapid solution of problems by quantum computation

From MaRDI portal

Publication:4033175

Jump to:navigation, search

DOI10.1098/rspa.1992.0167zbMath0792.68058OpenAlexW2050334794WikidataQ55934567 ScholiaQ55934567MaRDI QIDQ4033175

David Deutsch, Richard Jozsa

Publication date: 16 May 1993

Published in: Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1098/rspa.1992.0167

zbMATH Keywords

quantum computation modes of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Multiparty multicast schemes for remote state preparation of complex coefficient quantum states via partially entangled channels ⋮ Renormalization of quantum coherence and quantum phase transition in the Ising model ⋮ Sure success partial search ⋮ NMR quantum information processing ⋮ Deterministic implementations of single-photon multi-qubit Deutsch-Jozsa algorithms with linear optics ⋮ Query complexity of unitary operation discrimination ⋮ Implementation of Deutsch and Deutsch-Jozsa-like algorithms involving classical entanglement of elastic bits ⋮ The ambiguity of simplicity in quantum and classical simulation ⋮ Succinct arguments in the quantum random oracle model ⋮ Optimal parallel quantum query algorithms ⋮ Efficient quantum algorithms related to autocorrelation spectrum ⋮ Quantum image processing? ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Controlling quantum coherence of a two-component Bose-Einstein condensate via an impurity atom ⋮ Coherence-based measure of quantumness in (non-) Markovian channels ⋮ Quantum algorithm for solving hyperelliptic curve discrete logarithm problem ⋮ Criteria for SLOCC and LU equivalence of generic multi-qudit states ⋮ Simulation of three-spin evolution under \(XX\) Hamiltonian on quantum processor of IBM-quantum experience ⋮ An exact quantum algorithm for a restricted subtraction game ⋮ Synthesis of Deutsch-Jozsa circuits and verification by IBM Q ⋮ Fault-tolerant quantum error correction code preparation in UBQC ⋮ Quantum abstract detecting systems ⋮ A low failure rate quantum algorithm for searching maximum or minimum ⋮ A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions ⋮ Quantum walks for the determination of commutativity of finite dimensional algebras ⋮ Generation and robustness of quantum entanglement in spin graphs ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ Quantum algorithms for the Goldreich-Levin learning problem ⋮ Decoherence of a two-level system in a coherent superposition of two dephasing environments ⋮ A novel three-party quantum secret sharing scheme based on Bell state sequential measurements with application in quantum image sharing ⋮ Relaxation process of a two-level system in a coherent superposition of two environments ⋮ A normal form for single-qudit Clifford+\(T\) operators ⋮ Contextuality-based quantum conferencing ⋮ Entanglement universality of TGX states in qubit-qutrit systems ⋮ Generalization of Deutsch's algorithm ⋮ Configurable sublinear circuits for quantum state preparation ⋮ On a poset of quantum exact promise problems ⋮ A generalisation of the phase kick-back ⋮ A new sure-success generalization of Grover iteration and its application to weight decision problem of Boolean functions ⋮ Quantum walks in an inhomogeneous off-diagonal Aubry-André-Harper model ⋮ Histogram-based segmentation of quantum images ⋮ A proposal for the realization of universal quantum gates via superconducting qubits inside a cavity ⋮ Space-bounded quantum complexity ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ Quantum computers and possible wavefunction collapse ⋮ Efficient protocol of \(N\)-bit discrete quantum Fourier transform via transmon qubits coupled to a resonator ⋮ An alternate quantum adiabatic evolution for the Deutsch-Jozsa problem ⋮ Non-local quantum functions and the distributed Deutsch-Jozsa algorithm ⋮ Non-classicality created by quantum channels with indefinite causal order ⋮ One-dimensional quantum walks with a time and spin-dependent phase shift ⋮ A quantum algorithm for a FULL adder operation based on registers of the CPU in a quantum-gated computer ⋮ Physics' evolution toward computing ⋮ Generalization and demonstration of an entanglement-based Deutsch-jozsa-like algorithm using a 5-qubit quantum computer ⋮ Finite-data-size study on practical universal blind quantum computation ⋮ A model of discrete quantum computation ⋮ Quantum Relief algorithm ⋮ X states of the same spectrum and entanglement as all two-qubit states ⋮ De-quantisation of the quantum Fourier transform ⋮ Models of quantum computation and quantum programming languages ⋮ Multipartite entanglement in Grover's search algorithm ⋮ Permutation symmetric hypergraph states and multipartite quantum entanglement ⋮ Improved bounds on quantum learning algorithms ⋮ A modified quantum adiabatic evolution for the Deutsch-Jozsa problem ⋮ Can von Neumann's theory meet the Deutsch-Jozsa algorithm? ⋮ Quantum algorithms know in advance 50\% of the Solution they will find in the future ⋮ On the mathematics of quantum computers ⋮ Implementation of Grover's search algorithm in the QED circuit for two superconducting qubits ⋮ Quantum pseudo-telepathy ⋮ Classical concepts in quantum programming ⋮ A relational time-symmetric framework for analyzing the quantum computational speedup ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Some theoretically organized algorithm for quantum computers ⋮ Query complexity of generalized Simon's problem ⋮ Quantum computing: survey and analysis ⋮ Quantification of Entanglement by Means of Convergent Iterations ⋮ Quantum algorithm for the root-finding problem ⋮ Quantum median filter for total variation image denoising ⋮ Quantum mappings and characterization of entangled quantum states ⋮ Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations ⋮ Quantum generative adversarial networks based on Rényi divergences ⋮ Directed graph encoding in quantum computing supporting edge-failures ⋮ Blind quantum machine learning based on quantum circuit model ⋮ Evaluation of exact quantum query complexities by semidefinite programming ⋮ Quantum algorithms for learning Walsh spectra of multi-output Boolean functions ⋮ Quantum cryptographic property testing of multi-output Boolean functions ⋮ Solving Bernstein and Vazirani's problem with the 2-bit permutation function ⋮ Quantum absentminded driver problem revisited ⋮ Combinatorial and rotational quantum abstract detecting systems ⋮ Deterministic algorithms for the hidden subgroup problem ⋮ Probability amplitude-encoded multichannel representation for quantum audio signals ⋮ Multipartite mixed maximally entangled states: mixed states with entanglement 1 ⋮ A fast quantum image encryption algorithm based on affine transform and fractional-order Lorenz-like chaotic dynamical system ⋮ An improved quantum algorithm for the quantum learning with errors problem ⋮ Double sparse quantum state preparation ⋮ On commutativity of discrete Fourier transform ⋮ On exact quantum query complexity ⋮ Quantum algorithm for learning secret strings and its experimental demonstration ⋮ A different Deutsch-Jozsa ⋮ Realization of quantum gates with multiple control qubits or multiple target qubits in a cavity ⋮ Design and implementation of MQIR image scaling ⋮ Physical quantum algorithms ⋮ Efficient quantum algorithms of finding the roots of a polynomial function ⋮ Application of Grover's algorithm to check non-resiliency of a Boolean function ⋮ A one-way function from thermodynamics and applications to cryptography ⋮ Highlighting the mechanism of the quantum speedup by time-symmetric and relational quantum mechanics ⋮ Milestone developments in quantum information and no-go theorems ⋮ Quantum computation with coherent spin states and the close Hadamard problem ⋮ Resolving the forecasting problems of overshoot and volatility clustering using ANFIS coupling nonlinear heteroscedasticity with quantum tuning ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables ⋮ Quantum coherence and geometric quantum discord ⋮ Role of coherence in adiabatic search algorithms ⋮ On the black-box complexity of Sperner's Lemma ⋮ The 50\% advanced information rule of the quantum algorithms ⋮ A quantum-inspired evolutionary algorithm using Gaussian distribution-based quantization ⋮ Creating very true quantum algorithms for quantum energy based computing ⋮ Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup ⋮ Fiber optics protocols for quantum communication ⋮ Do multipartite correlations speed up adiabatic quantum computation or quantum annealing? ⋮ Realization of a quantum gate using gravitational search algorithm by perturbing three-dimensional harmonic oscillator with an electromagnetic field ⋮ Quantum iSWAP gate in optical cavities with a cyclic three-level system ⋮ Hypothetical solution of the problem of measurement through the notion of quantum backward causality ⋮ Gaussian quantum computation with oracle-decision problems ⋮ Quantum computing without entanglement ⋮ New features of Wehrl entropy and Wehrl PD of a single Cooper-pair box placed inside a dissipative cavity ⋮ Optimal separation in exact query complexities for Simon's problem ⋮ Quantum algorithm to solve function inversion with time-space trade-off ⋮ Generating three-dimensional entanglement for atomic ensembles trapped in two separated cavity via an optical fiber ⋮ Resonant transition-based quantum computation ⋮ Quantum weakly nondeterministic communication complexity ⋮ Dynamic Grover search: applications in recommendation systems and optimization problems ⋮ Classification of Boolean functions by the invariants of their matrix representation ⋮ Quantum computation with classical light: the Deutsch algorithm ⋮ Quantum computer simulation using the CUDA programming model ⋮ Quantum pattern search with closed match ⋮ Complete deterministic analyzer for multi-electron Greenberger-Horne-Zeilinger states assisted by double-side optical microcavities ⋮ Quantum cryptography based on the Deutsch-Jozsa algorithm ⋮ A theoretical framework for quantum image representation and data loading scheme ⋮ A quantum probability splitter and its application to qubit preparation ⋮ Quantum algorithms for finding constant-sized sub-hypergraphs ⋮ On the simulation of quantum Turing machines. ⋮ An improved lower bound on query complexity for quantum PAC learning ⋮ Entanglement of the quantum system with spin-spin coupling created by optical excitation ⋮ Quantum correlations and decoherence dynamics for a qutrit-qutrit system under random telegraph noise ⋮ Berry phases and entanglement of a two spin-1/2 model with Dzyaloshinski-Moriya interaction in magnetic fields ⋮ Global multipartite entanglement dynamics in Grover's search algorithm ⋮ Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms ⋮ Decompositions of \(n\)-qubit Toffoli gates with linear circuit complexity ⋮ Quantum teleportation and Grover's algorithm without the wavefunction ⋮ Optimality proofs of quantum weight decision algorithms ⋮ Can quantum entanglement detection schemes improve search? ⋮ Realization of Deutsch-like algorithm using ensemble computing ⋮ On the entanglement and engineering phase gates without dynamical phases for a two-qubit system with Dzyaloshinski-Moriya interaction in magnetic field ⋮ A classical probability space exists for the measurement theory based on the truth values ⋮ Preparation of multi-party entanglement of individual photons and atomic ensembles ⋮ Scheme for probabilistic remotely preparing a \(d\)-dimensional equatorial quantum state ⋮ Quantum algorithm design: techniques and applications ⋮ Computation in finitary stochastic and quantum processes ⋮ Efficient quantum algorithms to construct arbitrary Dicke states ⋮ Quantum theory and determinism ⋮ Controllability and universal three-qubit quantum computation with trapped electron states ⋮ Circuit QED: implementation of the three-qubit refined Deutsch-Jozsa quantum algorithm ⋮ Determining the parity of a permutation using an experimental NMR qutrit ⋮ Interferometric computation beyond quantum theory ⋮ An exact quantum search algorithm with arbitrary database ⋮ A quantum algorithm for testing and learning resiliency of a Boolean function ⋮ Fourier 1-norm and quantum speed-up ⋮ Efficient quantum algorithm for the parity problem of a certain function ⋮ Quantum key distribution protocol based on modified generalization of Deutsch-Jozsa algorithm in \(d\)-level quantum system ⋮ Necessary and sufficient condition for quantum computing ⋮ Quantum communication based on an algorithm of determining a matrix ⋮ Quantum Boolean image denoising ⋮ Image segmentation on a quantum computer ⋮ Measurement theory in Deutsch's algorithm based on the truth values ⋮ Quantum walks: a comprehensive review ⋮ Environment assisted energy transfer in dimer system ⋮ Optimal processing of reversible quantum channels ⋮ The Deutsch-Jozsa problem: de-quantisation and entanglement ⋮ Fundamentals of quantum information theory ⋮ Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights ⋮ On the power of Ambainis lower bounds ⋮ A quantum computing primer for operator theorists ⋮ Quantum information processing, operational quantum logic, convexity, and the foundations of physics ⋮ New method of calculating a multiplication by using the generalized Bernstein-Vazirani algorithm ⋮ On the solution of trivalent decision problems by quantum state identification ⋮ An introduction to many worlds in quantum computation ⋮ Quantum zero-error algorithms cannot be composed ⋮ On the circuit model of global adiabatic search algorithm ⋮ A relation between fidelity and quantum adiabatic evolution ⋮ Consciousness: Computing the uncomputable ⋮ Reasoning about faulty quantum programs ⋮ From quantum cellular automata to quantum lattice gases ⋮ Quantum computation based on retarded and advanced propagation. ⋮ The Landauer resistance and band spectra for the counting quantum Turing machine. ⋮ Quantum communication and complexity. ⋮ Regular languages accepted by quantum automata ⋮ Modelling the brain processes of conscious states ⋮ The behavior of the two-level entangled atom in an optical field ⋮ Mathematical models of quantum computation ⋮ Computational complexity of uniform quantum circuit families and quantum Turing machines ⋮ Introducing nega-forrelation: quantum algorithms in analyzing nega-Hadamard and nega-crosscorrelation spectra ⋮ Comments on ``Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms ⋮ Quantum encoding of dynamic directed graphs ⋮ Quantum linearization attacks ⋮ Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations ⋮ Decoherence mitigation by embedding a logical qubit in a qudit ⋮ Evaluating three levels of quantum metrics on quantum-inspire hardware ⋮ A side-channel attack against \textit{Classic McEliece} when loading the Goppa polynomial ⋮ Quantum linear key-recovery attacks using the QFT ⋮ Distributed Grover's algorithm ⋮ Implementation of three-qubit Deutsch-Jozsa algorithm with pendular states of polar molecules by optimal control ⋮ Quantum algorithms for learning hidden strings with applications to matroid problems ⋮ An approach to the classification of finite semifields by quantum computing ⋮ QuantQueryEXP : A novel strategic approach for query expansion based on quantum computing principles ⋮ Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies ⋮ An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Unnamed Item ⋮ Quantum information and correlation bounds ⋮ A public key cryptosystem based on data complexity under quantum environment ⋮ QUANTUM STATE TOMOGRAPHY AND QUANTUM LOGICAL OPERATIONS IN A THREE QUBITS NMR QUADRUPOLAR SYSTEM ⋮ DE-QUANTIZING THE SOLUTION OF DEUTSCH'S PROBLEM ⋮ Quantum circuits of $ \newcommand{\cZ}{c-\mathtt{Z}} \cZ$ and $ \newcommand{\Swap}{\mathtt{SWAP}} \Swap$ gates: optimization and entanglement ⋮ QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT ⋮ GEOMETRIC PHASES AND TOPOLOGICAL QUANTUM COMPUTATION ⋮ On Deciding Whether a Boolean Function is Constant or Not ⋮ D-Wave and predecessors: From simulated to quantum annealing ⋮ Trading quantum for classical resources in quantum data compression ⋮ Natural Quantum Operational Semantics with Predicates ⋮ From Quantum Query Complexity to State Complexity ⋮ Classical and Quantum Counter Automata on Promise Problems ⋮ Potential of Quantum Finite Automata with Exact Acceptance ⋮ Entanglement witness and multipartite quantum state discrimination ⋮ Distributed Bernstein-Vazirani algorithm ⋮ Following forrelation -- quantum algorithms in exploring Boolean functions' spectra ⋮ A family of unitaries for the quantum period finding algorithm ⋮ ON THE NON-EXISTENCE OF A UNIVERSAL HADAMARD GATE ⋮ Interference as a computational resource: a tutorial ⋮ Rapid solution of problems by quantum computation ⋮ Variable ansatz applied to spectral operator decomposition in a physical superconducting quantum device ⋮ Performance of Grover's search algorithm with diagonalizable collective noises ⋮ A generalization of Bernstein-Vazirani algorithm with multiple secret keys and a probabilistic oracle ⋮ Application of quantum approximate optimization algorithm to job shop scheduling problem ⋮ A quantum algorithm to approximate the linear structures of Boolean functions ⋮ Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$ ⋮ Linear-algebraic λ-calculus: higher-order, encodings, and confluence. ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ Unnamed Item ⋮ Fidelity-optimized quantum state estimation ⋮ A classical limit of Grover’s algorithm induced by dephasing: Coherence versus entanglement ⋮ THE DEUTSCH–JOZSA ALGORITHM REVISITED IN THE DOMAIN OF CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS ⋮ An Introduction to Quantum Computing, without the Physics ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES ⋮ Quantum hypergraph states ⋮ A strategy for quantum algorithm design assisted by machine learning ⋮ Signal-based classical emulation of a universal quantum computer ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Quantum Pushdown Automata with Garbage Tape ⋮ Design of quantum Fourier transforms and quantum algorithms by using circulant Hamiltonians ⋮ MULTI-COMPONENT SQUEEZED COHERENT STATE FOR N TRAPPED IONS IN ANY POSITION OF A STANDING WAVE ⋮ THEORETICAL AND EXPERIMENTAL ASPECTS OF QUANTUM DISCORD AND RELATED MEASURES ⋮ Matchgates and classical simulation of quantum circuits ⋮ NMR Quantum Computing ⋮ Revisiting the simulation of quantum Turing machines by quantum circuits ⋮ One-Qubit and Two-Qubit Codes in Noisy State Transfer ⋮ ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM ⋮ Quantum Algorithms Related to $$\textit{HN}$$ -Transforms of Boolean Functions ⋮ Counting by quantum eigenvalue estimation ⋮ MAXIMALLY ENTANGLED STATES FOR MANY TRAPPED IONS FROM SINGLE RESONANT INTERACTIONS ⋮ Unnamed Item ⋮ ENTANGLEMENT AND INFORMATION TRANSFER PROTOCOL BETWEEN TWO QUBITS ⋮ Analogies and differences between quantum and stochastic automata ⋮ Quasiclassical computation ⋮ Dispelling myths on superposition attacks: formal security model and attack analyses ⋮ Quantum algorithms for algebraic problems ⋮ Information and computation: Classical and quantum aspects ⋮ Quantum computation and quantum information† ⋮ A NEW PARAMETER OF ENTANGLEMENT FOR A QUBIT SYSTEM PLACED INSIDE A DISSIPATIVE CAVITY ⋮ A quantum speedup in machine learning: finding anN-bit Boolean function for a classification ⋮ EXTRACTION OF VALUE OF FUNCTION f(x) IN DEUTSCH ALGORITHM AND DEUTSCH–JOZSA ALGORITHM ⋮ DELETING A MARKED BASIS-STATE FROM AN EVEN SUPERPOSITION OF ALL BASIS-STATES WITH A SINGLE QUERY ⋮ Quantum-enhanced deliberation of learning agents using trapped ions ⋮ TELEPORTING N ROTATIONS ONTO N REMOTE QUBITS BY AN ENTANGLED QUDIT CHANNEL ⋮ Quantum Queries on Permutations with a Promise ⋮ Implementation of the Deutsch-Jozsa algorithm with Josephson charge qubits ⋮ Three-qubit network with a single trapped electron ⋮ Fast quantum modular exponentiation ⋮ NMR tomography of the three-qubit Deutsch-Jozsa algorithm ⋮ Fiber-Optics Implementation of the Deutsch-Jozsa and Bernstein-Vazirani Quantum Algorithms with Three Qubits ⋮ Experimental Realization of Deutsch’s Algorithm in a One-Way Quantum Computer ⋮ Deutsch-Jozsa Algorithm Using Triggered Single Photons from a Single Quantum Dot ⋮ Entanglement is Not Necessary for Perfect Discrimination between Unitary Operations ⋮ HADAMARD TYPE OPERATIONS FOR QUBITS ⋮ Generation of elementary gates and Bell’s states using controlled adiabatic evolutions ⋮ Quantum Queries on Permutations ⋮ Coherence makes quantum systems ‘magical’ ⋮ An Application of the Deutsch-Jozsa Algorithm to Formal Languages and the Word Problem in Groups ⋮ Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation ⋮ Quadrature squeezing of a mechanical resonator generated by the electromechanical coupling with two coupled quantum dots ⋮ Necessary and Sufficient Conditions for Quantum Computation ⋮ Quantum Perceptrons ⋮ Nanostructures, Entanglement and the Physics of Quantum Control ⋮ Oracle Quantum Computing ⋮ Information Exclusion Principle for Complementary Observables ⋮ Demonstration of a Fundamental Quantum Logic Gate ⋮ Quantum computing: beyond the limits of conventional computation† ⋮ PREPARATION AND STORAGE OF ENTANGLED STATES FOR MULTIPLE TRAPPED IONS IN THERMAL MOTION ⋮ Extending the Promise of the Deutsch–Jozsa–Høyer Algorithm for Finite Groups ⋮ Testing Boolean Functions Properties ⋮ The physics of quantum computation ⋮ Lattice structure based metric for feature data fusion ⋮ The information role of entanglement and interference operators in Shor quantum algorithm gate dynamics

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:4033175&oldid=17750434"