Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate ...is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer $${\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^T$$ J n CS ⊂ J n T , where $${\mathcal {J}}_n^{CS}$$ J n CS and $${\mathcal {J}}_n^T$$ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying $${\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}$$ J n Tof = J n CS , where $${\mathcal {J}}_n^{Tof}$$ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.
We give robust recovery results for synchronization on the rotation group, Formula omitted. In particular, we consider an adversarial corruption setting, where a limited percentage of the ...observations are arbitrarily corrupted. We develop a novel algorithm that exploits Tukey depth in the tangent space of Formula omitted. This algorithm, called Depth Descent Synchronization, exactly recovers the underlying rotations up to an outlier percentage of Formula omitted, which corresponds to 1/4 for Formula omitted and 1/8 for Formula omitted. In the case of Formula omitted, we demonstrate that a variant of this algorithm converges linearly to the ground truth rotations. We implement this algorithm for the case of Formula omitted and demonstrate that it performs competitively on baseline synthetic data.
Predictive Algorithms for a Crisis Sotillo, Claudia L; Franco, Idalid; Arriaga, Alexander F
Critical care medicine,
07/2022, Letnik:
50, Številka:
7
Journal Article
In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) Formula omitted, where Formula omitted is a Formula omitted matrix ...over a field Formula omitted and Formula omitted is an indeterminate for Formula omitted and Formula omitted. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719-734, 1995). Recent interests in this problem lie in the connection with non-commutative Edmonds' problem by Ivanyos et al. (Comput Complex 27:561-593, 2018) and Garg et al. (Found. Comput. Math. 20:223-290, 2020), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial Formula omitted-time algorithm for computing the symbolic rank of a Formula omitted-type generic partitioned matrix of size Formula omitted. Our algorithm is inspired by the Wong sequence algorithm by Ivanyos et al. for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field Formula omitted.
We consider the restricted inverse optimal value problem on shortest path under weighted Formula omitted norm on trees (RIOVSPT Formula omitted). It aims at adjusting some edge weights to minimize ...the total cost under weighted Formula omitted norm on the premise that the length of the shortest root-leaf path of the tree is lower-bounded by a given value D, which is just the restriction on the length of a given root-leaf path Formula omitted. If we ignore the restriction on the path Formula omitted, then we obtain the minimum cost shortest path interdiction problem on trees (MCSPIT Formula omitted). We analyze some properties of the problem (RIOVSPT Formula omitted) and explore the relationship of the optimal solutions between (MCSPIT Formula omitted) and (RIOVSPT Formula omitted). We first take the optimal solution of the problem (MCSPIT Formula omitted) as an initial infeasible solution of problem (RIOVSPT Formula omitted). Then we consider a slack problem Formula omitted, where the length of the path Formula omitted is greater than D. We obtain its feasible solutions gradually approaching to an optimal solution of the problem (RIOVSPT Formula omitted) by solving a series of subproblems Formula omitted. It aims at determining the only weight-decreasing edge on the path Formula omitted with the minimum cost so that the length of the shortest root-leaf path is no less than D. The subproblem can be solved by searching for a minimum cost cut in O(n) time. The iterations continue until the length of the path Formula omitted equals D. Consequently, the time complexity of the algorithm is Formula omitted and we present some numerical experiments to show the efficiency of the algorithm. Additionally, we devise a linear time algorithm for the problem (RIOVSPT Formula omitted) under unit Formula omitted norm.
In view of some shortcomings of traditional vertex 1-center (V1C), we introduce a vertex quickest 1-center (VQ1C) problem on a tree, which aims to find a vertex such that the maximum transmission ...time to transmit Formula omitted units data is minimum. We first characterize some intrinsic properties of VQ1C and design a binary search algorithm in Formula omitted time based on the relationship between V1C and VQ1C, where n is the number of vertices. Furthermore, we investigate the inverse VQ1C problem under weighted Formula omitted norm, in which we modify a given capacity vector in an optimal way such that a prespecified vertex becomes the vertex quickest 1-center. We introduce a concept of an effective modification and provide some optimality conditions for the problem. Then we propose an Formula omitted time algorithm. Finally, we show some numerical experiments to verify the efficiency of the algorithms.
The max+sum spanning tree (MSST) problem is to determine a spanning tree T whose combined weight Formula omitted is minimum for a given edge-weighted undirected network G(V, E, c, w). This problem ...can be solved within Formula omitted time, where m and n are the numbers of edges and nodes, respectively. An inverse MSST problem (IMSST) aims to determine a new weight vector Formula omitted so that a given Formula omitted becomes an optimal MSST of the new network Formula omitted. The IMSST problem under weighted Formula omitted norm is to minimize the modification cost Formula omitted, where q(e) is a cost modifying the weight w(e). We first provide some optimality conditions of the problem. Then we propose a strongly polynomial time algorithm in Formula omitted time based on a binary search and a greedy method. There are O(m) iterations and we solve an MSST problem under a new weight in each iteration. Finally, we perform some numerical experiments to show the efficiency of the algorithm.
PDF
