2018

Trading T gates for dirty qubits in state preparation and unitary synthesis

Low, Guang Hao, Kliuchnikov, Vadym, Schaeffer, Luke

Understand

Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g.

Clifford+T is a key subroutine in quantum computation.
As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates.
We present a quantum algorithm for preparing any dimension-$N$ pure quantum state specified by a list of $N$ classical numbers, that realizes a trade-off between space and T-gates.

Built on

“Unitary triangularization of a nonsymmetric matrix”
Alston S. Householder · 1958
Earlier work this paper cites.
“Elementary gates for quantum computation”
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter · 1995
Earlier work this paper cites.
“Approximation by quantum circuits” (1995)
E. Knill · 1995
Earlier work this paper cites.
“Efficient discrete approximations of quantum gates”
Aram W. Harrow, Benjamin Recht, and Isaac L. Chuang · 2002
Earlier work this paper cites.
“Creating superpositions that correspond to efficiently integrable probability distributions” (2002)
Lov Grover and Terry Rudolph · 2002
Earlier work this paper cites.
“Adiabatic quantum state generation and statistical zero knowledge”
Dorit Aharonov and Amnon Ta-Shma · 2003
Earlier work this paper cites.
“A new quantum ripple-carry addition circuit” (2004)
Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton · 2004
Earlier work this paper cites.
“Algorithmic complexity and entanglement of quantum states”
Caterina E. Mora and Hans J. Briegel · 2005
Earlier work this paper cites.
“Synthesis of quantum-logic circuits”
V. V. Shende, S. S. Bullock, and I. L. Markov · 2006
Earlier work this paper cites.
“Quantum algorithm for linear systems of equations”
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd · 2009
Earlier work this paper cites.
“Quantum computation and quantum information”
Michael A. Nielsen and Isaac L. Chuang · 2010
Earlier work this paper cites.
“Quantum algorithm for data fitting”
Nathan Wiebe, Daniel Braun, and Seth Lloyd · 2012
Earlier work this paper cites.
“Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates”
Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca · 2013
Earlier work this paper cites.
“Synthesis of unitaries with Clifford+T circuits” (2013)
Original
Vadym Kliuchnikov · 2013
Earlier work this paper cites.
“Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits”
Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca · 2013
Earlier work this paper cites.

Similar

“Quantum principal component analysis”
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost · 2014
Cited alongside, same era.
“An algorithm for the T-count”
David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo · 2014
Cited alongside, same era.
“Simulating Hamiltonian dynamics with a truncated Taylor series”
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma · 2015
Cited alongside, same era.
“Optimal ancilla-free Clifford+T approximation of Z-rotations”
Neil J Ross and Peter Selinger · 2016
Cited alongside, same era.
“The complexity of quantum states and transformations: From quantum money to black holes” (2016)
Original
Scott Aaronson · 2016
Cited alongside, same era.
“Optimal Hamiltonian simulation by quantum signal processing”
Guang Hao Low and Isaac L. Chuang · 2017
Cited alongside, same era.
“Hamiltonian simulation by uniform spectral amplification” (2017)
Original
Guang Hao Low and Isaac L. Chuang · 2017
Cited alongside, same era.
“Factoring using 2n + 2 qubits with Toffoli based modular multiplication”
Thomas Häner, Martin Roetteler, and Krysta M Svore · 2017
Cited alongside, same era.
“Encoding electronic spectra in quantum circuits with linear T complexity”
Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven · 2018
Cited alongside, same era.
“Toward the first quantum simulation with quantum speedup”
Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su · 2018
Cited alongside, same era.
“Halving the cost of quantum addition”
Craig Gidney · 2018
Cited alongside, same era.
“A game of surface codes: large-scale quantum computing with lattice surgery”
Daniel Litinski · 2019
Cited alongside, same era.

Then

“Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization”
Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush · 2019
Closest in time.
“A quantum algorithm for simulating non-sparse Hamiltonians”
Chunhao Wang and Leonard Wossnig · 2020
Closest in time.
“Lower bounds on the non-clifford resources for quantum computations”
Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov · 2020
Closest in time.
“Fault-tolerant resource estimation of quantum random-access memories”
Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca · 2020
Closest in time.
“Quantum algorithms for quantum chemistry and quantum materials science”
Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan · 2020
Closest in time.
“Compilation of fault-tolerant quantum heuristics for combinatorial optimization”
Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush · 2020
Closest in time.
“Halving the cost of quantum multiplexed rotations” (2021)
Original
Guang Hao Low · 2021
Closest in time.
“Resilience of quantum random access memory to generic noise”
Connor T. Hann, Gideon Lee, S.M. Girvin, and Liang Jiang · 2021
Closest in time.
“Quantum computing enhanced computational catalysis”
Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer · 2021
Closest in time.
“Even more efficient quantum computations of chemistry through tensor hypercontraction”
Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush · 2021
Closest in time.
“Space-time optimized table lookup” (2022)
Original
Thomas Häner, Vadym Kliuchnikov, Martin Roetteler, and Mathias Soeken · 2022
Closest in time.
“Quantum resources required to block-encode a matrix of classical data”
B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng · 2022
Closest in time.
“Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis”
Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang · 2023
Closest in time.
“Spacetime-efficient low-depth quantum state preparation with applications”
Kaiwen Gui, Alexander M. Dalzell, Alessandro Achille, Martin Suchara, and Frederic T. Chong · 2024
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…