I understand theoretically how Shor's algorithm works, but I don't know what specific gates are used (or would be used) to implement it. What would the quantum circuit look like?
1
-
2$\begingroup$ The same gates that are used in any other quantum circuit, nothing special there. The circuit is not trivial and has many parts. In such cases, we rarely actually draw the circuit, but prove it can be built (looking at the graph wont give you much insight anyway). This is similar to the case with Turing machines, after some basic exercises, we rarely draw the machine to convince ourselves a problem is decidable, but talk in terms of operations we already agree that can be done in a Turing machine (e.g. find minimum). $\endgroup$– ArielOct 6, 2016 at 5:19
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
There are several correct answers to this question because there are several candidate sets available for use as a universal set of quantum operators and because there isn't an agreed upon best implementation for the primitives needed by Shor's algorithm. Different circuits will trade-off circuit-depth for ancillary qubits and vice versa. Ultimately, the exact implementation is likely to depend on the architecture of the quantum computer.
What that in mind, you can probably find a version of the details you're looking for in Fast Modular Exponentiation Architecture for Shor's Factoring Algorithm by Pavlidis and Gizopoulos. The exact circuit layout is lengthy and complex and probably too much for an answer here. The paper has lots of diagrams though and a quick scan should should provide you with a rough feel for the circuit construction. Unsurprisingly, the circuit makes heavy use of Hadamard gates and controlled phase-shift operators both to implement the inverse QFT and the modular exponentiation circuit.
$\begingroup$
$\endgroup$
3
According to quantumplayground.net shor's algorithm uses some swaps, hadamards, measuerments, and Inverse Quantum Fourier Transform gates.
check it out yourself:
Shor's Algorithm
-
$\begingroup$ I don't really see how this answers the question. The page on Shor's algorithm that you link to contains a ninety-line program in some imperative programming language that invokes such routines as
QMath.ipowandQmath.gcd. That doesn't show what gates are used, or how to implement it as a quantum circuit. $\endgroup$ Nov 15, 2016 at 16:15 -
$\begingroup$ You make people guessing which content on that website is the one you're referenceing -- that's no good. Plus, links tend to die over time; a more robust reference would be better. $\endgroup$– RaphaelNov 15, 2016 at 21:22
-
$\begingroup$ @DavidRicherby I guess "Shor's Algorithm - libquantum" is the one we ought to look at? $\endgroup$– RaphaelNov 15, 2016 at 21:22