Advantage of Quantum Strategies in Random Symmetric XOR Games
Non-local games are known as a simple but useful model which is widely used for displaying nonlocal properties of quantum mechanics. In this paper we concentrate on a simple subset of non-local games: multiplayer XOR games with 1-bit inputs and 1-bit outputs which are symmetric w.r.t. permutations of players.
Starpībkopas, perfektas nelineāras funkcijas un kvantu dizaini
Bloku dizainiem, starpībkopām un perfektām nelineārām funkcijām ir daudz kā kopīga. Bieži vien tās iespējams iegūt vienu no otras un teorēmas par vienu iespējams pielāgot citai. Autors apskata šīs struktūras kontekstā ar savstarpēji nenosliektu bāžu (MUB) problēmu. MUBi ir ortonormētu bāžu kopa, kurās katru divu vektoru no dažādām bāzēm skalārais reizinājums ir vienāds. Darbā ir aprakstīta zināmā MUBu konstrukcija un tiek pētīta funkcija, kas ir tās pamatā.
Template MOLA realizācija
Darbā tiek apskatīta modeļu transformāciju valoda Template MOLA, kas ir piemērota modeļu transformāciju sintēzei valodā MOLA. Template MOLu galvenokārt ir paredzēts pielietot modeļu atbilstību valodu realizācijā, t.i., Template MOLA ir piemērota atbilstību valodu kompilēšanai uz transformāciju valodu MOLA. Template MOLA ir MOLA paplašinājums, kurš ļauj MOLA transformāciju sintēzi definēt ar MOLA elementu konkrēto grafisko sintaksi. Maģistra darbā tiek aprakstīta tās sintakse un semantika un aprakstīta tās implementācija.
Integer Complexity: Experimental and Analytical Results
We consider representing of natural numbers by arithmetical expressions using ones, addition, multiplication and parentheses. The (integer) complexity of n -- denoted by ||n|| -- is defined as the number of ones in the shortest expressions representing n. We arrive here very soon at the problems that are easy to formulate, but (it seems) extremely hard to solve. In this paper we represent our attempts to explore the field by means of experimental mathematics. Having computed the values of ||n|| up to 10^12 we present our observations. One of them (if true) implies that there is an infinite number of Sophie Germain primes, and even that there is an infinite number of Cunningham chains of len…
Structured Frequency Algorithms
B.A. Trakhtenbrot proved that in frequency computability (introduced by G. Rose) it is crucially important whether the frequency exceeds \(\frac{1}{2}\). If it does then only recursive sets are frequency-computable. If the frequency does not exceed \(\frac{1}{2}\) then a continuum of sets is frequency-computable. Similar results for finite automata were proved by E.B. Kinber and H. Austinat et al. We generalize the notion of frequency computability demanding a specific structure for the correct answers. We show that if this structure is described in terms of finite projective planes then even a frequency \(O(\frac{\sqrt{n}}{n})\) ensures recursivity of the computable set. We also show that …
Integer Complexity: Experimental and Analytical Results II
We consider representing of natural numbers by expressions using 1's, addition, multiplication and parentheses. $\left\| n \right\|$ denotes the minimum number of 1's in the expressions representing $n$. The logarithmic complexity $\left\| n \right\|_{\log}$ is defined as $\left\| n \right\|/{\log_3 n}$. The values of $\left\| n \right\|_{\log}$ are located in the segment $[3, 4.755]$, but almost nothing is known with certainty about the structure of this "spectrum" (are the values dense somewhere in the segment etc.). We establish a connection between this problem and another difficult problem: the seemingly "almost random" behaviour of digits in the base 3 representations of the numbers $…
Integer Complexity: Experimental and Analytical Results II
We consider representing natural numbers by expressions using only 1’s, addition, multiplication and parentheses. Let \( \left\| n \right\| \) denote the minimum number of 1’s in the expressions representing \(n\). The logarithmic complexity \( \left\| n \right\| _{\log } \) is defined to be \({ \left\| n \right\| }/{\log _3 n}\). The values of \( \left\| n \right\| _{\log } \) are located in the segment \([3, 4.755]\), but almost nothing is known with certainty about the structure of this “spectrum” (are the values dense somewhere in the segment?, etc.). We establish a connection between this problem and another difficult problem: the seemingly “almost random” behaviour of digits in the ba…
Tree Based Domain-Specific Mapping Languages
Model transformation languages have been mainly used by researchers --- the software engineering industry has not yet widely accepted the model driven software development (MDSD). One of the main reasons is the complexity of metamodelling principles the developers are required to know to actually use model transformations in the way the OMG has stated. We offer the basic principles how to create domain-specific model transformation languages which can be used by developers relying only on familiar modelling concepts. We propose to use simple graphical mappings to specify the correspondence between source and target models which are represented using trees based on the concrete syntax of und…
Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly k or l of the n input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.