Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I They physics of phase inversion in Grover's algorithm

  1. Apr 16, 2017 #1
    How would this operator be implemented physically if we had a quantum computer?

    In Grover's algorithm this magical operator is often called "phase inversion". Here is the operator from wiki:

    https://wikimedia.org/api/rest_v1/media/math/render/svg/07fb23bffa787430b084971c6a108a8f6ff6c2b3

    It’s an operator that does nothing to most of the states, except it inverts the phase of the states we’re looking for. (for all states x where f(x) = 1).

    I assume we are using the feature of quantum mechanics that we can input a superposition of all possible states, and acting upon them all at the same time with our operators, then at the end, measuring the state of the system, giving us the state we're looking for with high probability (p > 1/2).

    So I repeat my question:

    How would this operator be implemented physically if we had a quantum computer?

    Thanks
    Frímann Kjerúlf
    BSc Physics - University of Iceland
     
  2. jcsd
  3. Apr 16, 2017 #2

    PeterDonis

    User Avatar
    2016 Award

    Staff: Mentor

    You need to give a lot more context. Please give a link to the full article. Or, even better, to a textbook or peer-reviewed paper that discusses this operator.
     
  4. Apr 16, 2017 #3

    Strilanc

    User Avatar
    Science Advisor

    The black box in Grover's algorithm depends on the problem you're trying to solve. But generally it's just a "solution checker" that checks if a given input is correct, hits the "is it correct?" bit with a Z gate, then uncomputes all the junk it created while doing that.

    A simple example is searching for a 3-SAT solution. Suppose we want to find boolean values for x, y, and z that satisfy:

    $$(x \lor y \lor z) \land (\lnot x \lor \lnot y \lor \lnot z) \land (\lnot x \lor y \lor \lnot z)$$

    To check a solution, you need to check if each clause is satisfied then combine those answers into one big 'all clauses satisfied' answer. Which, combined with the Z gate and uncomputation, looks something like exactly this:

    3sat-grover.png

    Of course this is a very simple case. In more complicated cases, like checking if the input encodes a valid proof of a theorem, the circuit can get very complicated. You would want to use a tool to generate the circuit, based on some C code or whatever.
     
    Last edited: Apr 16, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: They physics of phase inversion in Grover's algorithm
  1. Grover's algorithm (Replies: 7)

Loading...