Add to GMail
Decision problems and shallow quantum circuits
10:00 AM to 11:00 AM
CSB 488
Joseph Slote, California Institute of Technology
Abstract: Constant-depth quantum circuits are powerful, capable of solving relational problems that are unconditionally hard for their classical counterparts [e.g., Watts et al. 2019]. It's natural to ask whether a decision separation exists as well, and as a first step in this direction we investigate whether a "QNC0 followed by AC0" hybrid model can approximate the Parity function—a task notoriously hard for AC0 alone.
We find evidence that despite QNC0's apparent power, it does little to help AC0 approximate Parity. In the case of a hybrid with a unitary QNC0 circuit, we give a Fourier-analytic proof that the model does little better than random guessing. To approach the case with a general QNC0 circuit, we reduce to questions about certain nonlocal and non-signaling games, where recent progress on approximate degree bounds [e.g., Sherstov 2018] provide mild no-gos for certain subclasses of AC0. In the interest of a full resolution, we also present work towards a "hybrid switching lemma": we show that non-signaling preprocessing doesn't increase decision tree depth.
Trustworthy Open Source: The Consequences of Success
11:50 AM to 12:40 PM
CSB 451 CS Auditorium
Eric Brewer, Google
Abstract:
Wide-spread use of open-source software is a remarkable achievement, but also creates a tremendous responsibility. How can we collectively step up to ensure open-source software is worthy of the trust the world now expects and deserves? We cover a range of structural and security challenges and how we might address them, including our hopes for a more sustainable future.
Bio:
Eric is a VP and Fellow at Google and leads technical areas including Kubernetes, Serverless, and Anthos. A recent focus is security for open-source software, including supply-chain risks and helping start the OpenSSF.
At Berkeley, he led work on cloud computing, network infrastructure, IoT, and the CAP Theorem. He has also led work on technology for developing regions, with projects in India, the Philippines, and Kenya among others, including communications, power, and health care.
In 1996, he co-founded Inktomi Corporation and helped lead it onto the NASDAQ 100. In 2000, working with President Clinton, Professor Brewer helped to create USA.gov, the official portal of the Federal government.
Major awards include membership in the NAE, AAAS, and AAA(&)S, the ACM Prize in Computing, and the ACM SIGOPS Mark Weiser Award.
Add to GMail