Grover's algorithm with W-state











up vote
3
down vote

favorite












In the general form of Grover's algorithm, we start with the uniform superposition of n qubits. Now, suppose instead that we start with a generic state, for example the W state, and the oracle only inverts the phase of one of the basis.



To make it more concrete, let's say we have in input a $W_3$ state $$|Wrangle = frac{1}{sqrt{3}} (|001rangle + |010rangle + |100rangle)$$
and that the oracle inverts only state $$|001rangle$$



At this point, how can we implement the diffusion operator? In other words, how can we amplify only this state in order to obtain the right output with an high probability?






algorithm entanglement grovers-algorithm







share|improve this question




























    up vote
    3
    down vote

    favorite












    In the general form of Grover's algorithm, we start with the uniform superposition of n qubits. Now, suppose instead that we start with a generic state, for example the W state, and the oracle only inverts the phase of one of the basis.



    To make it more concrete, let's say we have in input a $W_3$ state $$|Wrangle = frac{1}{sqrt{3}} (|001rangle + |010rangle + |100rangle)$$
    and that the oracle inverts only state $$|001rangle$$



    At this point, how can we implement the diffusion operator? In other words, how can we amplify only this state in order to obtain the right output with an high probability?






    algorithm entanglement grovers-algorithm







    share|improve this question


























      up vote
      3
      down vote

      favorite









      up vote
      3
      down vote

      favorite











      In the general form of Grover's algorithm, we start with the uniform superposition of n qubits. Now, suppose instead that we start with a generic state, for example the W state, and the oracle only inverts the phase of one of the basis.



      To make it more concrete, let's say we have in input a $W_3$ state $$|Wrangle = frac{1}{sqrt{3}} (|001rangle + |010rangle + |100rangle)$$
      and that the oracle inverts only state $$|001rangle$$



      At this point, how can we implement the diffusion operator? In other words, how can we amplify only this state in order to obtain the right output with an high probability?






      algorithm entanglement grovers-algorithm







      share|improve this question















      In the general form of Grover's algorithm, we start with the uniform superposition of n qubits. Now, suppose instead that we start with a generic state, for example the W state, and the oracle only inverts the phase of one of the basis.



      To make it more concrete, let's say we have in input a $W_3$ state $$|Wrangle = frac{1}{sqrt{3}} (|001rangle + |010rangle + |100rangle)$$
      and that the oracle inverts only state $$|001rangle$$



      At this point, how can we implement the diffusion operator? In other words, how can we amplify only this state in order to obtain the right output with an high probability?






      algorithm entanglement grovers-algorithm




      algorithm entanglement grovers-algorithm






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 1 hour ago









      Blue♦

      5,63511352




      5,63511352










      asked 8 hours ago









      tigerjack89

      1735




      1735






















          3 Answers
          3






          active

          oldest

          votes

















          up vote
          1
          down vote













          I think that it does not change the original Grover's algorithm idea. Let me explain better, Grover's algorithm does make any distinction about the input or the original state. See figure attached for better representation. I think it will work as a general case.
          enter image description here






          share|improve this answer





















          • Not too sure about it. It seems to me that the one you're representing as diffusion is a reflection about the uniform superposition. Here instead we don't have an uniform superposition in input.
            – tigerjack89
            8 hours ago




















          up vote
          1
          down vote













          Say $ | psi rangle $ represents the uniform suposition.



          Then, the Grover diffusion operator is written :
          $$ 2 | psi rangle langle psi | - I$$



          Now to act on a subset of a superposition, you would need to implement :
          $$ 2 | Wrangle langle W | - I$$



          I am not sure if someone had really looked into how decompose this operation as a circuit. I guess it would be too dependent on the initial state.



          This paper however shows a trick to still get the state you want with a high probability. Check section 3.3.1 .
          The idea is to start with $ | W rangle $ and use a first Grover iteration to inverse amplitudes about average by only marking the target state. Then you would mark the computational basis states that are present initially in $ | psi rangle $ and use inversion about average again. Finally, you would continue with usual Grover iterations. They provide an example to help you visualize the effect of the steps. The target should have a high probability of being measured, even if others states not present in $ | W rangle $ can be measured.






          share|improve this answer




























            up vote
            1
            down vote













            I think, if one starts with the $W$ state which contains only $3$ out of $8$ possible $3$-bit strings then the Grover algorithm will work correctly only of the secret is one of those $3$ strings. If secret has $2$ or $3$ $1$-bits , say 011 there is no matched initial state to amplify.
            There is a reason Grover starts with n Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.






            share|improve this answer










            New contributor




            Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
            Check out our Code of Conduct.


















            • Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
              – Blue♦
              1 hour ago













            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "694"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4963%2fgrovers-algorithm-with-w-state%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            3 Answers
            3






            active

            oldest

            votes








            3 Answers
            3






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            1
            down vote













            I think that it does not change the original Grover's algorithm idea. Let me explain better, Grover's algorithm does make any distinction about the input or the original state. See figure attached for better representation. I think it will work as a general case.
            enter image description here






            share|improve this answer





















            • Not too sure about it. It seems to me that the one you're representing as diffusion is a reflection about the uniform superposition. Here instead we don't have an uniform superposition in input.
              – tigerjack89
              8 hours ago

















            up vote
            1
            down vote













            I think that it does not change the original Grover's algorithm idea. Let me explain better, Grover's algorithm does make any distinction about the input or the original state. See figure attached for better representation. I think it will work as a general case.
            enter image description here






            share|improve this answer





















            • Not too sure about it. It seems to me that the one you're representing as diffusion is a reflection about the uniform superposition. Here instead we don't have an uniform superposition in input.
              – tigerjack89
              8 hours ago















            up vote
            1
            down vote










            up vote
            1
            down vote









            I think that it does not change the original Grover's algorithm idea. Let me explain better, Grover's algorithm does make any distinction about the input or the original state. See figure attached for better representation. I think it will work as a general case.
            enter image description here






            share|improve this answer












            I think that it does not change the original Grover's algorithm idea. Let me explain better, Grover's algorithm does make any distinction about the input or the original state. See figure attached for better representation. I think it will work as a general case.
            enter image description here







            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered 8 hours ago









            Gustavo Banegas

            11115




            11115












            • Not too sure about it. It seems to me that the one you're representing as diffusion is a reflection about the uniform superposition. Here instead we don't have an uniform superposition in input.
              – tigerjack89
              8 hours ago




















            • Not too sure about it. It seems to me that the one you're representing as diffusion is a reflection about the uniform superposition. Here instead we don't have an uniform superposition in input.
              – tigerjack89
              8 hours ago


















            Not too sure about it. It seems to me that the one you're representing as diffusion is a reflection about the uniform superposition. Here instead we don't have an uniform superposition in input.
            – tigerjack89
            8 hours ago






            Not too sure about it. It seems to me that the one you're representing as diffusion is a reflection about the uniform superposition. Here instead we don't have an uniform superposition in input.
            – tigerjack89
            8 hours ago














            up vote
            1
            down vote













            Say $ | psi rangle $ represents the uniform suposition.



            Then, the Grover diffusion operator is written :
            $$ 2 | psi rangle langle psi | - I$$



            Now to act on a subset of a superposition, you would need to implement :
            $$ 2 | Wrangle langle W | - I$$



            I am not sure if someone had really looked into how decompose this operation as a circuit. I guess it would be too dependent on the initial state.



            This paper however shows a trick to still get the state you want with a high probability. Check section 3.3.1 .
            The idea is to start with $ | W rangle $ and use a first Grover iteration to inverse amplitudes about average by only marking the target state. Then you would mark the computational basis states that are present initially in $ | psi rangle $ and use inversion about average again. Finally, you would continue with usual Grover iterations. They provide an example to help you visualize the effect of the steps. The target should have a high probability of being measured, even if others states not present in $ | W rangle $ can be measured.






            share|improve this answer

























              up vote
              1
              down vote













              Say $ | psi rangle $ represents the uniform suposition.



              Then, the Grover diffusion operator is written :
              $$ 2 | psi rangle langle psi | - I$$



              Now to act on a subset of a superposition, you would need to implement :
              $$ 2 | Wrangle langle W | - I$$



              I am not sure if someone had really looked into how decompose this operation as a circuit. I guess it would be too dependent on the initial state.



              This paper however shows a trick to still get the state you want with a high probability. Check section 3.3.1 .
              The idea is to start with $ | W rangle $ and use a first Grover iteration to inverse amplitudes about average by only marking the target state. Then you would mark the computational basis states that are present initially in $ | psi rangle $ and use inversion about average again. Finally, you would continue with usual Grover iterations. They provide an example to help you visualize the effect of the steps. The target should have a high probability of being measured, even if others states not present in $ | W rangle $ can be measured.






              share|improve this answer























                up vote
                1
                down vote










                up vote
                1
                down vote









                Say $ | psi rangle $ represents the uniform suposition.



                Then, the Grover diffusion operator is written :
                $$ 2 | psi rangle langle psi | - I$$



                Now to act on a subset of a superposition, you would need to implement :
                $$ 2 | Wrangle langle W | - I$$



                I am not sure if someone had really looked into how decompose this operation as a circuit. I guess it would be too dependent on the initial state.



                This paper however shows a trick to still get the state you want with a high probability. Check section 3.3.1 .
                The idea is to start with $ | W rangle $ and use a first Grover iteration to inverse amplitudes about average by only marking the target state. Then you would mark the computational basis states that are present initially in $ | psi rangle $ and use inversion about average again. Finally, you would continue with usual Grover iterations. They provide an example to help you visualize the effect of the steps. The target should have a high probability of being measured, even if others states not present in $ | W rangle $ can be measured.






                share|improve this answer












                Say $ | psi rangle $ represents the uniform suposition.



                Then, the Grover diffusion operator is written :
                $$ 2 | psi rangle langle psi | - I$$



                Now to act on a subset of a superposition, you would need to implement :
                $$ 2 | Wrangle langle W | - I$$



                I am not sure if someone had really looked into how decompose this operation as a circuit. I guess it would be too dependent on the initial state.



                This paper however shows a trick to still get the state you want with a high probability. Check section 3.3.1 .
                The idea is to start with $ | W rangle $ and use a first Grover iteration to inverse amplitudes about average by only marking the target state. Then you would mark the computational basis states that are present initially in $ | psi rangle $ and use inversion about average again. Finally, you would continue with usual Grover iterations. They provide an example to help you visualize the effect of the steps. The target should have a high probability of being measured, even if others states not present in $ | W rangle $ can be measured.







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered 3 hours ago









                cnada

                1,691211




                1,691211






















                    up vote
                    1
                    down vote













                    I think, if one starts with the $W$ state which contains only $3$ out of $8$ possible $3$-bit strings then the Grover algorithm will work correctly only of the secret is one of those $3$ strings. If secret has $2$ or $3$ $1$-bits , say 011 there is no matched initial state to amplify.
                    There is a reason Grover starts with n Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.






                    share|improve this answer










                    New contributor




                    Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                    Check out our Code of Conduct.


















                    • Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
                      – Blue♦
                      1 hour ago

















                    up vote
                    1
                    down vote













                    I think, if one starts with the $W$ state which contains only $3$ out of $8$ possible $3$-bit strings then the Grover algorithm will work correctly only of the secret is one of those $3$ strings. If secret has $2$ or $3$ $1$-bits , say 011 there is no matched initial state to amplify.
                    There is a reason Grover starts with n Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.






                    share|improve this answer










                    New contributor




                    Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                    Check out our Code of Conduct.


















                    • Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
                      – Blue♦
                      1 hour ago















                    up vote
                    1
                    down vote










                    up vote
                    1
                    down vote









                    I think, if one starts with the $W$ state which contains only $3$ out of $8$ possible $3$-bit strings then the Grover algorithm will work correctly only of the secret is one of those $3$ strings. If secret has $2$ or $3$ $1$-bits , say 011 there is no matched initial state to amplify.
                    There is a reason Grover starts with n Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.






                    share|improve this answer










                    New contributor




                    Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                    Check out our Code of Conduct.









                    I think, if one starts with the $W$ state which contains only $3$ out of $8$ possible $3$-bit strings then the Grover algorithm will work correctly only of the secret is one of those $3$ strings. If secret has $2$ or $3$ $1$-bits , say 011 there is no matched initial state to amplify.
                    There is a reason Grover starts with n Hadamards applied to $n$ qubits - this way all possible $2^n$ $n$-bit strings are present and one of them must match to the secret.







                    share|improve this answer










                    New contributor




                    Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                    Check out our Code of Conduct.









                    share|improve this answer



                    share|improve this answer








                    edited 1 hour ago









                    Blue♦

                    5,63511352




                    5,63511352






                    New contributor




                    Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                    Check out our Code of Conduct.









                    answered 1 hour ago









                    Jan Balewski

                    162




                    162




                    New contributor




                    Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                    Check out our Code of Conduct.





                    New contributor





                    Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                    Check out our Code of Conduct.






                    Jan Balewski is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                    Check out our Code of Conduct.












                    • Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
                      – Blue♦
                      1 hour ago




















                    • Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
                      – Blue♦
                      1 hour ago


















                    Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
                    – Blue♦
                    1 hour ago






                    Hi Jan. Welcome to Quantum Computing Stack Exchange! Please use MathJax to format the mathematical expressions in your answer, in the future. I've done it this time.
                    – Blue♦
                    1 hour ago




















                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Quantum Computing Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid …



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.





                    Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                    Please pay close attention to the following guidance:


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid …



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4963%2fgrovers-algorithm-with-w-state%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    -

                    Popular posts from this blog

                    Costa Masnaga

                    Image
                    .mw-parser-output .avviso .mbox-text-div>div,.mw-parser-output .avviso .mbox-text-full-div>div{font-size:90%}.mw-parser-output .avviso .mbox-image div{width:52px}.mw-parser-output .avviso .mbox-text-full-div .hide-when-compact{display:block} Questa voce o sezione sull'argomento Lombardia non cita le fonti necessarie o quelle presenti sono insufficienti . Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Costa Masnaga comune Localizzazione Stato   Italia Regione Lombardia Provincia Lecco Amministrazione Sindaco Sabina Panzeri (Al centro il cittadino) dall'08/06/2009 Territorio Coordinate 45°46′N 9°17′E  /  45.766667°N 9.283333°E 45.766667; 9.283333  ( Costa Masnaga ) Coordinate: 45°46′N 9°17′E  /  45.766667°N 9.283333°E 45.766667; 9.283333  ( Costa Masnaga ) Altitudine 318 m s.l.m...
                    Read more

                    Fotorealismo

                    Image
                    Guerrino Boatto, Venice's St. Barnaba Church and canal Il fotorealismo è un genere di pittura basato sull'uso di una o più fotografie dalle quali l'artista prende le informazioni necessarie da utilizzare poi nel processo della creazione dell'opera, in genere ad olio o ad acrilico, al fine di avere un aspetto finale il più simile possibile alla fotografia. Indice 1 Storia 2 Lista dei fotorealisti 3 Note 4 Voci correlate 5 Altri progetti Storia | Il fotorealismo è un movimento che nasce negli Stati Uniti d'America alla fine degli anni sessanta [1] sulla scia della Pop Art [2] [3] [4] , e insieme condividono il carattere reazionario verso la travolgente ascesa dei media, che alla metà del ventesimo secolo si trasforma in un fenomeno di massa talmente imponente da minacciare il valore dell'immagine nell'arte. [5] [6] Ne consegue così che, colto il gesto d'inizio che fu della Pop Art, i fotorealisti aprono ad un ...
                    Read more

                    Sidney Franklin

                    Image
                    Questa voce sull'argomento registi statunitensi è solo un abbozzo . Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Sidney Franklin, foto di Carl Van Vechten Oscar alla memoria Irving G. Thalberg 1943 Sidney Franklin , all'anagrafe Sidney Arnold Franklin , (San Francisco, 21 marzo 1893 – Santa Monica, 18 maggio 1972), è stato un regista, produttore cinematografico e attore statunitense. Il 20 giugno 1963, si sposò con l'attrice australiana Enid Bennett. Il matrimonio durò fino alla morte dell'attrice, il 14 maggio 1969 [1] Indice 1 Filmografia 1.1 Regista 1.2 Aiuto regia (parziale) 1.3 Produttore 1.4 Attore (parziale) 2 Note 3 Altri progetti 4 Collegamenti esterni Filmografia | Regista | The Baby , co-regia Chester M. Franklin (1915) The Rivals , co-regia Chester M. Franklin (1915) Little Dick's First Case , co-regia Chester M. Franklin (1915) Her Filmland Hero , co-...
                    Read more