Grover's algorithm – DES circuit as oracle?Why do we have to uncompute rather than simply set registers to zero?Reversible crypto systems for use in the Grover's algorithmWhy can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithmCompact encoding of Boolean formula as oracleQuantum attack on hash functionsPointer to related research (paper)Grover algorithm for more than one elementPossible results from Shor's algorithm in practiceN&C quantum circuit for Grover's algorithmGrover's algorithm: number of searchesReversible crypto systems for use in the Grover's algorithm

Differences between “pas vrai ?”, “c’est ça ?”, “hein ?”, and “n’est-ce pas ?”

Asking bank to reduce APR instead of increasing credit limit

Preserving culinary oils

The qvolume of an integer

Why the lack of hesitance to wear pads on the sabbath?

Can non-English-speaking characters use wordplay specific to English?

How can I offer a test ride while selling a bike?

How crucial is a waifu game storyline?

Different PCB color ( is it different material? )

How was Apollo supposed to rendezvous in the case of a lunar abort?

Possible nonclassical ion from a bicyclic system

Do creatures all have the same statistics upon being reanimated via the Animate Dead spell?

Why use water tanks from a retired Space Shuttle?

Points within polygons in different projections

Did airlines fly their aircraft slower in response to oil prices in the 1970s?

Team member doesn't give me the minimum time to complete a talk

Is there a rule that prohibits us from using 2 possessives in a row?

If a massive object like Jupiter flew past the Earth how close would it need to come to pull people off of the surface?

Fastest way to perform complex search on pandas dataframe

What is the intuition behind uniform continuity?

Is there an evolutionary advantage to having two heads?

If a problem only occurs randomly once in every N times on average, how many tests do I have to perform to be certain that it's now fixed?

Biblical Basis for 400 years of silence between old and new testament

Tic-Tac-Toe for the terminal



Grover's algorithm – DES circuit as oracle?


Why do we have to uncompute rather than simply set registers to zero?Reversible crypto systems for use in the Grover's algorithmWhy can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithmCompact encoding of Boolean formula as oracleQuantum attack on hash functionsPointer to related research (paper)Grover algorithm for more than one elementPossible results from Shor's algorithm in practiceN&C quantum circuit for Grover's algorithmGrover's algorithm: number of searchesReversible crypto systems for use in the Grover's algorithm






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;








3












$begingroup$


In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|xranglerightarrow(-1)^f(x)|xrangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.



My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?



I would be very interested in what you think about it!










share|improve this question











$endgroup$


















    3












    $begingroup$


    In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|xranglerightarrow(-1)^f(x)|xrangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.



    My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?



    I would be very interested in what you think about it!










    share|improve this question











    $endgroup$














      3












      3








      3





      $begingroup$


      In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|xranglerightarrow(-1)^f(x)|xrangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.



      My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?



      I would be very interested in what you think about it!










      share|improve this question











      $endgroup$




      In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|xranglerightarrow(-1)^f(x)|xrangle$. I have read that it is possible to transform any efficient classical circuit into a quantum circuit.



      My question, if I want to crack the DES encryption, is it possible to implement the DES algorithm as a circuit that acts as an oracle then? That's just a consideration. Is that conceivable? Could I find the key you are looking for? Is there perhaps some paper about it?



      I would be very interested in what you think about it!







      algorithm grovers-algorithm cryptography






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Apr 18 at 19:45









      Sanchayan Dutta

      7,34241660




      7,34241660










      asked Apr 13 at 16:17







      user4961



























          1 Answer
          1






          active

          oldest

          votes


















          3












          $begingroup$

          In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:



          1. AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965  

          2. MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377

          3. SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383

          A general programmatic framework to express general oracles, synthesize them into quantum circuits (while keeping quantum memory bounded), and perform cost analyses does not exist to the best of my knowledge.



          Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^64$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^86$ in the first paper above).



          In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.






          share|improve this answer











          $endgroup$












          • $begingroup$
            Thank you for your answer. Perhaps you can help me with this: "Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a circuit that checks whether $f(x) = y$". The last part is obvious, but why does $f$ have to be called twice?
            $endgroup$
            – user4961
            Apr 17 at 10:19







          • 2




            $begingroup$
            @QuantaMag The reason for the two calls is that first one has to evaluate $f$ (coherently, i.e., by way of a reversible circuit), then one evaluates the equality function, but then one has to uncompute the call to $f$. In other words: $$ sum_x |xrangle |0rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |f(x)stackrel?=y rangle mapsto sum_x |xrangle |0rangle |f(x)stackrel?= yrangle $$ If you don't uncompute the call to $f(x)$, then there will be no interference possible.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:28







          • 1




            $begingroup$
            @QuantaMag See also the answer quantumcomputing.stackexchange.com/a/5232/1828 to a related question about why we have to uncompute garbage.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:32












          Your Answer








          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',
          autoActivateHeartbeat: false,
          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%2f5907%2fgrovers-algorithm-des-circuit-as-oracle%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown
























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          3












          $begingroup$

          In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:



          1. AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965  

          2. MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377

          3. SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383

          A general programmatic framework to express general oracles, synthesize them into quantum circuits (while keeping quantum memory bounded), and perform cost analyses does not exist to the best of my knowledge.



          Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^64$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^86$ in the first paper above).



          In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.






          share|improve this answer











          $endgroup$












          • $begingroup$
            Thank you for your answer. Perhaps you can help me with this: "Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a circuit that checks whether $f(x) = y$". The last part is obvious, but why does $f$ have to be called twice?
            $endgroup$
            – user4961
            Apr 17 at 10:19







          • 2




            $begingroup$
            @QuantaMag The reason for the two calls is that first one has to evaluate $f$ (coherently, i.e., by way of a reversible circuit), then one evaluates the equality function, but then one has to uncompute the call to $f$. In other words: $$ sum_x |xrangle |0rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |f(x)stackrel?=y rangle mapsto sum_x |xrangle |0rangle |f(x)stackrel?= yrangle $$ If you don't uncompute the call to $f(x)$, then there will be no interference possible.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:28







          • 1




            $begingroup$
            @QuantaMag See also the answer quantumcomputing.stackexchange.com/a/5232/1828 to a related question about why we have to uncompute garbage.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:32
















          3












          $begingroup$

          In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:



          1. AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965  

          2. MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377

          3. SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383

          A general programmatic framework to express general oracles, synthesize them into quantum circuits (while keeping quantum memory bounded), and perform cost analyses does not exist to the best of my knowledge.



          Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^64$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^86$ in the first paper above).



          In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.






          share|improve this answer











          $endgroup$












          • $begingroup$
            Thank you for your answer. Perhaps you can help me with this: "Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a circuit that checks whether $f(x) = y$". The last part is obvious, but why does $f$ have to be called twice?
            $endgroup$
            – user4961
            Apr 17 at 10:19







          • 2




            $begingroup$
            @QuantaMag The reason for the two calls is that first one has to evaluate $f$ (coherently, i.e., by way of a reversible circuit), then one evaluates the equality function, but then one has to uncompute the call to $f$. In other words: $$ sum_x |xrangle |0rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |f(x)stackrel?=y rangle mapsto sum_x |xrangle |0rangle |f(x)stackrel?= yrangle $$ If you don't uncompute the call to $f(x)$, then there will be no interference possible.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:28







          • 1




            $begingroup$
            @QuantaMag See also the answer quantumcomputing.stackexchange.com/a/5232/1828 to a related question about why we have to uncompute garbage.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:32














          3












          3








          3





          $begingroup$

          In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:



          1. AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965  

          2. MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377

          3. SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383

          A general programmatic framework to express general oracles, synthesize them into quantum circuits (while keeping quantum memory bounded), and perform cost analyses does not exist to the best of my knowledge.



          Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^64$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^86$ in the first paper above).



          In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.






          share|improve this answer











          $endgroup$



          In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known that do not create as much memory overhead as Bennett's method. As far as programmatic support for this is concerned, there are several attempts for various ciphers and hash-functions to perform this cost analysis with the help of a computer:



          1. AES was analyzed (using C/C++ programs for resource counting and well known circuits for the underlying finite field arithmetic) in "Applying Grover's algorithm to AES: quantum resource estimates" by Grassl et al. Link to paper: https://arxiv.org/abs/1512.04965  

          2. MD5 and SHA-2 were analyzed (using prototypes such as REVS) in "Reversible circuit compilation with space constraints" by Parent et al. Note that technically not the entire encryption was implemented, but just one round function. In particular, no key scheduler. Link to paper: https://arxiv.org/abs/1510.00377

          3. SHA-2 and SHA-3 were analyzed (again using prototypes such as ReVer) in "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3" by Amy et al. Again, again not the entire encryption. Link to paper: https://arxiv.org/abs/1603.09383

          A general programmatic framework to express general oracles, synthesize them into quantum circuits (while keeping quantum memory bounded), and perform cost analyses does not exist to the best of my knowledge.



          Finally, note that applying Grover to breaking ciphers and hash-functions does not lead to practical attacks on these schemes, at least not for real-world parameters choices (such as AES-128 or even DES-56). The reason is that despite the quadratic speedup that you get from Grover's algorithm, the problem to find the encryption key is still exponential. Furthermore, the requirement to implement the oracle reversible typically leads to large overheads in terms of qubits and gates, so the quadratic speedup is even less pronounced than one might expect (see e.g. the mentioned AES-128 case above where the gate count is not $2^64$ as one might expect from the square root speedup over a naïve solution, but worked out to be about $2^86$ in the first paper above).



          In other words, the whole point of applying Grover's algorithm (and other known quantum algorithm such as claw-finding etc.) to classical cryptographic schemes is not so much to carry out said attacks, but instead is assess their security parameters against quantum attacks.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Apr 13 at 23:57

























          answered Apr 13 at 20:46









          MartinQuantumMartinQuantum

          48529




          48529











          • $begingroup$
            Thank you for your answer. Perhaps you can help me with this: "Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a circuit that checks whether $f(x) = y$". The last part is obvious, but why does $f$ have to be called twice?
            $endgroup$
            – user4961
            Apr 17 at 10:19







          • 2




            $begingroup$
            @QuantaMag The reason for the two calls is that first one has to evaluate $f$ (coherently, i.e., by way of a reversible circuit), then one evaluates the equality function, but then one has to uncompute the call to $f$. In other words: $$ sum_x |xrangle |0rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |f(x)stackrel?=y rangle mapsto sum_x |xrangle |0rangle |f(x)stackrel?= yrangle $$ If you don't uncompute the call to $f(x)$, then there will be no interference possible.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:28







          • 1




            $begingroup$
            @QuantaMag See also the answer quantumcomputing.stackexchange.com/a/5232/1828 to a related question about why we have to uncompute garbage.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:32

















          • $begingroup$
            Thank you for your answer. Perhaps you can help me with this: "Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a circuit that checks whether $f(x) = y$". The last part is obvious, but why does $f$ have to be called twice?
            $endgroup$
            – user4961
            Apr 17 at 10:19







          • 2




            $begingroup$
            @QuantaMag The reason for the two calls is that first one has to evaluate $f$ (coherently, i.e., by way of a reversible circuit), then one evaluates the equality function, but then one has to uncompute the call to $f$. In other words: $$ sum_x |xrangle |0rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |f(x)stackrel?=y rangle mapsto sum_x |xrangle |0rangle |f(x)stackrel?= yrangle $$ If you don't uncompute the call to $f(x)$, then there will be no interference possible.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:28







          • 1




            $begingroup$
            @QuantaMag See also the answer quantumcomputing.stackexchange.com/a/5232/1828 to a related question about why we have to uncompute garbage.
            $endgroup$
            – MartinQuantum
            Apr 20 at 7:32
















          $begingroup$
          Thank you for your answer. Perhaps you can help me with this: "Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a circuit that checks whether $f(x) = y$". The last part is obvious, but why does $f$ have to be called twice?
          $endgroup$
          – user4961
          Apr 17 at 10:19





          $begingroup$
          Thank you for your answer. Perhaps you can help me with this: "Each call to $U_g$ involves two calls to a reversible implementation of $f$ and one call to a circuit that checks whether $f(x) = y$". The last part is obvious, but why does $f$ have to be called twice?
          $endgroup$
          – user4961
          Apr 17 at 10:19





          2




          2




          $begingroup$
          @QuantaMag The reason for the two calls is that first one has to evaluate $f$ (coherently, i.e., by way of a reversible circuit), then one evaluates the equality function, but then one has to uncompute the call to $f$. In other words: $$ sum_x |xrangle |0rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |f(x)stackrel?=y rangle mapsto sum_x |xrangle |0rangle |f(x)stackrel?= yrangle $$ If you don't uncompute the call to $f(x)$, then there will be no interference possible.
          $endgroup$
          – MartinQuantum
          Apr 20 at 7:28





          $begingroup$
          @QuantaMag The reason for the two calls is that first one has to evaluate $f$ (coherently, i.e., by way of a reversible circuit), then one evaluates the equality function, but then one has to uncompute the call to $f$. In other words: $$ sum_x |xrangle |0rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |0rangle mapsto sum_x |xrangle |f(x)rangle |f(x)stackrel?=y rangle mapsto sum_x |xrangle |0rangle |f(x)stackrel?= yrangle $$ If you don't uncompute the call to $f(x)$, then there will be no interference possible.
          $endgroup$
          – MartinQuantum
          Apr 20 at 7:28





          1




          1




          $begingroup$
          @QuantaMag See also the answer quantumcomputing.stackexchange.com/a/5232/1828 to a related question about why we have to uncompute garbage.
          $endgroup$
          – MartinQuantum
          Apr 20 at 7:32





          $begingroup$
          @QuantaMag See also the answer quantumcomputing.stackexchange.com/a/5232/1828 to a related question about why we have to uncompute garbage.
          $endgroup$
          – MartinQuantum
          Apr 20 at 7:32


















          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.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f5907%2fgrovers-algorithm-des-circuit-as-oracle%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

          Tamil (spriik) Luke uk diar | Nawigatjuun

          Align equal signs while including text over equalitiesAMS align: left aligned text/math plus multicolumn alignmentMultiple alignmentsAligning equations in multiple placesNumbering and aligning an equation with multiple columnsHow to align one equation with another multline equationUsing \ in environments inside the begintabularxNumber equations and preserving alignment of equal signsHow can I align equations to the left and to the right?Double equation alignment problem within align enviromentAligned within align: Why are they right-aligned?

          Training a classifier when some of the features are unknownWhy does Gradient Boosting regression predict negative values when there are no negative y-values in my training set?How to improve an existing (trained) classifier?What is effect when I set up some self defined predisctor variables?Why Matlab neural network classification returns decimal values on prediction dataset?Fitting and transforming text data in training, testing, and validation setsHow to quantify the performance of the classifier (multi-class SVM) using the test data?How do I control for some patients providing multiple samples in my training data?Training and Test setTraining a convolutional neural network for image denoising in MatlabShouldn't an autoencoder with #(neurons in hidden layer) = #(neurons in input layer) be “perfect”?