publication . Preprint . Article . 2014

Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits

Nathan Wiebe; Martin Roetteler;
Open Access English
  • Published: 08 Jun 2014
Abstract
We develop a method for approximate synthesis of single--qubit rotations of the form $e^{-i f(\phi_1,\ldots,\phi_k)X}$ that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions $f$ can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as $3$ ancilla qubits, one can obtain RUS circuits for approximate m...
Persistent Identifiers
Subjects
arXiv: Computer Science::Emerging Technologies
free text keywords: Quantum Physics, Computer Science - Numerical Analysis, Nuclear and High Energy Physics, Theoretical Computer Science, Mathematical Physics, Computational Theory and Mathematics, General Physics and Astronomy, Statistical and Nonlinear Physics
Related Organizations
31 references, page 1 of 3

[10] Thomas G Draper, Samuel A Kutin, Eric M Rains, and Krysta M Svore. A logarithmic-depth quantum carry-lookahead adder. Quantum Information & Computation, 6(4):351{369, 2006.

[11] Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and Moulton David P. A new quantum ripple-carry addition circuit. 2004. arXiv preprint quant-ph/0410184.

[12] Yasuhiro Takahashi and Noboru Kunihiro. A linear-size quantum circuit for addition with no ancillary qubits. Quantum Information & Computation, 5(6):440{448, 2005.

[13] Stephane Beauregard. Circuit for Shor's algorithm using 2n + 3 qubits. arXiv preprint quant-ph/0205095, 2002.

[14] Rodney van Meter and Kohei M Itoh. Fast quantum modular exponentiation. Phys. Rev. A, 71(5):052320, 2005.

[15] Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub, and Sabre Kais. Quantum algorithm and circuit design solving the Poisson equation. New Journal of Physics, 15(1):013021, 2013.

[16] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Fast and e cient exact synthesis of single-qubit unitaries generated by cli ord and t gates. Quantum Information & Computation, 13(7-8):607{630, 2013.

[17] Nathan Wiebe and Vadym Kliuchnikov. Floating point representations in quantum circuit synthesis. New Journal of Physics, 15(9):093041, 2013.

[18] Adam Paetznick and Krysta M Svore. Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries. arXiv preprint arXiv:1311.1074, 2013. [OpenAIRE]

[19] Alex Bocharov, Martin Roetteler, and Krysta M Svore. E cient synthesis of universal Repeat-Until-Success circuits. arXiv preprint arXiv:1404.5320, 2014.

[20] Neil J Ross and Peter Selinger. Optimal ancilla-free cli ord+ t approximation of z-rotations. arXiv preprint arXiv:1403.2975, 2014.

[21] Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data tting. Phys. Rev. Lett., 109:050505, Aug 2012.

[22] Guoming Wang. Quantum algorithms for curve tting. arXiv preprint arXiv:1402.0660, 2014.

[23] Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum amplitude ampli cation and estimation. arXiv preprint quant-ph/0005055, 2000.

[24] Emanuel Knill, Raymond La amme, and Gerald J Milburn. A scheme for e cient quantum computation with linear optics. nature, 409(6816):46{52, 2001.

31 references, page 1 of 3
Abstract
We develop a method for approximate synthesis of single--qubit rotations of the form $e^{-i f(\phi_1,\ldots,\phi_k)X}$ that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions $f$ can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as $3$ ancilla qubits, one can obtain RUS circuits for approximate m...
Persistent Identifiers
Subjects
arXiv: Computer Science::Emerging Technologies
free text keywords: Quantum Physics, Computer Science - Numerical Analysis, Nuclear and High Energy Physics, Theoretical Computer Science, Mathematical Physics, Computational Theory and Mathematics, General Physics and Astronomy, Statistical and Nonlinear Physics
Related Organizations
31 references, page 1 of 3

[10] Thomas G Draper, Samuel A Kutin, Eric M Rains, and Krysta M Svore. A logarithmic-depth quantum carry-lookahead adder. Quantum Information & Computation, 6(4):351{369, 2006.

[11] Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and Moulton David P. A new quantum ripple-carry addition circuit. 2004. arXiv preprint quant-ph/0410184.

[12] Yasuhiro Takahashi and Noboru Kunihiro. A linear-size quantum circuit for addition with no ancillary qubits. Quantum Information & Computation, 5(6):440{448, 2005.

[13] Stephane Beauregard. Circuit for Shor's algorithm using 2n + 3 qubits. arXiv preprint quant-ph/0205095, 2002.

[14] Rodney van Meter and Kohei M Itoh. Fast quantum modular exponentiation. Phys. Rev. A, 71(5):052320, 2005.

[15] Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub, and Sabre Kais. Quantum algorithm and circuit design solving the Poisson equation. New Journal of Physics, 15(1):013021, 2013.

[16] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Fast and e cient exact synthesis of single-qubit unitaries generated by cli ord and t gates. Quantum Information & Computation, 13(7-8):607{630, 2013.

[17] Nathan Wiebe and Vadym Kliuchnikov. Floating point representations in quantum circuit synthesis. New Journal of Physics, 15(9):093041, 2013.

[18] Adam Paetznick and Krysta M Svore. Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries. arXiv preprint arXiv:1311.1074, 2013. [OpenAIRE]

[19] Alex Bocharov, Martin Roetteler, and Krysta M Svore. E cient synthesis of universal Repeat-Until-Success circuits. arXiv preprint arXiv:1404.5320, 2014.

[20] Neil J Ross and Peter Selinger. Optimal ancilla-free cli ord+ t approximation of z-rotations. arXiv preprint arXiv:1403.2975, 2014.

[21] Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data tting. Phys. Rev. Lett., 109:050505, Aug 2012.

[22] Guoming Wang. Quantum algorithms for curve tting. arXiv preprint arXiv:1402.0660, 2014.

[23] Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum amplitude ampli cation and estimation. arXiv preprint quant-ph/0005055, 2000.

[24] Emanuel Knill, Raymond La amme, and Gerald J Milburn. A scheme for e cient quantum computation with linear optics. nature, 409(6816):46{52, 2001.

31 references, page 1 of 3
Any information missing or wrong?Report an Issue