Dissertation Defense

Quantum computers are expected to dramatically outperform classical computers for certain computational problems. Originally developed for simulating quantum physics, quantum algorithms have been subsequently developed to address diverse computational challenges.

The connectivity between qubits is one of the many design aspects that go into building a quantum computer. Better connectivity makes it easier to perform arbitrary interacting operations in quantum algorithms, but it may also come with additional noise and may be costly to manufacture. Therefore, many proposals for scalable quantum computer architectures sacrifice connectivity to obtain better modularity and suppress noise. This poses a challenge to running quantum algorithms because simulating missing connectivity can come with significant overhead.

Quantum computers have come a long way since conception, and there is still a long way to go before the dream of universal, fault-tolerant computation is realized. In the near term, quantum computers will occupy a middle ground that is popularly known as the ``Noisy, Intermediate-Scale Quantum'' (or NISQ) regime. The NISQ era represents a transition in the nature of quantum devices from experimental to computational.

Besides potentially delivering a huge leap in computational power, quantum computers also offer an essential platform for simulating properties of quantum systems.  Consequently, various algorithms have been developed for approximating the dynamics of a target system on quantum computers. But generic quantum simulation algorithms---developed to simulate all Hamiltonians---are unlikely to result in optimal simulations of most physically relevant systems; optimal quantum algorithms need to exploit unique properties of target systems.

Quantum computing is the offspring of quantum mechanics and computer science, two great scientific fields founded in the 20th century. Quantum computing is a relatively young field and is recognized as having the potential to revolutionize science and technology in the coming century. The primary question in this field is essentially to ask which problems are feasible with potential quantum computers and which are not. In this dissertation, we study this question with a physical bent of mind.

In recent decades, the rapid development of quantum technologies has led to a new era of programmable platforms, enabling the realizations of quantum simulation and quantum computation.

Quantum computing devices can solve problems that are infeasible for classical computers.

One of the most fundamental and counterintuitive features of quantum mechanics is entanglement, which is central to many demonstrations of the quantum advantage. Studying quantum correlations generated by local measurements on an entangled physical system is one of the direct ways to gain insights into entanglement. The focus of this dissertation is to get better understanding of the hardness of determining if a given correlation is quantum, which is also known
as the membership problem of quantum correlations.

Simulating the Hamiltonian dynamics of quantum systems is one of the most promising applications of digital quantum computers. In this dissertation, we develop an understanding of quantum simulation algorithms concerning their design, analysis, implementation, and application.

The theories of optimization and machine learning answer foundational questions in computer science and lead to new algorithms for practical applications. While these topics have been extensively studied in the context of classical computing, their quantum counterparts are far from well-understood. In this thesis, we explore algorithms that bridge the gap between the fields of quantum computing and machine learning. First, we consider general optimization problems with only function evaluations.