Editing (Symmetric) Private Information Retrieval (section)

===Optimal communication complexity of the (Q)(S)PIR problem===
Below are summarised known bounds for the communication complexity of information-theoretically secure (S)PIR protocols in the classical and quantum settings, for a quantum or classical database.

*<math>f</math> : number of database elements (quantum states in the 'fully' quantum setting)
*<math>m</math> : total size of database elements (i.e., the sum of the sizes, in bits, of each database element)
*<math>d</math> : dimension of the quantum states stored in the quantum database (<math>d=2</math> if they are qubits)
*<math>k</math> : number of servers (or equivalently of replicated databases)

====Single-database case====
{| class="wikitable plainrowheaders"
 ! scope="col" | Problem
 ! scope="col" | Additional assumptions
 ! scope="col" | Optimal communication complexity
 ! scope="col" | Reference
 |-
 ! scope="row" | Classical PIR
 |  || <math>\Theta(m)</math> || [http://www.wisdom.weizmann.ac.il/~oded/PSX/pir2.pdf Chor et al (1995)]
 |-
 ! scope="row" | Classical SPIR
 |  || NA (impossible) ||
 |-
 ! scope="row" rowspan="4" | Quantum PIR (Classical database)
 | Specious server || <math>\Theta(m)</math> || [https://arxiv.org/pdf/1304.5490.pdf Baumeler and Broadbent (2015)]
 |-
 | Specious server & prior entanglement || <math>\Theta(m)</math> || [https://arxiv.org/pdf/1902.09768.pdf Aharonov et al (2019)]
 |-
 | Honest server || <math>O(poly \log (m))</math> || [https://repository.ubn.ru.nl/bitstream/handle/2066/155747/155747.pdf Kerenidis et al (2016)]
 |-
 | Honest server & prior entanglement || <math>O(\log (m))</math> || [https://repository.ubn.ru.nl/bitstream/handle/2066/155747/155747.pdf Kerenidis et al (2016)]
 |-
 ! scope="row" rowspan="2" | Quantum SPIR (Classical database)
 |  || NA (impossible) || [https://arxiv.org/pdf/quant-ph/9611031.pdf Lo (1997)]
 |-
 | The server will not cheat if there is a non-zero probability of being caught cheating & imperfect data privacy (the user should get at most two database items) || <math>O(\log (m))</math> || [https://arxiv.org/pdf/0708.2992.pdf Giovannetti et al (2008)]
 |-
 ! scope="row" rowspan="3" | Quantum PIR (Quantum database)
 | Honest server & blind setting || <math>\Theta(m)</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
 |-
 | Honest server & visible setting || <math>\Theta(m)</math> (for one-round) || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
 |-
 | Honest server & prior entanglement || <math>O(\log (m))</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
 |-
 ! scope="row" | Quantum SPIR (Quantum database)
 |  ||  || 
|}

====Multi-database case====
{| class="wikitable plainrowheaders"
 ! scope="col" | Problem
 ! scope="col" | Additional assumptions
 ! scope="col" | Optimal communication complexity
 ! scope="col" | Reference
 |-
 ! scope="row" | Classical PIR
 |  ||  || 
 |-
 ! scope="row" | Classical SPIR
 | Servers do not communicate with each other & secure classical channels || <math>O(m^{\frac{1}{2k-1}}) \text{ bits}</math> || [https://dl.acm.org/doi/abs/10.1145/276698.276723 Gertner et al (2000)]
 |-
 ! scope="row" | Quantum PIR (Classical database)
 |  ||  || 
 |-
 ! scope="row" rowspan="2" | Quantum SPIR (Classical database)
 | Servers do not communicate with each other || <math>O(m^{\frac{1}{2k-1}}) \text{ bits}+ \text{ comm. complexity of QKD}</math> || [https://www.mdpi.com/1099-4300/23/1/54/htm Kon and Lim (2021)]
 |-
 | Servers do not communicate with each other & honest user & prior entanglement || <math>m^{O(\log \log (k)/k \log(k))}</math> || [https://arxiv.org/pdf/quant-ph/0307076.pdf Kerenidis and de Wolf (2004)]
 |-
 ! scope="row" | Quantum PIR (Quantum database)
 |  ||  || 
 |-
 ! scope="row" rowspan="3" | Quantum SPIR (Quantum database)
 | Servers do not communicate with each other & prior entanglement & visible setting & database contains pure qubit states || <math>O(f) \text{ bits} + O(1) \text{ qubits} + O(1) \text{ ebits}</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
 |-
 | Servers do not communicate with each other & prior entanglement & visible setting & database contains pure qudit states || <math>O(f) \text{ bits} + O(d^d \log (d)) \text{ qubits} + O(d^d \log (d)) \text{ ebits}</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
 |-
 | Servers do not communicate with each other & prior entanglement & visible setting & database contains commutative unitaries || <math>O(f) \text{ bits} + O(\log (d)) \text{ qubits} + O(\log (d)) \text{ ebits}</math> || [https://arxiv.org/pdf/2101.09041.pdf Song and Hayashi (2021)]
|}