Quantum computing does not just provide speedups over classical algorithms, but is also a source of new computational and cryptographic questions that bridge computer science and physics. Such questions impact our conceptual understanding of quantum algorithms and randomness, and open up new cryptographic applications for near-term quantum devices. I will illustrate this theme with two main results: First, I will explain a new connection between quantum and classical randomness, which has allowed us to prove the long-standing spectral gap conjecture for random quantum circuits. This enables more efficient and practical randomized quantum algorithms and has surprising implications for circuit complexity and quantum gravity. Second, I will show how understanding the interplay between quantum uncertainty and entanglement has enabled us to give the first general security proof for quantum key distribution, a foundational primitive in quantum cryptography that is already commercially available today.