Lower Bounds

Takashi Hirayama, Ryo Endo, Katsuhisa Yamanaka

This paper presents an improved lower bound, denoted as$v$, on the number of gates in Toffoli-based reversible circuits that realize a given reversible logic function. The previous lower bound$\sigma-lb$used 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 bound$v$is better than the previous lower bound$\sigma-lb$by 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.

Xifan Zheng, Reihaneh Safavi–Naini, Hadi Ahmadi

Hao‐Fan Wang, Shao-Ming Fei

We provide a class of lower bounds for concurrence based on symmetric measurements. We show that our lower bounds estimate the quantum entanglement better than some existing lower bounds by detailed examples. Moreover, our lower bounds can be experimentally identified without state tomography.

Arvid J. Bessen

We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower-bound approaches to the case where the oracle $Q$ is given by controlled powers ${Q}^{p}$ of $Q$, as it is, for example, in Shor's order-finding algorithm. In this setting we will prove a $\ensuremath{\Omega}(\mathrm{log}\phantom{\rule{0.2em}{0ex}}1∕ϵ)$ lower bound for the number of applications of ${Q}^{{p}_{1}}$, ${Q}^{{p}_{2}},\dots{}$. This bound is tight due to a matching upper bound. We obtain the lower bound using a technique based on frequency analysis.

Richard Cleve, Alex May

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, $\sqrt{\text{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.