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

Generalized measurements on qubits in quantum randomness certification and expansion

Physical Review Applied 2024年第4期22卷 044041页

作者： Piotr Mironowicz Marcus Grünfeld Mohamed Bourennane Department of Physics Department of Algorithms and System Modeling Faculty of Electronics Telecommunications and Informatics

Quantum mechanics has greatly impacted our understanding of microscopic nature. One of the key concepts of this theory is generalized measurements, which have proven useful in various quantum information processing tasks. However, despite their significance, they have not yet been shown empirically to provide an advantage in quantum randomness certification and expansion protocols. This investigation explores scenarios where generalized measurements can yield more than 1 bit of certified randomness with a single-qubit system measurement on untrusted devices and against a quantum adversary. We compare the robustness of several protocols to exhibit the advantage of exploiting generalized measurements. In our analysis of experimental data, we were able to obtain 1.21 bits of min-entropy from a measurement taken on one qubit of an entangled state. We also obtained 1.07 bits of min-entropy from an experiment with quantum state preparation and generalized measurement on a single qubit. We also provide finite data analysis for a protocol using generalized measurements and the Entropy Accumulation Theorem. Our exploration demonstrates the potential of generalized measurements to improve the certification of quantum sources of randomness and enhance the security of quantum cryptographic protocols and other areas of quantum information.

关键词： Entropy Quantum correlations in quantum information Quantum cryptography Quantum information processing Quantum measurements Quantum metrology Quantum protocols Quantum verification

来源：评论

学校读者我要写书评

暂无评论

Application of genetic algorithms in graph searching problem

Application of genetic algorithms in graph searching problem

引用

作者： Wrona, Lukasz Jaworski, Bartosz Department of Algorithms and System Modeling Gdansk University of Technology Gdansk Poland Control Engineering Department Gdansk University of Technology Gdansk Poland

ISBN: (纸本)9788360779026

Graph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in an environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called the (edge) search strategy. Unfortunately calculating both the optimal search strategy and the search number is NP-hard for general graphs. Furthermore, due to the complexity of the pursuit rules, the application of heuristic solutions is not straight forward. In this paper we suggest a method of applying genetic algorithms to solve graph searching problem. The idea is based on LaPaugh's result on graph searching monotonicity and utilizes representation of a search strategy as a permutation of edges.

关键词： Genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient List Cost Coloring of Vertices and/or Edges of Some Sparse Graphs

引用

AIP Conference Proceedings 2007年第1期936卷 241-243页

作者： Krzysztof Giaro Marek Kubale Department of Algorithms and System Modeling Gdańsk University of Technology Poland

We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial‐time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Total Completion Time Minimization for Scheduling with Incompatibility Cliques 31

Total Completion Time Minimization for Scheduling with Incom...

引用

31st International Conference on Automated Planning and Scheduling, ICAPS 2021

作者： Jansen, Klaus Lassota, Alexandra Maack, Marten Pikies, Tytus Department of Computer Science Faculty Of Engineering Kiel University Kiel24098 Germany Department of Algorithms and System Modeling Gdańsk University of Technology Gdańsk80-233 Poland

ISBN: (纸本)9781713832317

This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent years. While the research up to this point has been focused on the makespan objective, we broaden the scope and study the classical total completion time criterion. In the setting without incompatibilities, this objective is well-known to admit polynomial time algorithms even for unrelated machines via matching techniques. We show that the introduction of incompatibility cliques results in a richer, more interesting picture. We prove that scheduling on identical machines remains solvable in polynomial time, while scheduling on unrelated machines becomes APX-hard. Next, we study the problem under the paradigm of fixed-parameter tractable algorithms (FPT). In particular, we consider a problem variant with assignment restrictions for the cliques rather than the jobs. We prove that, despite still being APX-hard, it can be solved in FPT time with respect to the number of cliques. Moreover, we show that the problem on unrelated machines can be solved in FPT time for reasonable parameters, in particular, the parameter combination: maximum processing time, number of job kinds, and number of machines or maximum processing time, number of job kinds, and number of cliques. The latter results are extensions of known results for the case without incompatibilities, and can even be further extended to the case of total weighted completion time. All of the FPT results make use of n-fold Integer Programs that recently received great attention by proving their usefulness for scheduling problems. Copyright © 2021, Association for the Advancement of Artificial Intelligence

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Koala graph coloring library: An open graph coloring library for real-world applications

Koala graph coloring library: An open graph coloring library...

引用

International Conference on Information Technology (ICIT)

作者： Tomasz Dobrowolski Dariusz Dereniowski Lukasz Kuszner Department of Algorithms and System Modeling Gdansk University of Technology Poland

A lot of research has been done in the field of graph coloring, yet there are no publicly released libraries available. This paper introduces such a library. This library is designed to meet several important criteria for industrial applications. Most importantly, it is designed with performance in mind. Several heuristic algorithms are implemented to deal with the NP-completeness. Further optimizations are done at the code level. The library is written in C++ with components that can be used independently. Upon completion, Koala will be released as open source, and free for educational use.

关键词： Libraries Algorithm design and analysis Approximation algorithms Heuristic algorithms Color Complexity theory Approximation methods

来源：评论

学校读者我要写书评

暂无评论

Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines 31

Scheduling with Complete Multipartite Incompatibility Graph ...

引用

31st International Conference on Automated Planning and Scheduling, ICAPS 2021

作者： Pikies, Tytus Turowski, Krzysztof Kubale, Marek Department of Algorithms and System Modeling Gdańsk University of Technology Gdańsk80-233 Poland Theoretical Computer Science Department Jagiellonian University Kraków30-348 Poland

ISBN: (纸本)9781713832317

In this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. We provide several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality: Cmax (makespan) and P Cj (total completion time). We consider a variety of machine types in our paper: identical, uniform, and unrelated. Our results consist of delimitation of the easy (polynomial) and NP-hard problems within these constraints. We also provide algorithms, either polynomial exact algorithms for the easier problems, or algorithms with a guaranteed constant worst-case approximation ratio. In particular, we fill the gap on research for the problem of finding a schedule with the smallest P Cj on uniform machines. We address this problem by developing a linear programming relaxation technique with an appropriate rounding, which to our knowledge is a novelty for this criterion in the considered setting. Copyright © 2021, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Energy Optimisation in Resilient Self-Stabilizing Processes

Energy Optimisation in Resilient Self-Stabilizing Processes

引用

International Conference on Parallel Computing in Electrical Engineering (PARLEC)

作者： A. Kosowski L. Kuszner Department of Algorithms and System Modeling Gdańsk University of Technology Poland

When performing an algorithm in the self-stabilizing model, a distributed system must achieve a desirable global state regardless of the initial state, whereas each node has only local information about the system. Depending on adopted assumptions concerning the model of simultaneous execution and scheduler fairness, some algorithms may differ in stabilization time or possibly not stabilize at all. Surprisingly, we show that the class of polynomially-solvable self-stabilizing problems is invariant with respect to the assumption of weak scheduler fairness. Furthermore, for systems with a single distinguished vertex we prove a much stronger equivalence, stating that synchronisation, the existence of a central scheduler and its fairness have no influence on polynomial stabilization time

关键词： Peer to peer computing Polynomials Scheduling algorithm Concurrent computing Processor scheduling modeling Electronic mail Distributed algorithms Communication channels Costs

来源：评论

学校读者我要写书评

暂无评论

Comparing arbitrary unrooted phylogenetic trees using generalized matching split distance

Comparing arbitrary unrooted phylogenetic trees using genera...

引用

International Conference on Information Technology (ICIT)

作者： Damian Bogdanowicz Krzysztof Giaro Department of Algorithms and System Modeling Gdansk University of Technology Gdansk Poland

In the paper, we describe a method for comparing arbitrary, not necessary fully resolved, unrooted phylogenetic trees. The proposed method is based on finding a minimum weight matching in bipartite graphs and can be regarded as a generalization of well-known Robinson-Foulds distance. We present some properties and advantages of the new distance. We also investigate some properties of the presented distance in a common biological problem of finding a single phylogenetic tree (consensus tree) that reliably represents a set of various phylogenetic trees. Finding a consensus tree (or a small set of such trees) is an important phase in the phylogenetic research, especially if a method that is chosen for the construction process returns a set of trees (for example the very popular Bayesian approach).

关键词： Organisms

来源：评论

学校读者我要写书评

暂无评论

Zero-visibility cops and robber game on a graph

Zero-visibility cops and robber game on a graph

引用

7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013

作者： Dereniowski, Dariusz Dyer, Danny Tifenbach, Ryan M. Yang, Boting Department of Algorithms and System Modeling Gdańsk University of Technology Gdańsk Poland Department of Mathematics and Statistics Memorial University of Newfoundland St. John's Canada Department of Computer Science University of Regina Regina Canada

ISBN: (纸本)9783642387555

We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops & robber game in one way: the robber is invisible. We show that this model is not monotonic. We also provide bounds on both the zero-visibility copnumber and monotonic zero-visibility copnumber in terms of the pathwidth. © 2013 Springer-Verlag Berlin Heidelberg.

关键词： Visibility

来源：评论

学校读者我要写书评

暂无评论

Inferring perfect phylogenies with restrictions on character state transitions

Inferring perfect phylogenies with restrictions on character...

引用

International Conference on Information Technology (ICIT)

作者： Jakub Truszkowski Krzysztof Giaro Gdansk University of Technology Poland Department of Algorithms and System Modeling Gdansk University of Technology Poland

One of the important problems in evolutionary biology is inferring phylogenetic trees for sets of related species. We introduce a new model for inferring phylogenies which is a generalization of the widely studied perfect phylogeny model. The perfect phylogeny model assumes that a feature shared by a set of species cannot have evolved independently in any two of the species in the set, i.e. the species with this feature form a subtree in the correct phylogenetic tree. We briefly review earlier similar results on this subject and describe the difference between our model and the ones previously investigated. It turns out that the problem of finding a perfect phylogeny with restrictions is NP-complete even if the number of characters is 2. This contrasts with the complexity of finding unrestricted perfect phylogenies. On the other hand, the new model shows similar properties to the classical perfect phylogeny model in case where the number of cycles in each state transition graph is bounded by a small constant.

关键词： Phylogeny Polynomials Biological system modeling History Programming Complexity theory Teeth

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：