IQC faculty Michele Mosca and Ashwin Nayak, together with former postdoctoral fellow Tzu-Chieh Wei, recently published a paper in Physical Review Letters investigating the computational complexity of bosons. Titled "Interacting boson problems can be QMA-hard", the paper examines whether problems using bosons (particles that prefer to bunch together) are computationally "easy," as they have been typically regarded. The counterparts of bosons, called fermions, prefer to stay away from another. Fermionic problems are usually considered computationally hard (often attributed to the infamous "sign problem") whereas bosonic problems have been thought to be "easy."
The team from IQC investigated whether this is actually the case. The researchers utilized the tools in both computer science and physics to demonstrate that two families of bosonic problems are indeed "QMA-hard" (referring to Quantum Merlin-Arthur problems, which are considered difficult even for quantum computers). The researchers also demonstrated the problems were complete in QMA.
The first family of the problems is to determine the ground-state energy of interacting bosons with generic two-body interactions. This can actually be understood from the point of view of simulating spin systems using bosons, manifest in the linear-optics quantum computation scheme of Knill, Laflamme and Milburn, where photons are used to simulate qubits and perform universal quantum computation. Since there exist Hamiltonians of spin that are known to be QMA-hard to determine their ground-state energy, the corresponding (bosonic) Hamiltonians simulated by bosons will be hard.
The second family of the problems is the so-called N-representability, in which you are given a description of a two-particle state and are asked to determine whether it can be obtained from an N-particle state by removing all but two of the particles. The fermionic version of this problem finds its application in quantum chemistry, as an efficient algorithm for N-representability would enable precise and efficient determination of, for example, molecular binding energy. But fermionic N-representability has recently been shown to be QMA-complete.
It came as a surprise to these researchers that bosonic version of N-representability problem is QMA-complete as well. These QMA-hard results imply, among other things, that developing various approximation schemes, either classical or quantum, is a necessary route to the understanding of many-particle systems.
About IQC: Founded in 2002, the mission of the Institute for Quantum Computing (IQC) is to aggressively explore and advance the application of quantum mechanical systems to a vast array of relevant information processing techniques.
A part of the University of Waterloo, Waterloo, Ont., Canada, IQC creates a truly unique environment fostering cutting-edge research and collaboration between researchers in the areas of computer, engineering, mathematical and physical sciences.
At the time of this release, IQC has 17 faculty members, 22 postdoctoral fellows and over 55 students and research assistants, as well as a support staff of 18.
The Institute for Quantum Computing acknowledges the support of the Government of Canada through Industry Canada and the Government of Ontario through the Ministry of Research and Innovation.