Abstract:
Real quantum computers are noisy physical devices whose interactions are shaped by three-dimensional geometry. This leads to the guiding question of the talk: what is the computational power of quantum computers under realistic physical constraints, and how can we enable it?
In this talk, I will describe three lines of my research advancing this perspective, in quantum complexity theory, algorithms, and error correction. First, in quantum complexity theory, I establish the strongest currently known unconditional separation between noisy, shallow-depth, 3D-local quantum circuits and comparable classical AC0 circuits, namely shallow-depth Boolean circuits with unbounded fan-in AND and OR gates. Second, in quantum algorithms, I revisit algorithm design from the perspective of the underlying hardware. For hybrid qubit–oscillator systems with experimentally available operations, I give a space-efficient polynomial-time integer-factoring algorithm using only three oscillators and one qubit. Finally, in quantum error correction, I study 3D codes with optimal parameters. I identify a new instantiation of a recent code construction that achieves these parameters without requiring good quantum LDPC codes as input, and I design decoders. I then prove memory-time lower bounds establishing partial self-correction for these codes, and I support this behavior with numerics.
We would like to cordially invite you to a special seminar of
Libor Caha (Technical University of Munich, Germany)which will take place on
July 2nd at 14:00 ONLINE.
Zoom link:
https://us06web.zoom.us/j/84248911743?pwd=ZsiAOQbRgYCm5IFsArOnb18Fj5IsZh.1Meeting ID:
842 4891 1743Passcode:
394021
