  The no-go theorem regarding unconditionally secure Quantum Bit Commitment
protocols is a relevant result in quantum cryptography. Such result has been
used to prove the impossibility of unconditional security for other protocols,
such as Quantum Oblivious Transfer or One-Sided Two Party Computation. In this
paper, we formally define two non-deterministic versions of Quantum Private
Queries, a protocol addressing the Symmetric-Private Information Retrieval
problem. We show that the strongest variant of such scheme is formally
equivalent to Quantum Bit Commitment, Quantum Oblivious Transfer and One-Sided
Two Party Computation protocols. This equivalence serves as conclusive evidence
of the impracticality of achieving unconditionally secure Strong Probabilistic
Quantum Private Queries.
