> -----Original Message----- > From: [email protected] <[email protected]> > Sent: Monday, July 30, 2018 2:52 PM > To: [email protected] > Cc: Scott Fluhrer (sfluhrer) <[email protected]>; [email protected]; > [email protected]; [email protected]; [email protected] > Subject: Re: [IPsec] Modp-12288 and Modp-16384 > > Interesting item in the abstract: "... using a quantum circuit of at most > 448.n^3.log2(n)+4090.n^3 Toffoli gates." In the past I've seen mention of > qubit counts but not gate counts. While the gate count isn't exponential, > it's > nevertheless formidable. For 1000 bit inputs it translates to several > teragates. How tight is that upper bound?
I believe that is a misleading statistic. What that is a measure of is "if we implement the circuit as a huge combinatorial circuit, how many individual quantum gates will we need?" It's misleading because, in practice, we'd never implement things that way. Instead, we'd devise ways where the same physical Tofolli gate is used multiple times during the computation (analogous to how, on a classical computer, we reuse the same addition and multiplication circuit repeatedly when performing a series of operations). Now, in the Quantum realm, this problem turns out to be a bit different than in the classical realm; however I believe that is a problem that can be solved (and, indeed, needs to be solved for Quantum Computing to be realistic) _______________________________________________ IPsec mailing list [email protected] https://www.ietf.org/mailman/listinfo/ipsec
