research
∙
08/10/2023
Testing GPT-4 with Wolfram Alpha and Code Interpreter plug-ins on math and science problems
This report describes a test of the large language model GPT-4 with the ...
share
research
∙
03/02/2023
Certified Randomness from Quantum Supremacy
We propose an application for near-term quantum devices: namely, generat...
research
∙
02/20/2023
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
Relational problems (those with many possible valid outputs) are differe...
research
∙
10/27/2022
Discrete Bulk Reconstruction
According to the AdS/CFT correspondence, the geometries of certain space...
research
∙
09/14/2022
How Much Structure Is Needed for Huge Quantum Speedups?
I survey, for a general scientific audience, three decades of research i...
research
∙
09/07/2022
Learning Distributions over Quantum Measurement Outcomes
Shadow tomography for quantum states provides a sample efficient approac...
research
∙
04/25/2022
A very preliminary analysis of DALL-E 2
The DALL-E 2 system generates original synthetic images corresponding to...
research
∙
11/19/2021
The Acrobatics of BQP
One can fix the randomness used by a randomized algorithm, but there is ...
research
∙
09/14/2021
Open Problems Related to Quantum Query Complexity
I offer a case that quantum query complexity still has loads of enticing...
research
∙
05/31/2021
An Automated Approach to the Collatz Conjecture
We explore the Collatz conjecture and its variants through the lens of t...
research
∙
02/20/2021
Efficient Learning of Non-Interacting Fermion Distributions
We give an efficient classical algorithm that recovers the distribution ...
research
∙
10/23/2020
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Based on the recent breakthrough of Huang (2019), we show that for any t...
research
∙
04/28/2020
Quantum Implications of Huang's Sensitivity Theorem
Based on the recent breakthrough of Huang (2019), we show that for any t...
research
∙
04/20/2020
Quantum Copy-Protection from Hidden Subspaces
Quantum copy-protection is an innovative idea that uses the no-cloning p...
research
∙
11/05/2019
On the Quantum Complexity of Closest Pair and Related Problems
The closest pair problem is a fundamental problem of computational geome...
research
∙
10/26/2019
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
Recently, Google announced the first demonstration of quantum computatio...
research
∙
08/28/2019
Quantum Approximate Counting, Simplified
In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorith...
research
∙
04/18/2019
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
This paper proves new limitations on the power of quantum computers to s...
research
∙
12/11/2018
A Quantum Query Complexity Trichotomy for Regular Languages
We present a trichotomy theorem for the quantum query complexity of regu...
research
∙
08/07/2018
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials
We consider the following problem: estimate the size of a nonempty set S...
research
∙
05/22/2018
PDQP/qpoly = ALL
We show that combining two different hypothetical enhancements to quantu...
research
∙
02/25/2018
Online Learning of Quantum States
Suppose we have many copies of an unknown n-qubit state ρ. We measure so...
research
∙
11/03/2017
Shadow Tomography of Quantum States
We introduce the problem of *shadow tomography*: given an unknown D-dime...
research
∙
06/11/2014
Quantum POMDPs
We present quantum observable Markov decision processes (QOMDPs), the qu...
research
∙
06/02/2013