.. _sphx_glr_api_gallery_quantum_quantum_computing:

Quantum computing
-----------------

A state-vector circuit simulator running the first quantum algorithms:
Deutsch-Jozsa's one-query test, the quantum Fourier transform behind
Shor's period finding, and Grover's square-root search.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="David Deutsch (1985) asked whether a computer obeying quantum mechanics could do something no classical one can. With Richard Jozsa (1992) he gave the first problem with an exponential gap. A function f:\{0,1\}^n \to \{0,1\} is promised to be either constant or balanced (0 on exactly half the inputs). A deterministic classical algorithm may need 2^{n-1} + 1 evaluations to tell which. The quantum algorithm needs one call to the phase oracle |x\rangle \to (-1)^{f(x)}|x\rangle:">

.. only:: html

  .. image:: /api/gallery/quantum/quantum_computing/images/thumb/sphx_glr_plot_deutsch_jozsa_algorithm_thumb.png
    :alt:

  :doc:`/api/gallery/quantum/quantum_computing/plot_deutsch_jozsa_algorithm`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The Deutsch-Jozsa algorithm: the first exponential quantum speed-up</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Lov Grover (1996) showed that finding a marked item among N unsorted ones takes about \tfrac{\pi}{4}\sqrt N queries of a quantum oracle, against N/2 on average classically, and Bennett, Bernstein, Brassard and Vazirani had just proved that no quantum algorithm can do better. Each Grover iteration reflects the state about the unmarked subspace (the oracle) and then about the uniform superposition |s\rangle (the diffusion operator 2|s\rangle\langle s| - I). Together they rotate it by 2\theta toward the marked state, where \sin\theta = \sqrt{M/N}, so after k iterations">

.. only:: html

  .. image:: /api/gallery/quantum/quantum_computing/images/thumb/sphx_glr_plot_grover_search_thumb.png
    :alt:

  :doc:`/api/gallery/quantum/quantum_computing/plot_grover_search`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Grover's quantum search: a square-root speed-up</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Peter Shor (1994) showed that a quantum computer could factor integers in polynomial time, which no known classical algorithm does. Factoring N reduces to finding the period r of f(x) = a^x \bmod N; then \gcd(a^{r/2} \pm 1, N) are factors. The quantum step is the Fourier transform over 2^t amplitudes,">

.. only:: html

  .. image:: /api/gallery/quantum/quantum_computing/images/thumb/sphx_glr_plot_shor_quantum_fourier_transform_thumb.png
    :alt:

  :doc:`/api/gallery/quantum/quantum_computing/plot_shor_quantum_fourier_transform`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Shor's period finding and the quantum Fourier transform</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/quantum/quantum_computing/plot_deutsch_jozsa_algorithm
   /api/gallery/quantum/quantum_computing/plot_grover_search
   /api/gallery/quantum/quantum_computing/plot_shor_quantum_fourier_transform