Recently emerged as a disruptive networking paradigm, quantum networks rely on the mysterious quantum entanglement to teleport qubits without physically transferring quantum particles. However, the state of quantum systems is extremely fragile due to environment noise. A promising technique to combat against quantum decoherence is entanglement purification. To fully exploit its benefit, two fundamental research questions need to be answered: (1) given an entanglement path, what is the optimal entanglement purification schedule? (2) how to compute min-cost end-to-end entanglement paths subject to fidelity constraint? In this paper, we give algorithmic solutions to both questions. For the first question, we develop an optimal entanglement purification scheduling algorithm for the singlehop case and analyze the PURIFY-AND-SWAP strategy in the multi-hop case by establishing the closed-form condition for its optimality. For the second question, we design a polynomialtime algorithm constructing an$\epsilon$-optimal fidelity-constrained path. The effectiveness of our algorithms are also numerically demonstrated by extensive simulations.

Entanglement purification is a fundamental operation to combat against quantum decoherence and improve the fidelity of the entanglement. When multiple rounds of entanglement purification are performed, the fidelity of the final entanglement depends on the way how we schedule entanglement purification operations at each round. In this paper, we formulate and analyze the optimal entanglement purification scheduling problem arising from this context. Our main results include an optimal link-level purification scheduling algorithm and a joint entanglement purification scheduling and routing algorithm to establish fidelity-guaranteed end-to-end entanglements with quasi-optimal throughput in quantum networks. Our algorithmic framework developed in this paper can serve as functional building blocks for entanglement provisioning to support high-fidelity quantum information transfer by exploiting the limited quantum resources in a cost-effective way in order to fully realize the unrivalled capabilities offered by quantum networks.

We revisit the problem of missing tag identification in RFID networks by making three contributions. Firstly, we quantitatively compare and gauge the existing propositions spanning over a decade on missing tag identification. We show that the expected execution time of the best solution in the literature is$\Theta \left(N+\frac{(1-\alpha)^2(1-\delta)^2}{ \epsilon^2}\right)$, where$\delta$and$\epsilon$are parameters quantifying the required identification accuracy,$N$denotes the number of tags in the system, among which$\alpha N$tags are missing. Secondly, we analytically establish the expected execution time lower-bound foranymissing tag identification algorithm as$\Theta\left(\frac{N}{\log N}+\frac{(1-\delta)^2(1-\alpha)^2}{\epsilon^2 \log \frac{(1-\delta)(1-\alpha)}{\epsilon}}\right)$, thus setting the theoretical performance limit. Thirdly, we develop two novel missing tag identification algorithms with the expected execution time of$\Theta \left(\frac{\log\log N}{\log N}N+\frac{(1-\alpha)^2(1-\delta)^2}{ \epsilon^2}\right)$, reducing the time overhead by a factor of up to$\log N$over the best algorithm in the literature. The key technicality in our first algorithm is a novel data structure termed as collision-partition tree (CPT), built on a subset of bits in tag pseudo-IDs, leading to a more balanced tree structure and reducing the time complexity in parsing the entire tree. To further improve time efficiency, our second algorithm integrates multiple CPTs to form a collision-partition forest (CPF), reducing both the number of slots and the quantity of information broadcasting.