From Simulatability to Universality of Continuous-Variable Quantum Computers

This book makes a significant contribution to the field of quantum computing by exploring the boundary between classical and quantum computational power. While quantum computers offer a revolutionary approach to solving complex problems, we still do not fully understand which problems will benefit from the power of quantum computing. This book explores this question by demonstrating that large classes of quantum circuits can be simulated efficiently on a classical computer. The primary focus of the thesis is on a specific type of quantum computing, namely, continuous-variable quantum computing. This approach, which operates with continuous ranges of values, similar to how analogue systems can represent any value within a range, is a promising direction for the future of computing. Previous studies have demonstrated that when a quantum algorithm contains certain features, it implies that a classical device can achieve the same results in approximately the same time. However, this book turns these results on their head, instead demonstrating that certain quantum algorithms do not fit the previous criteria and can still be easily simulated by classical devices. The book also identifies a theoretically grounded condition that proves that algorithms satisfying the condition is always able to achieve an advantage over classical devices.