Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Demo: Co-simulation of UAVs with INTO-CPS and PVSio-web
2018
This demo shows our ongoing work on the co-simulation of co-operative Unmanned Aerial Vehicles (UAVs). The work is based on the INTO-CPS co-simulation engine, which adopts the widely accepted Functional Mockup Interface (FMI) standard for co-simulation, and the PVSioweb prototyping tool, that extends a system simulator based on the PVS logic language with a web-based graphical interface. Simple scenarios of Quadcopters with assigned different tasks, such as rendez-vous and space coverage, are shown. We assumed a linearized dynamic model for Quadcopters formalized in OpenModelica, and a linearized set of equations for the flight control module written in C language. The co-ordination algorit…
Words with the Maximum Number of Abelian Squares
2015
An abelian square is the concatenation of two words that are anagrams of one another. A word of length n can contain \(\varTheta (n^2)\) distinct factors that are abelian squares. We study infinite words such that the number of abelian square factors of length n grows quadratically with n.
On the accurate determination of nonisolated solutions of nonlinear equations
1981
A simple but efficient method to obtain accurate solutions of a system of nonlinear equations with a singular Jacobian at the solution is presented. This is achieved by enlarging the system to a higher dimensional one whose solution in question is isolated. Thus it can be computed e. g. by Newton's method, which is locally at least quadratically convergent and selfcorrecting, so that high accuracy is attainable.
Quantum walk on the line through potential barriers
2015
Quantum walks are well-known for their ballistic dispersion, traveling $\Theta(t)$ away in $t$ steps, which is quadratically faster than a classical random walk's diffusive spreading. In physical implementations of the walk, however, the particle may need to tunnel through a potential barrier to hop, and a naive calculation suggests this could eliminate the ballistic transport. We show by explicit calculation, however, that such a loss does not occur. Rather, the $\Theta(t)$ dispersion is retained, with only the coefficient changing, which additionally gives a way to detect and quantify the hopping errors in experiments.
Quadratically Tight Relations for Randomized Query Complexity
2020
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional…
Applications of Bond-Based 3D-Chiral Quadratic Indices in QSAR Studies Related to Central Chirality Codification
2009
The concept of bond-based quadratic indices is generalized to codify chemical structure information for chiral drugs, making use of a trigonometric 3D-chirality correction factor. In order to evaluate the effectiveness of this novel approach in drug design, we have modeled several well-known data sets. In particularly, Cramer's steroid data set has become a benchmark for the assessment of novel QSAR methods. This data set has been used by several researchers using 3D-QSAR approaches. Therefore, it is selected by us for the shake of comparability. In addition, to evaluate the effectiveness of this novel approach in drug design, we model the angiotensin-converting enzyme inhibitory activity o…
Searching for exceptional points and inspecting non-contractivity of trace distance in (anti-) PT -symmetric systems
2022
Non-Hermitian systems with parity-time ($\mathcal{PT}$) symmetry and anti-$\mathcal{PT}$ symmetry give rise to exceptional points (EPs) with intriguing properties related to, e.g., chiral transport and enhanced sensitivity, due to the coalescence of eigenvectors. In this paper, we propose a powerful and easily computable tool, based on the Hilbert-Schmidt speed (HSS), which does not require the diagonalization of the evolved density matrix, to detect exactly the EPs and hence the critical behavior of the (anti-)$\mathcal{PT}\!-$symmetric systems, especially high-dimensional ones. Our theoretical predictions, made without the need for modification of the Hilbert space, which is performed by …
Distributed construction of quantum fingerprints
2003
Quantum fingerprints are useful quantum encodings introduced by Buhrman, Cleve, Watrous, and de Wolf (Physical Review Letters, Volume 87, Number 16, Article 167902, 2001; quant-ph/0102001) in obtaining an efficient quantum communication protocol. We design a protocol for constructing the fingerprint in a distributed scenario. As an application, this protocol gives rise to a communication protocol more efficient than the best known classical protocol for a communication problem.
Diagrammatic approach to quantum search
2014
We introduce a simple diagrammatic approach for estimating how a randomly walking quantum particle searches on a graph in continuous-time, which involves sketching small weighted graphs with self-loops and considering degenerate perturbation theory's effects on them. Using this method, we give the first example of degenerate perturbation theory solving search on a graph whose evolution occurs in a subspace whose dimension grows with $N$.
Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
2015
In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the "simplex of $K_M$ complete graphs" with all configurations of two marked vertices, two configurations of $M+1$ marked vertices, and two configurations of $2(M+1)$ marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration's value can cause the search to fail. This sensitivity to the jumping rate is an is…