Search results for "Computation Theory & Mathematics"
showing 10 items of 332 documents
Continuous-Variable Sampling from Photon-Added or Photon-Subtracted Squeezed States
2017
We introduce a new family of quantum circuits in Continuous Variables and we show that, relying on the widely accepted conjecture that the polynomial hierarchy of complexity classes does not collapse, their output probability distribution cannot be efficiently simulated by a classical computer. These circuits are composed of input photon-subtracted (or photon-added) squeezed states, passive linear optics evolution, and eight-port homodyne detection. We address the proof of hardness for the exact probability distribution of these quantum circuits by exploiting mappings onto different architectures of sub-universal quantum computers. We obtain both a worst-case and an average-case hardness re…
Matroid optimization problems with monotone monomials in the objective
2022
Abstract In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. We present a complete description of this polytope. Apart from linearization constraints one needs appropriately strengthened rank inequalities. The separation problem for these inequalities reduces to a submodular function minimization problem. These polyhedral results give rise to a new hiera…
Recent results on syntactic groups of prefix codes
2012
International audience; We give a simplified presentation of groups in transformation monoids. We use this presentation to describe two recent results on syntactic groups of prefix codes. The first one uses Sturmian words to build finite bifix codes with a given permutation group as syntactic group. The second one describes a class of prefix codes such that all their syntactic groups are cyclic.
A Generalization of Girod's Bidirectional Decoding Method to Codes with a Finite Deciphering Delay
2012
Girod’s encoding method has been introduced in order to efficiently decode from both directions messages encoded by using finite prefix codes. In the present paper, we generalize this method to finite codes with a finite deciphering delay. In particular, we show that our decoding algorithm can be realized by a deterministic finite transducer. We also investigate some properties of the underlying unlabeled graph.
Quantum Property Testing for Bounded-Degree Graphs
2011
We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph s…
Quantum Security Proofs Using Semi-classical Oracles
2019
We present an improved version of the one-way to hiding (O2H) Theorem by Unruh, J ACM 2015. Our new O2H Theorem gives higher flexibility (arbitrary joint distributions of oracles and inputs, multiple reprogrammed points) as well as tighter bounds (removing square-root factors, taking parallelism into account). The improved O2H Theorem makes use of a new variant of quantum oracles, semi-classical oracles, where queries are partially measured. The new O2H Theorem allows us to get better security bounds in several public-key encryption schemes.
A Constructive Arboricity Approximation Scheme
2020
The arboricity \(\varGamma \) of a graph is the minimum number of forests its edge set can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they approximate the arboricity as a value without computing a corresponding forest partition. This is because they operate on pseudoforest partitions or the dual problem of finding dense subgraphs.
A note on strong protomodularity, actions and quotients
2013
Abstract In order to study the problems of extending an action along a quotient of the acted object and along a quotient of the acting object, we investigate some properties of the fibration of points. In fact, we obtain a characterization of protomodular categories among quasi-pointed regular ones, and, in the semi-abelian case, a characterization of strong protomodular categories. Eventually, we return to the initial questions by stating the results in terms of internal actions.
Irreducible characters of $3'$-degree of finite symmetric, general linear and unitary groups
2018
Abstract Let G be a finite symmetric, general linear, or general unitary group defined over a field of characteristic coprime to 3. We construct a canonical correspondence between irreducible characters of degree coprime to 3 of G and those of N G ( P ) , where P is a Sylow 3-subgroup of G . Since our bijections commute with the action of the absolute Galois group over the rationals, we conclude that fields of values of character correspondents are the same.
Virtual and arrow Temperley–Lieb algebras, Markov traces, and virtual link invariants
2021
Let [Formula: see text] be the algebra of Laurent polynomials in the variable [Formula: see text] and let [Formula: see text] be the algebra of Laurent polynomials in the variable [Formula: see text] and standard polynomials in the variables [Formula: see text] For [Formula: see text] we denote by [Formula: see text] the virtual braid group on [Formula: see text] strands. We define two towers of algebras [Formula: see text] and [Formula: see text] in terms of diagrams. For each [Formula: see text] we determine presentations for both, [Formula: see text] and [Formula: see text]. We determine sequences of homomorphisms [Formula: see text] and [Formula: see text], we determine Markov traces […