Fetching the paper…

Reading the bibliography…

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search · Around

2021

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search

Rosenthal, Gregory

Original
PDF
Post on X

Understand

We prove that any $n$-qubit unitary can be implemented (i) approximately in time $\tilde O\big(2^{n/2}\big)$ with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth $\tilde O\big(2^{n/2}\big)$ with one- and two-qubit gates and $2^{O(n)}$ ancillae.

The proofs involve similar reductions to Grover search.
The proof of (ii) also involves a linear-depth construction of arbitrary quantum states using one- and two-qubit gates (in fact, this can be improved to constant depth with the addition of fanout and generalized Toffoli gates) which may be of independent interest.
We also prove a matching $\Omega\big(2^{n/2}\big)$ lower bound for (i) and (ii) for a certain class of implementations.

Built on

“The synthesis of two-terminal switching circuits”
Claude Shannon · 1949
Earlier work this paper cites.
“On a method of circuit synthesis”
Oleg Lupanov · 1958
Earlier work this paper cites.
“Almost optimal lower bounds for small depth circuits”
Johan Håstad · 1986
Earlier work this paper cites.
“Counting, fanout, and the complexity of quantum ACC”
Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett · 2002
Earlier work this paper cites.
“Quantum lower bounds by quantum arguments”
Andris Ambainis · 2002
Earlier work this paper cites.
“Quantum fan-out is powerful”
Peter Høyer and Robert Špalek · 2005
Earlier work this paper cites.
“Quantum computing and communications: an engineering approach”
Sándor Imre and Ferenc Balázs · 2005
Earlier work this paper cites.
“The Solovay–Kitaev algorithm”
Christopher M. Dawson and Michael A. Nielsen · 2006
Earlier work this paper cites.

Similar

“Quantum versus classical proofs and advice”
Scott Aaronson and Greg Kuperberg · 2007
Cited alongside, same era.
“Quantum computation and quantum information: 10th anniversary edition”
Michael A. Nielsen and Isaac L. Chuang · 2010
Cited alongside, same era.
“Inverting a permutation is as hard as unordered search”
Original
Ashwin Nayak · 2011
Cited alongside, same era.
“Boolean function complexity”
Stasys Jukna · 2012
Cited alongside, same era.
“The complexity of quantum states and transformations: from quantum money to black holes”
Original
Scott Aaronson · 2016
Cited alongside, same era.
“Collapse of the hierarchy of constant-depth exact quantum circuits”

Then

Personal communication
Nathan Wiebe (2021) · 2021
Closest in time.
“Quantum search-to-decision reductions and the state synthesis problem”
Original
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen · 2022
Closest in time.
“Quantum state preparation with optimal circuit depth: Implementations and applications”
Original
Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan · 2022
Closest in time.
“Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis”
Original
Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang · 2023
Closest in time.
“Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits”
Original
Pei Yuan and Shengyu Zhang · 2023

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…

Yasuhiro Takahashi and Seiichiro Tani · 2016

Cited alongside, same era.

“Open problems related to quantum query complexity”

Scott Aaronson · 2021

Cited alongside, same era.

Closest in time.

“A one-query lower bound for unitary synthesis and breaking quantum cryptography”

Alex Lombardi, Fermi Ma, and John Wright · 2024

Closest in time.

“Efficient quantum state synthesis with one query”

Gregory Rosenthal · 2024

Closest in time.