Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with AdS/CFT:
TR16-109 | 18th July 2016
Scott Aaronson

The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, ... more >>>

TR20-146 | 24th September 2020
Scott Aaronson, Yosi Atia, Leonard Susskind

On the Hardness of Detecting Macroscopic Superpositions

When is decoherence "effectively irreversible"? Here we examine this central question of quantum foundations using the tools of quantum computational complexity. We prove that, if one had a quantum circuit to determine if a system was in an equal superposition of two orthogonal states (for example, the $|$Alive$\rangle$ and $|$Dead$\rangle$ ... more >>>

ISSN 1433-8092 | Imprint