Certifying Quantum Separability with Adaptive Polytopes

Thank you for your effort in reviewing our manuscript. We have revised the manuscript taking your comments into account. Below we discuss the points you have raised.

**The Reviewer wrote:**

I thank the Authors for replying to my previous report. However, I am not sure if I can find the amendmments satisfactory enough at this stage. The Authors claim that the Algorithm certifies separability and such a message can be read from the description of the algorithm. Moreover, Figure 5 suggests that convergence may be expected even for 2 iterations. However, I, and I believve the Reader, would like to know about the omplexity of the algorithm. In each step, a semi-definite program must be run, and we do not know much about optimizing tau operators. I think it would be beneficial to give runtimes for a few examples discusssed in the paper in context of the specs of a computer used.

**Our response:**

Thank you for your comment. We agree, and now explicitly give some examples of run times for certain states so that the readers have an idea of how long it typically takes. This is given at the end of section 2.2 for random 5x5-dimensional states (order of seconds in a normal desktop) and in the Caption of Table 1 for multiparticle states (order of minutes in a normal desktop).


**The Reviewer wrote:**

Another question that would need to be discussed is the symmetry under the swap of particles. The algorithm is presented as for a system of two identical subsystems. Shall the Reader assume that in case of, say, 2x4 we simply expand the space to 4x4? But what about taus being now sigmas?

**Our response:**

No, the spaces do not have to be expanded. Our algorithm switches between optimisations on Alice and Bob's generalized Bloch spheres which may have different dimensions. Importantly, in the third step of the algorithm, in which the systems A and B are exchanged, a swap operation on the state is performed which transforms a 2x4-dimensional state into an 4x2-dimensional state. Hence, every odd iteration step involves an optimisation of 2x2 matrices, while every even iteration step involves an optimisation of 4x4 matrices (or the other way around). In this way, the algorithm does work normally in the asymmetric setting without any additional increase in complexity compared to the symmetric setting.
In the revision, we clarified this in section 2.2.


**The Reviewer wrote:**

In the newest version, the Author now claim that calculating both P_in and P_out is efficient. One of the versions of the dual problem we optimize Tr rho W, suggesting an entanglement witness. Table 5 quotes both upper and lower bounds of white noise robustness. Thus I am surprised that the Authors clarified in their response that they certify separability. The above hints me towards believing that the Algorithm is indeed able to provide an entanglement witness. I ask the Authors to confirm or deny. Also, If witnesses are provided, then despite the recent literature was updated, it still lack some references relevant to finding custom-tailored entanglement witnesses. For example, it was Brandao to first notice the relation between an entanglement witness and a separble approximation of a state.

**Our response:**

Sorry for the confusion. Inner polytopes provide an inner approximation of the separable states whereas outer polytopes give rise to an outer approximation. Hence, entanglement detection is indeed possible by using the outer polytope approximation. However, the outer polytope approximation is only practical if one of the systems is a qubit, since then its low-dimensional Bloch sphere allows for an efficient construction of an outer polytope approximation to it. Such a construction is unknown for qudits. Also, the adaption techniques we developed for the inner polytopes cannot be applied to the outer approximation. We added few sentences in the end of Section 2.1. together with references on customized entanglement witnesses to clarify this. On the other hand, the algorithm with adaptive inner polytopes allows for certification of separability also for system of qudits. As this problem has been long considered to be difficult, we mainly concentrate on this aspect in the rest of the manuscript.

**The Reviewer wrote:**

Finally, as a remark, I would point out that the stop criterion in the caption of Figure 5 is not informative, as it ignores the dynamics of the subsequnt iterations. If many rounds of the procedure offer the correction of 10^-4 each, we are still far away. On the other hand, a lot is known about robustness of two-qudit Werner states, and it is difficult to infer how close the Algorithm has got. Only from other data it seems that it is rapidly convergent.

**Our response:**

Thank you for pointing this out. The convergence of the Figure 5 was in fact confirmed by comparing with upper bounds given by the PPT criterion (which is good for random states as we discussed in section 2.2.) We revise the caption to make this clear.

**The Reviewer wrote:**

I am still in favour of publishing the work in SciPost, but basing on the above comments, I think there is still some space to for improvements to make it more useful to the Reader.

**Our response:**

Thank you, your comments have indeed improved the clarity of the manuscript!