We generalize quantum circuits for the Toffoli gate presented by Selinger and Jones for functionally controlled NOT gates, i.e., $X$ gates controlled by arbitrary $n$-variable Boolean functions. Our constructions target the gate set consisting of Cli
fford gates and single qubit rotations by arbitrary angles. Our constructions use the Walsh-Hadamard spectrum of Boolean functions and build on the work by Schuch and Siewert and Welch et al. We present quantum circuits for the case where the target qubit is in an arbitrary state as well as the special case where the target is in a known state. Additionally, we present constructions that require no auxiliary qubits and constructions that have a rotation depth of 1.
We present a completely automatic synthesis framework for oracle functions, a central part in many quantum algorithms. The proposed framework for resource-constrained oracle synthesis (ROS) is a LUT-based hierarchical method in which every step is sp
ecifically tailored to address hardware resource constraints. ROS embeds a LUT mapper designed to simplify the successive synthesis steps, costing each LUT according to the resources used by its corresponding quantum circuit. In addition, the framework exploits a SAT-based quantum garbage management technique. Those two characteristics give ROS the ability to beat the state-of-the-art hierarchical method both in number of qubits and in number of operations. The efficiency of the framework is demonstrated by synthesizing quantum oracles for Grovers algorithm.
We give precise quantum resource estimates for Shors algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, im
plemented within the framework of the quantum computing software tool suite LIQ$Ui|rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2lceillog_2(n)rceil+10$ qubits using a quantum circuit of at most $448 n^3 log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shors algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shors factoring algorithm. The results also support estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.
We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on LUT networks (lookup-table networks), which play a key role in conventional logic synthesis. Establishing a connec
tion between LUTs in a LUT network and reversible single-target gates in a reversible network allows us to bridge conventional logic synthesis with logic synthesis for quantum computing, despite several fundamental differences. We call our synthesis framework LUT-based Hierarchical Reversible Logic Synthesis (LHRS). Input to LHRS is a classical logic network; output is a quantum network (realized in terms of Clifford+$T$ gates). The framework offers to trade-off the number of qubits for the number of quantum gates. In a first step, an initial network is derived that only consists of single-target gates and already completely determines the number of qubits in the final quantum network. Different methods are then used to map each single-target gate into Clifford+$T$ gates, while aiming at optimally using available resources. We demonstrate the effectiveness of our method in automatically synthesizing IEEE compliant floating point networks up to double precision. As many quantum algorithms target scientific simulation applications, they can make rich use of floating point arithmetic components. But due to the lack of quantum circuit descriptions for those components, it can be difficult to find a realistic cost estimation for the algorithms. Our synthesized benchmarks provide cost estimates that allow quantum algorithm designers to provide the first complete cost estimates for a host of quantum algorithms. Thus, the benchmarks and, more generally, the LHRS framework are an essential step towards the goal of understanding which quantum algorithms will be practical in the first generations of quantum computers.
A major hurdle to the deployment of quantum linear systems algorithms and recent quantum simulation algorithms lies in the difficulty to find inexpensive reversible circuits for arithmetic using existing hand coded methods. Motivated by recent advanc
es in reversible logic synthesis, we synthesize arithmetic circuits using classical design automation flows and tools. The combination of classical and reversible logic synthesis enables the automatic design of large components in reversible logic starting from well-known hardware description languages such as Verilog. As a prototype example for our approach we automatically generate high quality networks for the reciprocal $1/x$, which is necessary for quantum linear systems algorithms.
We determine the cost of performing Shors algorithm for integer factorization on a ternary quantum computer, using two natural models of universal fault-tolerant computing: (i) a model based on magic state distillation that assumes the availability
of the ternary Clifford gates, projective measurements, classical control as its natural instrumentation set; (ii) a model based on a metaplectic topological quantum computer (MTQC). A natural choice to implement Shors algorithm on a ternary quantum computer is to translate the entire arithmetic into a ternary form. However, it is also possible to emulate the standard binary version of the algorithm by encoding each qubit in a three-level system. We compare the two approaches and analyze the complexity of implementing Shors period finding function in the two models. We also highlight the fact that the cost of achieving universality through magic states in MTQC architecture is asymptotically lower than in generic ternary case.
We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves $varepsilon$-approximations using circuits of length $O(log(1/varepsilon))$, which is asymptoticall
y optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+$pi/12$ [arXiv:1409.3552], running on average in time polynomial in $O(log(1/varepsilon))$ (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a good gate set for a fault-tolerant quantum computer.
It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algori
thms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore, Russell, and Schulman that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Omega(n log n) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because highly entangled measurements seem hard to implement in general. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL(n, F_{p^m}) and G^n where G is finite and satisfies a suitable property.
Suppose that a quantum circuit with K elementary gates is known for a unitary matrix U, and assume that U^m is a scalar matrix for some positive integer m. We show that a function of U can be realized on a quantum computer with at most O(mK+m^2log m)
elementary gates. The functions of U are realized by a generic quantum circuit, which has a particularly simple structure. Among other results, we obtain efficient circuits for the fractional Fourier transform.
We show that many well-known signal transforms allow highly efficient realizations on a quantum computer. We explain some elementary quantum circuits and review the construction of the Quantum Fourier Transform. We derive quantum circuits for the Dis
crete Cosine and Sine Transforms, and for the Discrete Hartley transform. We show that at most O(log^2 N) elementary quantum gates are necessary to implement any of those transforms for input sequences of length N.
