检索结果-内蒙古大学图书馆

Teleportation of quantum coherence

学校读者我要写书评

暂无评论

Physical Review A 2023年第4期108卷 042620-042620页

作者： Sohail Arun K. Pati Vijeth Aradhya Indranil Chakrabarty Subhasree Patro Quantum Information and Computation Group Harish-Chandra Research Institute A CI of Homi Bhabha National Institute Chhatnag Road Jhunsi Prayagraj 211019 India Centre for Quantum Science and Technology International Institute of Information Technology Hyderabad Gachibowli Hyderabad-500032 Telangana India Center for Security Theory and Algorithmic Research International Institute of Information Technology Hyderabad Gachibowli Hyderabad-500032 Telangana India Department of Computer Science National University of Singapore 117417 Singapore Computer science and physics department Utrecht University 3584 CS Utrecht The Netherlands Algorithms and complexity group QuSoft Centrum Wiskunde and Informatica 1098XG Amsterdam The Netherlands

We investigate whether it is possible to teleport the coherence of an unknown quantum state from Alice to Bob by communicating a smaller number of classical bits in comparison to what is required for teleporting an unknown quantum state. We find that we cannot achieve perfect teleportation of coherence with one bit of classical communication for an arbitrary qubit. However, we find that if the qubit is partially known, i.e., chosen from the equatorial and polar circles of the Bloch sphere, then teleportation of coherence is possible with the transfer of one cbit of information when we have maximally entangled states as a shared resource. In the case of the resource being a nonmaximally entangled state, we can teleport the coherence with a certain probability of success. In a general teleportation protocol for coherence, we derive a compact formula for the final state at Bob's laboratory in terms of the composition of the completely positive maps corresponding to the shared resource state and a joint positive operator-valued measure (POVM) performed by Alice on her qubit and the unknown state. Using this formula, we show that teleportation of the coherence of a partially known state with real matrix elements is perfectly possible with the help of a maximally entangled state as a resource. Furthermore, we explore the teleportation of coherence with Werner states and show that even when Werner states become separable, the amount of teleported coherence is nonzero, implying the possibility of teleportation of coherence without entanglement.

关键词： Quantum coherence & coherence measures Quantum communication Quantum correlations in quantum information Quantum information theory Quantum protocols

A study of 4−cycle systems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bagheri, B.Gh. Khosravi, M. Mahmoodian, E.S. Rashidi, S. Algorithms and Complexity Group Vienna University of Technology Favoritenstrasse 9-11 Vienna1040 Austria Department of Pure Mathematics Faculty of Mathematics and Computer Shahid Bahonar University of Kerman Kerman Iran Department of Mathematical Sciences Sharif University of Technology P.O. Box 11155-9415 Tehran Iran Department of Applied Mathematics Faculty of Mathematics and Computer Shahid Bahonar University of Kerman Kerman Iran

A 4−cycle system is a partition of the edges of the complete graph Kn into 4−cycles. Let C be a collection of cycles of length 4 whose edges partition the edges of Kn. A set of 4-cycles T1 ⊂ C is called a 4-cycle trade if there exists a set T2 of edge-disjoint 4-cycles on the same vertices, such that (C \ T1) ∪ T2 also is a collection of cycles of length 4 whose edges partition the edges of Kn. We study 4−cycle trades of volume two (double-diamonds) and three and show that the set of all 4-CS(9) is connected with respect of trading with trades of volume 2 (double-diamond) and 3. In addition, we present a full rank matrix whose null-space is containing *** Codes 05B30, 05B05 © 2023, CC BY-NC-ND.

关键词： Diamonds

Interplay of periodic dynamics and noise: Insights from a simple adaptive system

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Folz, Frederic Mehlhorn, Kurt Morigi, Giovanna Theoretische Physik Universität des Saarlandes Saarbrücken66123 Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarland Informatics Campus Saarbrücken66123 Germany

We study the dynamics of a simple adaptive system in the presence of noise and periodic damping. The system is composed by two paths connecting a source and a sink, the dynamics is governed by equations that usually describe food search of the paradigmatic Physarum polycephalum. In this work we assume that the two paths undergo damping whose relative strength is periodically modulated in time and analyse the dynamics in the presence of stochastic forces simulating Gaussian noise. We identify different responses depending on the modulation frequency and on the noise amplitude. At frequencies smaller than the mean dissipation rate, the system tends to switch to the path which minimizes dissipation. Synchronous switching occurs at an optimal noise amplitude which depends on the modulation frequency. This behaviour disappears at larger frequencies, where the dynamics can be described by the time-averaged equations. Here, we find metastable patterns that exhibit the features of noise-induced resonances. © 2021, CC BY-NC-SA.

关键词： Dynamics

complexity of Maker-Breaker Games on Edge Sets of Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Duchêne, Eric Gledel, Valentin Inerney, Fionn Mc Nisse, Nicolas Oijid, Nacim Parreau, Aline Stojaković, Miloš Univ Lyon CNRS INSA Lyon UCBL Centrale Lyon Univ Lyon 2 LIRIS UMR5205 VilleurbanneF-69622 France Université Savoie Mont Blanc CNRS LAMA ChambéryF-73000 France Algorithms and Complexity Group TU Wien Austria Université Côte d’Azur Inria CNRS I3S France Department of Mathematics and Informatics Faculty of Sciences University of Novi Sad Novi Sad Serbia

We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the H-game. Maker wins if she claims the edges of a perfect matching in the first, and a copy of a fixed graph H in the second. We prove that deciding who wins the perfect matching game and the H-game is PSPACE-complete, even for the latter in small-diameter graphs if H is a tree. Toward finding the smallest graph H for which the H-game is PSPACE-complete, we also prove that such an H of order 51 and size 57 exists. We then give several positive results for the H-game. As the H-game is already PSPACE-complete when H is a tree, we mainly consider the case where H belongs to a subclass of trees. In particular, we design two linear-time algorithms, both based on structural characterizations, to decide the winners of the P4-game in general graphs and the K1,-game in trees. Then, we prove that the K1,-game in any graph, and the H-game in trees are both FPT parameterized by the length of the game, notably adding to the short list of games with this property, which is of independent interest. Another natural direction to take is to consider the H-game when H is a cycle. While we were unable to resolve this case, we prove that the related arboricity-k game is polynomial-time solvable. In particular, when k = 2, Maker wins this game if she claims the edges of any *** Codes 91A24, 91A43, 91A46 © 2023, CC BY.

关键词： Trees (mathematics)

Crossing-optimal extension of simple drawings

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Ganian, Robert Hamm, Thekla Klute, Fabian Parada, Irene Vogtenhuber, Birgit Algorithms and Complexity Group TU Wien Austria Utrecht University Netherlands TU Eindhoven Netherlands Graz University of Technology Austria

In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, only recently it has been shown that the extension problem of simple drawings is NP-hard even when the task is to insert a single edge. In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing. © 2020, CC BY.

关键词： Graph theory

Gerrymandering on graphs: Computational complexity and parameterized algorithms

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Gupta, Sushmita Jain, Pallavi Panolan, Fahad Roy, Sanjukta Saurabh, Saket Institute of Mathematical Science HBNI India Indian Institute of Technology Jodhpur India Indian Institute of Technology Hyderabad India Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Science HBNI India University of Bergen Norway

The practice of partitioning a region into areas to favor a particular candidate or a party in an election has been known to exist for the last two centuries. This practice is commonly known as gerrymandering. Recently, the problem has also attracted a lot of attention from complexity theory perspective. In particular, Cohen-Zemach et al. [AAMAS 2018] proposed a graph theoretic version of gerrymandering problem and initiated an algorithmic study around this, which was continued by Ito et al. [AAMAS 2019]. In this paper we continue this line of investigation and resolve an open problem in the literature, as well as move the algorithmic frontier forward by studying this problem in the realm of parameterized complexity. Our contributions in this article are two-fold, conceptual and computational. We first resolve the open question posed by Ito et al. [AAMAS 2019] about the computational complexity of gerrymandering when the input graph is a path. Next, we propose a generalization of the model studied in [AAMAS 2019], where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function wv : C → Z+ for each voter v ∈ V (G) representing the preference of the voter over the candidates, a distinguished candidate p ∈ C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pairwise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts the vertex set needs to be partitioned (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k = 2, m = 2, and G is either a complete bipartite graph (in fact K2,n, a complete bipartite graphs with one side of size 2 and the other of size n) or a complete graph. This hardness result implies that we cannot hope to have an algorithm wit

关键词： Graph theory

Balanced Independent and Dominating Sets on Colored Interval Graphs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Haunert, Jan-Henrik Klute, Fabian Li, Guangping Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Geoinformation Group University of Bonn Bonn Germany Algorithms and Complexity Group TU Wien Vienna Austria

We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely f-Balanced Independent Set (f-BIS) and f-Balanced Dominating Set (f-BDS). Let G = (V, E) be a vertex-colored interval graph with a k-coloring γ : V → {1,..., k} for some k ∈ N. A subset of vertices S ⊆ V is called f-balanced if S contains f vertices from each color class. In the f-BIS and f-BDS problems, the objective is to compute an independent set or a dominating set that is f-balanced. We show that both problems are NP-complete even on proper interval graphs. For the f-BIS problem we design two FPT algorithms, one parameterized by (f, k) for interval graphs and the other parameterized by the vertex cover number for general graphs. Moreover, for the optimization variant of 1-BIS on interval graphs, we show that a simple greedy approach achieves approximation ratio 2. Copyright © 2020, The Authors. All rights reserved.

关键词： Graphic methods

Parameterized study of STEINER TREE on unit disk graphs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Carmi, Paz Kolay, Sudeshna Kolay, Sudeshna Algorithms and Complexity Group Tu Wien Vienna Austria Ben-Gurion University of the Negev Beersheba Israel Indian Institute of Technology Kharagpur

We study the STEINER TREE problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V (G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \ R. The vertices of R are referred to as terminals and the vertices of V (G) \ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the STEINER TREE problem on unit disk graphs can be solved in nO(√t+k)time. We also show that the STEINER TREE problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2O(k)nO(1). In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [16]. We mention that the algorithmic results can be made to work for STEINER TREE on disk graphs with bounded aspect ratio. Finally, we prove that STEINER TREE on disk graphs parameterized by k is W[1]-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： Hardness

Solving the Steiner Tree Problem with few Terminals

学校读者我要写书评

暂无评论

Solving the Steiner Tree Problem with few Terminals

International Conference on Tools for Artificial Intelligence (ICTAI)

作者： Johannes K. Fichte Markus Hecher André Schidler Institute of Artificial Intelligence TU Dresden Dresden Germany University of Potsdam Germany Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (数字)9781728192284

ISBN: (纸本)9781728185361

The Steiner tree problem is a well-known problem in network design, routing, and VLSI design. Given a graph, edge costs, and a set of dedicated vertices (terminals), the Steiner tree problem asks to output a sub-graph that connects all terminals at minimum cost. A state-of-the-art algorithm to solve the Steiner tree problem by means of dynamic programming is the Dijkstra-Steiner algorithm. The algorithm builds a Steiner tree of the entire instance by systematically searching for smaller instances, based on subsets of the terminals, and combining Steiner trees for these smaller instances. The search heavily relies on a guiding heuristic function in order to prune the search space. However, to ensure correctness, this algorithm allows only for limited heuristic functions, namely, those that satisfy a so-called consistency condition. In this paper, we enhance the Dijkstra-Steiner algorithm and establish a revisited algorithm, called DS*. The DS* algorithm allows for arbitrary lower bounds as heuristics relaxing the previous condition on the heuristic function. Notably, we can now use linear programming based lower bounds. Further, we capture new requirements for a heuristic function in a condition, which we call admissibility. We show that admissibility is indeed weaker than consistency and establish correctness of the DS* algorithm when using an admissible heuristic function. We implement DS* and combine it with modern preprocessing, resulting in an open-source solver (DS*Solve). Finally, we compare its performance on standard benchmarks and observe a competitive behavior.

关键词： Steiner trees Heuristic algorithms Very large scale integration Tools Routing Standards Open source software