This paper presents an improved lower bound, denoted asv, on the number of gates in Toffoli-based reversible circuits that realize a given reversible logic function. The previous lower boundσ−lbused the characteristic vectors of reversible functions to formulate the theory of lower bounds. We carefully investigate cofactors of reversible functions to refine the characteristic vectors, and obtain a new theoretical basis for improving lower bounds. We show that the proposed lower boundvis better than the previous lower boundσ−lbby making both mathematical and experimental comparisons. Although the gain of refinement is not so significant in the experiments, an improvement of lower bounds is valuable as a theoretical achievement.
Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, SWAP, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.