



01345nas a2200145   4500008004100000245006600041210006200107260001400169490000600183520092300189100001801112700001301130700001901143856003701162       2020                        eng d00aApproximate Quantum Fourier Transform with O(nlog(n)) T gates0 aApproximate Quantum Fourier Transform with Onlogn T gates  c3/13/20200 v63 a<p>The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer enables the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, and phase estimation. The standard fault-tolerant implementation of an n-qubit QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+t gates, incurring the t-count complexity of O(n log2 (n)). In this paper we show how to obtain approximate QFT with the t-count of O(n log(n)). Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.</p>1 aNam, Yunseong1 aSu, Yuan1 aMaslov, Dmitri  uhttps://arxiv.org/abs/1803.0493301295nas a2200169   4500008004100000245008000041210006900121260001500190490000600205520078500211100001800996700001901014700001301033700002301046700001901069856003701088       2018                        eng d00aAutomated optimization of large quantum circuits with continuous parameters0 aAutomated optimization of large quantum circuits with continuous  c2017/10/190 v43 a<p>We develop and implement automated methods for optimizing quantum circuits of the size and type expected in quantum computations that outperform classical computers. We show how to handle continuous gate parameters and report a collection of fast algorithms capable of optimizing large-scale quantum circuits. For the suite of benchmarks considered, we obtain substantial reductions in gate counts. In particular, we provide better optimization in significantly less time than previous approaches, while making minimal structural changes so as to preserve the basic layout of the underlying quantum algorithms. Our results help bridge the gap between the computations that can be run on existing hardware and those that are expected to outperform classical computers.&nbsp;</p>1 aNam, Yunseong1 aRoss, Neil, J.1 aSu, Yuan1 aChilds, Andrew, M.1 aMaslov, Dmitri  uhttps://arxiv.org/abs/1710.0734501659nas a2200133   4500008004100000245011600041210006900157260001500226300001100241490000700252520121100259100001901470856003601489       2016                        eng d00aOn the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization0 aadvantages of using relative phase Toffolis with an application   c2016/02/10  a0223110 v933 aVarious implementations of the Toffoli gate up to a relative phase have been known for years. The advantage over regular Toffoli gate is their smaller circuit size. However, their use has been often limited to a demonstration of quantum control in designs such as those where the Toffoli gate is being applied last or otherwise for some specific reasons the relative phase does not matter. It was commonly believed that the relative phase deviations would prevent the relative phase Toffolis from being very helpful in practical large-scale designs. 
In this paper, we report three circuit identities that provide the means for replacing certain configurations of the multiple control Toffoli gates with their simpler relative phase implementations, up to a selectable unitary on certain qubits, and without changing the overall functionality. We illustrate the advantage via applying those identities to the optimization of the known circuits implementing multiple control Toffoli gates, and report the reductions in the CNOT-count, T-count, as well as the number of ancillae used. We suggest that a further study of the relative phase Toffoli implementations and their use may yield other optimizations.1 aMaslov, Dmitri  uhttp://arxiv.org/abs/1508.03273