How to prevent future loops using a control qubit?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
3
down vote

favorite












I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|yrangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?










share|improve this question



























    up vote
    3
    down vote

    favorite












    I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|yrangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?










    share|improve this question

























      up vote
      3
      down vote

      favorite









      up vote
      3
      down vote

      favorite











      I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|yrangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?










      share|improve this question















      I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|yrangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?







      quantum-gate






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 2 hours ago









      Blue

      5,43811147




      5,43811147










      asked 4 hours ago









      nikojpapa

      975




      975




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          2
          down vote













          You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.



          figure from paper



          In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:



          for index, qubit in enumerate(input1):
          if qubit:
          output += input2 << index


          multiplication






          share|improve this answer






















            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: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            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%2f4552%2fhow-to-prevent-future-loops-using-a-control-qubit%23new-answer', 'question_page');

            );

            Post as a guest






























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            2
            down vote













            You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.



            figure from paper



            In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:



            for index, qubit in enumerate(input1):
            if qubit:
            output += input2 << index


            multiplication






            share|improve this answer


























              up vote
              2
              down vote













              You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.



              figure from paper



              In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:



              for index, qubit in enumerate(input1):
              if qubit:
              output += input2 << index


              multiplication






              share|improve this answer
























                up vote
                2
                down vote










                up vote
                2
                down vote









                You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.



                figure from paper



                In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:



                for index, qubit in enumerate(input1):
                if qubit:
                output += input2 << index


                multiplication






                share|improve this answer














                You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.



                figure from paper



                In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:



                for index, qubit in enumerate(input1):
                if qubit:
                output += input2 << index


                multiplication







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited 1 hour ago

























                answered 2 hours ago









                Craig Gidney

                2,712117




                2,712117



























                     

                    draft saved


                    draft discarded















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4552%2fhow-to-prevent-future-loops-using-a-control-qubit%23new-answer', 'question_page');

                    );

                    Post as a guest













































































                    Popular posts from this blog

                    How to check contact read email or not when send email to Individual?

                    Christian Cage

                    How to properly install USB display driver for Fresco Logic FL2000DX on Ubuntu?