Deutsch–Jozsa algorithm
The Deutsch–Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998.[1][2] Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm.[3] The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm.It is a black box problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need an exponential number of queries to the black box to solve the problem.More formally, it yields an oracle relative to which EQP, the class of problems that can be solved exactly in polynomial time on a quantum computer, and P are different.[4] Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with BPP, the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer.In the Deutsch–Jozsa problem, we are given a black box quantum computer known as an oracle that implements some function:is constant, just over half the set of inputs must be evaluated and their outputs found to be identical (because the function is guaranteed to be either balanced or constant, not somewhere in between).The best case occurs where the function is balanced and the first two output values are different.evaluations of the function suffices to produce the correct answer with a high probability (failing with probabilityevaluations are still required if we want an answer that has no possibility of error.The Deutsch-Jozsa quantum algorithm produces an answer that is always correct with a single evaluation ofThe Deutsch–Jozsa algorithm generalizes earlier (1985) work by David Deutsch, which provided a solution for the simple case whereSpecifically, given a Boolean function whose input is one bit,[5] The algorithm, as Deutsch had originally proposed it, was not deterministic.In 1992, Deutsch and Jozsa produced a deterministic algorithm which was generalized to a function which takesFurther improvements to the Deutsch–Jozsa algorithm were made by Cleve et al.,[2] resulting in an algorithm that is both deterministic and requires only a single query of[2] For the Deutsch–Jozsa algorithm to work, the oracle computingThe point of view of the Deutsch-Jozsa algorithm ofA Hadamard gate is applied to each bit to obtain the state whereThe oracle maps its input stateTesting these two possibilities, we see the above state is equal to At this point the last qubitmay be ignored and the following remains: Next, we will have each qubit go through a Hadamard gate.is addition modulo 2, which can also be viewed as a quantum XOR gate implemented as a Controlled NOT gate), if zero, thenBelow is a simple example of how the Deutsch–Jozsa algorithm can be implemented in Python using Qiskit, an open-source quantum computing software development framework by IBM.We will walk through each part of the code step by step to show how it translates the theory into a working quantum circuit.We use Qiskit’s core elements: We run the circuit using Aer’s built-in aer_simulator.Because the Deutsch–Jozsa algorithm only needs one execution (one set of shots) to distinguish between constant and balanced with 100% certainty, running multiple shots will always yield the same outcome.Classically, you might have to “call” the function (f) (our “mystery” black box) many times—potentially up toAlthough Deutsch–Jozsa itself is considered more of a “teaching example” than a practical application, it demonstrates one of the key ideas of quantum algorithms: leveraging superposition and interference to reduce the number of required function calls dramatically.
deterministicquantum algorithmDavid DeutschRichard JozsaRichard CleveArtur EkertMichele Moscaexponentially fasterblack boxSimon's problemoraclepromisedconstantdomainrandomized algorithmBoolean functiondecohereno cloning theoremquantum circuitconstructive interferencedestructive interferenceXOR gateControlled NOT gateQiskittranspileBernstein–Vazirani algorithmBibcodeCiteSeerXQuantum information scienceDiVincenzo's criteriaNISQ eraQuantum computingtimelineQuantum informationQuantum programmingQuantum simulationphysical vs. logicalQuantum processorscloud-basedBell'sEastin–KnillGleason'sGottesman–KnillHolevo'sNo-broadcastingNo-cloningNo-communicationNo-deletingNo-hidingNo-teleportationQuantum speed limitThresholdSolovay–KitaevPurificationClassical capacityentanglement-assistedquantum capacityEntanglement distillationMonogamy of entanglementQuantum channelquantum networkQuantum teleportationquantum gate teleportationSuperdense codingQuantum cryptographyPost-quantum cryptographyQuantum coin flippingQuantum moneyQuantum key distributionSARG04other protocolsQuantum secret sharingQuantum algorithmsAmplitude amplificationBernstein–VaziraniBoson samplingGrover'sHidden subgroupQuantum annealingQuantum countingQuantum Fourier transformQuantum optimizationQuantum phase estimationShor'sSimon'sQuantumcomplexity theoryPostBQPQuantum supremacyQuantum volumeRandomized benchmarkingRelaxation timescomputing modelsAdiabatic quantum computationContinuous-variable quantum informationOne-way quantum computercluster statequantum logic gateQuantum machine learningquantum neural networkQuantum Turing machineTopological quantum computerQuantumerror correctionquantum convolutionalstabilizerBacon–ShorSteaneQuantum opticsCavity QEDCircuit QEDLinear optical QCKLM protocolUltracold atomsNeutral atom QCTrapped-ion QCKane QCSpin qubit QCNV centerNMR QCSuperconductingCharge qubitFlux qubitPhase qubitTransmonQuantumprogrammingOpenQASMIBM QX