Dissertation Defense

A quantum speedup occurs when a computational problem can be solved faster on a quantum computer than on a classical computer. This thesis studies the circumstances under which quantum speedups can arise from three perspectives. First, we study the structure of the problem. We show how a problem’s symmetries relate to whether it can admit a polynomial or superpolynomial quantum speedup. In particular, we show that the computation of any partial function of a hypergraph’s adjacency matrix can only admit a polynomial speedup.

Quantum many-body systems with long-range interactions—such as those that decay as a power-law in the distance between particles—are promising candidates for quantum information processors. Due to their high degree of connectivity, they are potentially capable of generating entanglement more quickly than systems limited to local interactions, which may lead to faster computational speeds.

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.