Fetching the paper…
Reading the bibliography…
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any $n$-qubit unitary $U$ can be implemented by an efficient quantum algorithm $A$ augmented with an oracle that computes an arbitrary Boolean function $f$.
The synthesis of two-terminal switching circuits
Claude Shannon · 1949
Earlier work this paper cites.
Relative to a random oracle a a , P a ≠ NP a ≠ co − NP a \mathrm{P}^{a}\neq\mathrm{NP}^{a}\neq\mathrm{co-NP}^{a} with probability 1
Charles Bennett and John Gill · 1981
Earlier work this paper cites.
Limits on the provable consequences of one-way permutations
Russell Impagliazzo and Steven Rudich · 1989
Earlier work this paper cites.
Quantum complexity theory
Ethan Bernstein and Umesh Vazirani · 1997
Earlier work this paper cites.
Quantum versus classical proofs and advice
Scott Aaronson and Greg Kuperberg · 2007
Earlier work this paper cites.
Quantum computation and quantum information
Michael Nielsen and Isaac Chuang · 2010
Earlier work this paper cites.
A simple decoupling inequality in probability theory
Roman Vershynin · 2011
Earlier work this paper cites.
Linear algebra
Peter Petersen · 2012
Earlier work this paper cites.
User-friendly tail bounds for sums of random matrices
Joel Tropp · 2012
Earlier work this paper cites.
Quantum principal component analysis
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost · 2014
Earlier work this paper cites.
An introduction to matrix concentration inequalities
Joel Tropp · 2015
Earlier work this paper cites.
The complexity of quantum states and transformations: from quantum money to black holes
Scott Aaronson · 2016
Earlier work this paper cites.
Structured random matrices
Ramon van Handel · 2017
Earlier work this paper cites.
Pseudorandom quantum states
Zhengfeng Ji, Yi-Kai Liu, and Fang Song · 2018
Earlier work this paper cites.
High-dimensional probability: an introduction with applications in data science
Roman Vershynin · 2018
Cited alongside, same era.
The theory of quantum information
John Watrous · 2018
Cited alongside, same era.
Quantum random oracle model with auxiliary input
Minki Hhan, Keita Xagawa, and Takashi Yamakawa · 2019
Cited alongside, same era.
Tight quantum time-space tradeoffs for function inversion
Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian · 2020
Cited alongside, same era.
Lower bounds for function inversion with quantum advice
Kai-Min Chung, Tai-Ning Liao, and Luowen Qian · 2020
Cited alongside, same era.
Open problems related to quantum query complexity, comment #36, 2021
Scott Aaronson · 2021
Cited alongside, same era.
Interactive proofs for synthesizing quantum states and unitaries
Gregory Rosenthal and Henry Yuen · 2022
Later among the works it cites.
General properties of quantum bit commitments
Jun Yan · 2022
Later among the works it cites.
Lecture 6 from COMS E6998: Frontiers of quantum complexity and cryptography
Henry Yuen · 2022
Later among the works it cites.
Lecture 7 from COMS E6998: Frontiers of quantum complexity and cryptography
Henry Yuen · 2022
Later among the works it cites.
On the computational hardness needed for quantum cryptography
Zvika Brakerski, Ran Canetti, and Luowen Qian · 2023
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
One-way functions imply secure computation in a quantum world
James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma · 2021
Cited alongside, same era.
Oblivious transfer is in MiniQCrypt
Alex Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan · 2021
Cited alongside, same era.
Quantum pseudorandomness and classical complexity
William Kretschmer · 2021
Cited alongside, same era.
Cryptography from pseudorandom quantum states
Prabhanjan Ananth, Luowen Qian, and Henry Yuen · 2022
Cited alongside, same era.
QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
Anne Broadbent and Alex Grilo · 2022
Cited alongside, same era.
Quantum search-to-decision reductions and the state synthesis problem
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen · 2022
Cited alongside, same era.
John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen · 2023
Closest in time.
Quantum Merlin-Arthur proof systems for synthesizing quantum states
Hugo Delavenne, François Le Gall, Yupan Liu, and Masayuki Miyamoto · 2023
Closest in time.
Commitments to quantum states
Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry · 2023
Closest in time.
Quantum cryptography in Algorithmica
William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal · 2023
Closest in time.
Does quantum cryptography imply classical lower bounds?
William Kretschmer · 2023
Closest in time.
Non-uniformity and quantum advice in the quantum random oracle model
Qipeng Liu · 2023
Closest in time.
stateQIP= statePSPACE
Tony Metger and Henry Yuen · 2023
Closest in time.
Efficient quantum state synthesis with one query
Gregory Rosenthal · 2023
Closest in time.
Quantum State and Unitary Complexity
Gregory Rosenthal · 2023
Closest in time.