Scott Aaronson | DeepAI

AI Chat

Featured Co-authors

Elad Hazan
65 publications
Xinyi Chen
29 publications
Ruizhe Zhang
22 publications
Chunhao Wang
19 publications
Robin Kothari
16 publications
William Kretschmer
16 publications
Ernest Davis
16 publications
Marijn J. H. Heule
15 publications
Avishay Tal
13 publications
Nai-Hui Chia
13 publications
Shih-Han Hung
12 publications

∙ 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 ...

0 Ernest Davis, et al. ∙

∙ 03/02/2023

Certified Randomness from Quantum Supremacy

We propose an application for near-term quantum devices: namely, generat...

0 Scott Aaronson, et al. ∙

∙ 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...

0 Scott Aaronson, et al. ∙

∙ 10/27/2022

Discrete Bulk Reconstruction

According to the AdS/CFT correspondence, the geometries of certain space...

0 Scott Aaronson, et al. ∙

∙ 09/14/2022

How Much Structure Is Needed for Huge Quantum Speedups?

I survey, for a general scientific audience, three decades of research i...

0 Scott Aaronson, et al. ∙

∙ 09/07/2022

Learning Distributions over Quantum Measurement Outcomes

Shadow tomography for quantum states provides a sample efficient approac...

0 Weiyuan Gong, et al. ∙

∙ 04/25/2022

A very preliminary analysis of DALL-E 2

The DALL-E 2 system generates original synthetic images corresponding to...

47 Gary Marcus, et al. ∙

∙ 11/19/2021

The Acrobatics of BQP

One can fix the randomness used by a randomized algorithm, but there is ...

0 Scott Aaronson, et al. ∙

∙ 09/14/2021

Open Problems Related to Quantum Query Complexity

I offer a case that quantum query complexity still has loads of enticing...

0 Scott Aaronson, et al. ∙

∙ 05/31/2021

An Automated Approach to the Collatz Conjecture

We explore the Collatz conjecture and its variants through the lens of t...

0 Emre Yolcu, et al. ∙

∙ 02/20/2021

Efficient Learning of Non-Interacting Fermion Distributions

We give an efficient classical algorithm that recovers the distribution ...

0 Scott Aaronson, et al. ∙

∙ 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...

0 Scott Aaronson, et al. ∙

∙ 04/28/2020

Quantum Implications of Huang's Sensitivity Theorem

Based on the recent breakthrough of Huang (2019), we show that for any t...

0 Scott Aaronson, et al. ∙

∙ 04/20/2020

Quantum Copy-Protection from Hidden Subspaces

Quantum copy-protection is an innovative idea that uses the no-cloning p...

0 Scott Aaronson, et al. ∙

∙ 11/05/2019

On the Quantum Complexity of Closest Pair and Related Problems

The closest pair problem is a fundamental problem of computational geome...

0 Scott Aaronson, et al. ∙

∙ 10/26/2019

On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking

Recently, Google announced the first demonstration of quantum computatio...

0 Scott Aaronson, et al. ∙

∙ 08/28/2019

Quantum Approximate Counting, Simplified

In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorith...

0 Scott Aaronson, et al. ∙

∙ 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...

0 Scott Aaronson, et al. ∙

∙ 12/11/2018

A Quantum Query Complexity Trichotomy for Regular Languages

We present a trichotomy theorem for the quantum query complexity of regu...

0 Scott Aaronson, et al. ∙

∙ 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...

0 Scott Aaronson, et al. ∙

∙ 05/22/2018

PDQP/qpoly = ALL

We show that combining two different hypothetical enhancements to quantu...

0 Scott Aaronson, et al. ∙

∙ 02/25/2018

Online Learning of Quantum States

Suppose we have many copies of an unknown n-qubit state ρ. We measure so...

0 Scott Aaronson, et al. ∙

∙ 11/03/2017

Shadow Tomography of Quantum States

We introduce the problem of *shadow tomography*: given an unknown D-dime...

0 Scott Aaronson, et al. ∙

∙ 06/11/2014

Quantum POMDPs

We present quantum observable Markov decision processes (QOMDPs), the qu...

0 Jennifer Barry, et al. ∙

∙ 06/02/2013

The Ghost in the Quantum Turing Machine

In honor of Alan Turing's hundredth birthday, I unwisely set out some th...

0 Scott Aaronson, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world