publication . Preprint . Article . 2019

Repeat-Until-Success circuits with fixed-point oblivious amplitude amplification

Gian Giacomo Guerreschi;
Open Access English
  • Published: 07 Feb 2019
Abstract
Certain quantum operations can be built more efficiently through a procedure known as Repeat-Until-Success. Differently from other non-deterministic quantum operations, this procedure provides a classical flag which certifies the success or failure of the procedure and, in the latter case, a recovery step allows the restoration of the quantum state to its original condition. The procedure can then be repeated until success is achieved. After success is certified, the RUS procedure can be equated to a coherent gate. However, this is not the case when the operation needs to be conditioned on the state of other qubits, possibly being in a superposition state. In th...
Persistent Identifiers
Subjects
free text keywords: Quantum Physics, Amplitude amplification, Qubit, Quantum, Electronic circuit, Quantum state, Superposition principle, Fixed point, Distortion, Topology, Physics
16 references, page 1 of 2

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

[2] Adam Paetznick and Krysta M. Svore. Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries. Quantum Information & Computation, 14(15 & 16):1277{1301, 2014.

[3] Alex Bocharov, Martin Roetteler, and Krysta M. Svore. E cient synthesis of universal repeat-until-success quantum circuits. Physical Review Letters, 114:080502, 2015.

[4] Yudong Cao, Gian Giacomo Guerreschi, and Alan Aspuru-Guzik. Quantum Neuron: an elementary building block for machine learning on quantum computers. arXiv:1711.11240, pages 1{30, 2017.

[5] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. Proceedings of the 2014 ACM Symposium on Theory of Computing, pages 283{292, 2014.

[6] Markus Reiher, Nathan Wiebe, Krysta M. Svore, David Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences USA, 114(29):7555{7560, 2017.

[7] Cody Jones. Low-overhead constructions for the fault-tolerant To oli gate. Physical Review A, 87:022328, 2013.

[8] Daniel S. Abrams and Seth Lloyd. Quantum algorithm providing exponential speed increase for nding eigenvalues and eigenvectors. Physical Review Letters, 83(24):5162{5165, dec 1999.

[9] Alan Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies. Science, 309:1704{1707, sep 2005.

[10] Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum amplitude ampli cation and estimation. Quantum Computation and Information, Contemporary Mathematics, 305:53{74, 2002.

[11] Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79(2):325{328, 1997. [OpenAIRE]

[12] Lov K. Grover. Fixed-point quantum search. Physical Review Letters, 95(15):150501, 2005. [OpenAIRE]

[13] Sourav Chakraborty, Jaikumar Radhakrishnan, and Nandakumar Raghunathan. Bounds for error reduction with few quantum queries. In Chandra Chekuri, Klaus Jansen, Jose D. P. Rolim, and Luca Trevisan, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 245{256, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.

[14] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. Fixed-point quantum search with an optimal number of queries. Physical Review Letters, 113(21):210501, 2014.

[15] Private communication with Yudong Cao.

16 references, page 1 of 2
Abstract
Certain quantum operations can be built more efficiently through a procedure known as Repeat-Until-Success. Differently from other non-deterministic quantum operations, this procedure provides a classical flag which certifies the success or failure of the procedure and, in the latter case, a recovery step allows the restoration of the quantum state to its original condition. The procedure can then be repeated until success is achieved. After success is certified, the RUS procedure can be equated to a coherent gate. However, this is not the case when the operation needs to be conditioned on the state of other qubits, possibly being in a superposition state. In th...
Persistent Identifiers
Subjects
free text keywords: Quantum Physics, Amplitude amplification, Qubit, Quantum, Electronic circuit, Quantum state, Superposition principle, Fixed point, Distortion, Topology, Physics
16 references, page 1 of 2

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

[2] Adam Paetznick and Krysta M. Svore. Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries. Quantum Information & Computation, 14(15 & 16):1277{1301, 2014.

[3] Alex Bocharov, Martin Roetteler, and Krysta M. Svore. E cient synthesis of universal repeat-until-success quantum circuits. Physical Review Letters, 114:080502, 2015.

[4] Yudong Cao, Gian Giacomo Guerreschi, and Alan Aspuru-Guzik. Quantum Neuron: an elementary building block for machine learning on quantum computers. arXiv:1711.11240, pages 1{30, 2017.

[5] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. Proceedings of the 2014 ACM Symposium on Theory of Computing, pages 283{292, 2014.

[6] Markus Reiher, Nathan Wiebe, Krysta M. Svore, David Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences USA, 114(29):7555{7560, 2017.

[7] Cody Jones. Low-overhead constructions for the fault-tolerant To oli gate. Physical Review A, 87:022328, 2013.

[8] Daniel S. Abrams and Seth Lloyd. Quantum algorithm providing exponential speed increase for nding eigenvalues and eigenvectors. Physical Review Letters, 83(24):5162{5165, dec 1999.

[9] Alan Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies. Science, 309:1704{1707, sep 2005.

[10] Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum amplitude ampli cation and estimation. Quantum Computation and Information, Contemporary Mathematics, 305:53{74, 2002.

[11] Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters, 79(2):325{328, 1997. [OpenAIRE]

[12] Lov K. Grover. Fixed-point quantum search. Physical Review Letters, 95(15):150501, 2005. [OpenAIRE]

[13] Sourav Chakraborty, Jaikumar Radhakrishnan, and Nandakumar Raghunathan. Bounds for error reduction with few quantum queries. In Chandra Chekuri, Klaus Jansen, Jose D. P. Rolim, and Luca Trevisan, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 245{256, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.

[14] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. Fixed-point quantum search with an optimal number of queries. Physical Review Letters, 113(21):210501, 2014.

[15] Private communication with Yudong Cao.

16 references, page 1 of 2
Any information missing or wrong?Report an Issue