Complex photonic integrated circuits (PIC) may have strongly non-planar topologies that require waveguide crossings (WGX) when realized in single-layer integration platforms. The number of WGX increases rapidly with t...
详细信息
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 un...
详细信息
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.
Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to data inaccuracies or modeling errors, in practical applications one often fa...
详细信息
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\)-set of a graph \(G\) i...
详细信息
We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets \(\sigma,\rho\) of non-negative integers, a \((\sigma,\rho)\)-set of a graph \(G\) is a set \(S\) of vertices such that \(|N(u)\cap S|\in\sigma\) for every \(u\in S\), and \(|N(v)\cap S|\in\rho\) for every \(v\not\in S\). The problem of finding a \((\sigma,\rho)\)-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many *** all pairs of finite or cofinite sets \((\sigma,\rho)\), we determine (under standard complexity assumptions) the best possible value \(c_{\sigma,\rho}\) such that there is an algorithm that counts \((\sigma,\rho)\)-sets in time \(c_{\sigma,\rho}^{\rm{tw}} \cdot n^{O(1)}\) (if a tree decomposition of width \(\rm{tw}\) is given in the input). Let \(s_{\rm{top}}\) denote the largest element of \(\sigma\) if \(\sigma\) is finite, or the largest missing integer \(+1\) if \(\sigma\) is cofinite; \(r_{\rm{top}}\) is defined analogously for \(\rho\). Surprisingly, \(c_{\sigma,\rho}\) is often significantly smaller than the natural bound \(s_{\rm{top}}+r_{\rm{top}}+2\) achieved by existing algorithms [van Rooij, 2020]. Toward defining \(c_{\sigma,\rho}\), we say that \((\sigma,\rho)\) is m-structured if there is a pair \((\alpha,\beta)\) such that every integer in \(\sigma\) equals \(\alpha\) mod m, and every integer in \(\rho\) equals \(\beta\) mod m. Then, setting—\(c_{\sigma,\rho}=s_{\rm{top}}+r_{\rm{top}}+2\) if \((\sigma,\rho)\) is not m-structured for any \(\rm{m}\geq 2\),—\(c_{\sigma,\rho}=\max\{s_{\rm{top}},r_{\rm{top}}\}+2\) if \((\sigma,\rho)\) is 2-structured, but not \(\rm{m}\)-structured for any \(\rm{m}\geq 3\), and \(s_{\rm{top}}=r_{\rm{top}}\) is even, and—\(c_{\sigma,\rho}=\max\{s_{\rm{top}},r_{\rm{top}}\}+1\), otherwise,we provide algorithms counting \((\sigma,\rho)\)-sets in time \(c_{\sigma,\rho}^{\rm{tw}}\cdot n^{O(1)}\). For e
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph ...
详细信息
For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u)∩S| ∈ σ for every u ∈ S, and |N(v)∩S| ∈ ρ for every \(v\not\in S\). The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set, Dominating Set, Independent Dominating Set, and many *** an accompanying paper, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time \((c_{\sigma,\rho })^{\sf tw}\cdot n^{{\rm O}(1)}\) (if a tree decomposition of width \({\sf tw}\) is given in the input). Here, cσ, ρ is a constant with an intricate dependency on σ and ρ. Despite this intricacy, we show that the algorithms in the accompanying paper are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any ε > 0, a \((c_{\sigma,\rho }-\varepsilon)^{\sf tw}\cdot n^{{\rm O}(1)}\)-algorithm counting the number of (σ, ρ)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well.
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, suc...
详细信息
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms that achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width *** by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels,•Independent Set and Dominating Set can be solved in time \(2^{\mathcal {O}(dk)}\cdot n^{\mathcal {O}(1)}\) using \(\mathcal {O}(dk\log n)\) space;•Max Cut can be solved in time \(n^{\mathcal {O}(dk)}\) using \(\mathcal {O}(dk\log n)\) *** also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.
作者：
STEMMER, WPCPalo Alto Institute of Molecular Medicine 2462 Wyandotte Street Mountain View
CA 94043 (e-mail:youvan@***)REFERENCES Stemmer W.P.C. 1995. Searching sequence space. Bio/Technology 13: 549-553.|ISI|ChemPort|Stemmer W.P.C. 1994. DNA shuffling by random fragmentation and reassembly: In vitro recombination for molecular evolution. Proc. Natl. Acad. Sci. USA 91: 10747-10751.|Article|PubMed|ChemPort|Stemmer W.P.C. 1994. Rapid evolution of a protein in vitro by DNA shuffling. Nature 370: 389-391.|Article|PubMed|ISI|ChemPort|Arkin A.P. and Youvan D.C. 1992. An algorithm for protein engineering: Simulation of recursive ensemble mutagenesis. Proc. Natl. Acad. Sci USA 89: 7811-7815.|PubMed|ChemPort|Youvan D.C. Arkin A.P. and Yang N.M. 1992. Recursive ensemble mutagenesis: A combinatorial optimization technique for protein engineering. In Parallel Problem Solving from Nature. B. Manderick. ed. Elsevier Publishing Co. New York pp.401-410.Reidhaar-Olson J.F. Bowie J.U. Breyer R.M. Hu J.C. Knight K.L. Lim W.A. Mossing M.C. Parsell D.A. Shoemaker K.R. and Sauer R.T. 1991. Random mutagenesis of protein sequences using oligonucleotide cassettes. Meth. Enzymol. 208: 564-587.|PubMed|ChemPort|Oliphant A.R. Nussbaum A.L. and Struhl K. 1986. Cloning of random sequence oligonucleotides. Gene 44: 177-183.|Article|PubMed|ISI|ChemPort|Fuellen G. and Youvan D.C. 1994. Genetic algorithms and recursive ensemble mutagenesis in protein engineering. Complexity International http://life.anu.edu.au/ci/voll/fuellen/REM.html.Goldman E.R. and Youvan D.C. 1992. An algorithmically optimized combinatorial library screened by digital imaging spectroscopy. Bio/Technology 10: 1557-1561.|Article|PubMed|ISI|ChemPort|Youvan D.C. 1994. Imaging sequence space. Nature 369: 79-80.|Article|PubMed|ISI|ChemPort|Delagrave S.Goldman E.R. and Youvan D.C. 1993. Recursive ensemble mutagenesis. Protein Engineering 6: 327-331.|PubMed|ISI|ChemPort|Youvan D.C. Goldman E. Delagrave S. and Yang M.M. 1994. Digit
Using recombination to search more efficiently and thoroughly instead of making bigger combinatorial libraries
Using recombination to search more efficiently and thoroughly instead of making bigger combinatorial libraries
暂无评论