Reducing the classical complexity of boson sampling via algebraic graph theory

An active area of current quantum information research is identifying tasks that intermediate-size quantum systems can potentially perform more efficiently than classical computers, such as the simulation of quantum many body systems. One such task is boson sampling, the determination of the output probabilities for photons (non-interacting bosons) scattered by the linear elements of an optical apparatus, such as beam splitters and phase shifters. Classically, this calculation is dominated by the determination of a matrix permanent, which scales exponentially with the number of bosons. The permanent can be expressed as the determinant of the adjacency matrix of a weighted hypercube graph, which doesn’t seem to be much help. However, unweighted hypercube graphs can be reduced via equitable vertex partitioning to weighted path graphs, whose determinants are exponentially more efficient to compute. In this work, we make use of these ideas in algebraic graph theory to explore the intriguing possibility that boson sampling probabilities could be efficiently computed classically for a subset of possible optical elements.