An official website of the United States government
We consider the problem of multipath entanglement distribution to a pair of nodes in a quantum network consisting of devices with nondeterministic entanglement swapping capabilities. Multipath entanglement distribution enables a network to establish end-to-end entangled links across any number of available paths with preestablished link-level entanglement. Probabilistic entanglement swapping, on the other hand, limits the amount of entanglement that is shared between the nodes; this is especially the case when, due to practical constraints, swaps must be performed in temporal proximity to each other. Limiting our focus to the case where only bipartite entanglement is generated across the network, we cast the problem as an instance of generalized flow maximization between two quantum end nodes wishing to communicate. We propose a mixed-integer quadratically constrained program (MIQCP) to solve this flow problem for networks with arbitrary topology. We then compute the overall network capacity, defined as the maximum number of Einstein–Podolsky–Rosen (EPR) states distributed to users per time unit, by solving the flow problem for all possible network states generated by probabilistic entangled link presence and absence, and subsequently by averaging over all network state capacities. The MIQCP can also be applied to networks with multiplexed links. While our approach for computing the overall network capacity has the undesirable property that the total number of states grows exponentially with link multiplexing capability, it nevertheless yields an exact solution that serves as an upper bound comparison basis for the throughput performance of more easily implementable yet nonoptimal entanglement routing algorithms.
more »
« less
Relaxed Schroedinger bridges and robust network routing
We seek network routing towards a desired final distribution that can mediate possible random link failures. In other words, we seek a routing plan that utilizes alternative routes so as to be relatively robust to link failures. To this end, we provide a mathematical formulation of a relaxed transport problem where the final distribution only needs to be close to the desired one. The problem is cast as a maximum entropy problem for probability distributions on paths with an added terminal cost. The entropic regularizing penalty aims at distributing the choice of paths amongst possible alternatives. We prove that the unique solution may be obtained by solving a generalized Schro ̈dinger system of equations. An iterative algorithm to com- pute the solution is provided. Each iteration of the algorithm contracts the distance (in the Hilbert metric) to the optimal solution by more than 1/2, leading to extremely fast convergence.
more »
« less
- PAR ID:
- 10114201
- Date Published:
- Journal Name:
- IEEE Transactions on Control of Network Systems
- ISSN:
- 2372-2533
- Page Range / eLocation ID:
- 1 to 1
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Railroads are maintained routinely by using various types of rail‐bound machines so as to achieve the longest possible rail life and reduce the safety risks associated with unanticipated rail failures. The rail maintenance routing and scheduling problem (RMRSP), which involves routing of multiple maintenance vehicles and scheduling of hundreds of maintenance jobs over a large‐scale network, is usually subject to various types of complex constraints and extremely difficult to solve. This article proposes a vehicle routing problem with time windows (VRPTW) formulation for RMRSP and develops a customized stepwise algorithm to solve the problem. A series of numerical experiments are conducted to demonstrate that the proposed algorithm works very effectively, significantly outperforming the state‐of‐the‐art commercial solver. The results of two real‐world instances from a Class I railroad company show that the proposed model and solution algorithm enable the expensive maintenance vehicles to achieve a higher level of utilization, that is, spending more time on working and less time on deadhead traveling.more » « less
-
Oblivious routing of network traffic uses predetermined paths that do not change with changing traffic patterns. It has the benefit of using a fixed network configuration while robustly handling a range of varying and unpredictable traffic. Theoretical advances have shown that the benefits of oblivious routing are achievable without compromising much capacity efficiency. For oblivious routing, we only assume knowledge of the ingress/egress capacities of the edge nodes through which traffic enters or leaves the network. All traffic patterns possible subject to the ingress/egress capacity constraints (also known as the hose constraints) are permissible and are to be handled using oblivious routing. We use the widely deployed segment routing method for route control. Furthermore, for ease of deployment and to not deviate too much from conventional shortest path routing, we restrict paths to be 2-segment paths (the composition of two shortest path routed segments). We solve the 2-segment oblivious routing problem for all permissible traffic matrices (which can be infinitely-many).We develop a new adversarial and machine-learning driven approach that uses an iterative gradient descent method to solve the routing problem with worst-case performance guarantees. Additionally, the parallelism involved in descent methods allows this method to scale well with the network size making it amenable for use in practice.more » « less
-
We study a general stochastic ranking problem in which an algorithm needs to adaptively select a sequence of elements so as to “cover” a random scenario (drawn from a known distribution) at minimum expected cost. The coverage of each scenario is captured by an individual submodular function, in which the scenario is said to be covered when its function value goes above a given threshold. We obtain a logarithmic factor approximation algorithm for this adaptive ranking problem, which is the best possible (unless P = NP). This problem unifies and generalizes many previously studied problems with applications in search ranking and active learning. The approximation ratio of our algorithm either matches or improves the best result known in each of these special cases. Furthermore, we extend our results to an adaptive vehicle-routing problem, in which costs are determined by an underlying metric. This routing problem is a significant generalization of the previously studied adaptive traveling salesman and traveling repairman problems. Our approximation ratio nearly matches the best bound known for these special cases. Finally, we present experimental results for some applications of adaptive ranking.more » « less
-
Statistical and Computational Complexities of BFGS Quasi-Newton Method for Generalized Linear ModelsThe gradient descent (GD) method has been used widely to solve parameter estimation in generalized linear models (GLMs), a generalization of linear models when the link function can be non-linear. In GLMs with a polynomial link function, it has been shown that in the high signal-to-noise ratio (SNR) regime, due to the problem's strong convexity and smoothness, GD converges linearly and reaches the final desired accuracy in a logarithmic number of iterations. In contrast, in the low SNR setting, where the problem becomes locally convex, GD converges at a slower rate and requires a polynomial number of iterations to reach the desired accuracy. Even though Newton's method can be used to resolve the flat curvature of the loss functions in the low SNR case, its computational cost is prohibitive in high-dimensional settings as it is $$\mathcal{O}(d^3)$$, where $$d$$ the is the problem dimension. To address the shortcomings of GD and Newton's method, we propose the use of the BFGS quasi-Newton method to solve parameter estimation of the GLMs, which has a per iteration cost of $$\mathcal{O}(d^2)$$. When the SNR is low, for GLMs with a polynomial link function of degree $$p$$, we demonstrate that the iterates of BFGS converge linearly to the optimal solution of the population least-square loss function, and the contraction coefficient of the BFGS algorithm is comparable to that of Newton's method. Moreover, the contraction factor of the linear rate is independent of problem parameters and only depends on the degree of the link function $$p$$. Also, for the empirical loss with $$n$$ samples, we prove that in the low SNR setting of GLMs with a polynomial link function of degree $$p$$, the iterates of BFGS reach a final statistical radius of $$\mathcal{O}((d/n)^{\frac{1}{2p+2}})$$ after at most $$\log(n/d)$$ iterations. This complexity is significantly less than the number required for GD, which scales polynomially with $(n/d)$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1109/TCNS.2019.2935623
