All Questions

2 views

How are new probabilities computed when simulating measurement on a set of qubits?

Suppose I have a set of 3 qubits and I have calculated the probabilities for their distribution: |000> -> a |001> -> b |010> -> c |011> -> d |100> -> e |101> -> f |110> -> g |111> -> h With it ...
$\newcommand{\convh}{\text{convh}}$Suppose that two convex polytopes $Q,S\in \mathbb{R}^n$ are given, where $Q= \convh(\bigcup_{a=1}^t Q_a)$ and $S= \convh(\bigcup_{b=1}^r S_b)$ where the $Q_a$'s and $... 0answers 31 views Testing for satisfiability of a system of linear equations over GF(2) Consider a system linear equations in$x$,$Ax =b$, where A is an$n\times n$matrix, and$b$is a column vector, and all operations are over$GF(2)$. Is it easier to check satisfiability of the ... 1answer 59 views How do you get the Calculus of Constructions from the other points in the Lambda Cube? The CoC is said to be the culmination of all three dimensions of the Lambda Cube. This isn't apparent to me at all. I think I understand the individual dimensions, and the combination of any two seems ... 2answers 48 views Known and described subclasses of Context-Free Grammars class I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known: deterministic/non-deterministic ... 0answers 29 views a linear sort program? [on hold] I want to know the goal of the following question taken from my text book: Suppose its known that each of the items in$a\space[1.\space.N]$has one of two distinct values. Give a sorting method ... 0answers 76 views what if P = NP intersection CO-NP [on hold] Can someone tells what if p equals np intersection co-np. I am sorry i cannot write the qeustion in popper notations cause i dont know how to do that thanks 0answers 28 views What are the connections between P-complete and L-complete [on hold] I have limited knowledge about complexity theory. From what I learned, DFA membership testing is an L-complete problem. However, I am not quite sure what it implies. For example, is it also a P-... 1answer 71 views “Impredicative” in type theory I am confused. I think I've read two usages of the word "impredicative" in type theory: When people talk about the "impredicative" version of Martin-Löf's type theory, which they say it is ... 0answers 42 views On the size of residue classes Let$n \in \mathbb{N}$be a odd number. Let$S \subseteq \{1,3,5,7,...,n-2,n\}$and$|S|$is even number. Let$R_i^k=\{a \mid a \in S \text{ } \&\text{ } a\equiv i \text{ }(mod \text{ } k)\}$... 0answers 127 views MLTT vs. [weak] MSOL I've noted that both Martin-Lof type theory and [Weak] Monadic Second-Order logic (eg over trees) enjoy the ability to express basically any finite computer program, in a decidable manner. I was ... 1answer 137 views Structured set of binary words Definitions: Let$n\in \mathbb N$be an integer, and consider the field$\mathbb K=GF(2^n)$. For$c\in \mathbb N$, let$S_c$be a set of$n$elements from$\mathbb K$such that: Every element$e$... 0answers 28 views Cluster Edge Deletion on 2-trees Definitions: Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a$P_3$as an induced ... 0answers 26 views How to interpret these adiabatic evolutions? I was trying to study the adiabatic Hamiltonian defined in the paper (arXiv:1207.1712) titled 'Solving the Graph Isomorphism Problem with a Quantum Annealer'. My case is the cycle graph$C_n$when$n$... 1answer 91 views Kth best problem that is NP-hard for K polynomial A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to ... 1answer 74 views Finding All Cliques of an Undirected Graph How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm) 2answers 114 views Characterisation of P in terms of register machines It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown. It is relatively straightforward to prove that indirect addressing ... 0answers 68 views Communication complexity protocols depending on inputs Classical communication complexity requires one protocol (binary tree with edges labeled by bits Alice and Bob send) to solve the problem for every pair of inputs. What if we allow Alice and Bob to ... 0answers 19 views Reference Request : Computing directed domination number of Oriented graphs An oriented graph ($\overrightarrow{G}$) is a directed graph having no symmetric pair of directed edges (arcs). A directed dominating set in a directed graph$D$is a subset$S$of vertex set$V$... 1answer 42 views Efficient update of reachable set of a node in a digraph Given a digraph$G = (V, E)$and a set of vertices$S$, which does not change over the whole process, the goal is to compute the set of vertices,$R_{reach}$, reachable from$S$and the set of nodes , ... 1answer 90 views What is the relationship between tail recursion with other recursions? [on hold] I'm rather confused by the recursion theory. From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ... 0answers 24 views Asking for DFA Problem Solution [closed] Help me to find out the solution, Give a DFA for Σ = {a, b} that accepts strings with ( ab U aba )* 1answer 88 views how to show that there is no derivation in system type [closed] look at my system type (rules of them): $$\frac{\Gamma(x:\tau)\vdash e:\rho}{\Gamma(x:\tau)\vdash \lambda x .e:\tau\rightarrow\rho}$$$$\frac{\Gamma\vdash e_1:\tau\rightarrow\rho\ \ \ \ \ \Gamma\vdash ... 0answers 30 views How does the simplified Stabilizer ZX Calculus limit the Quantum Algorithms expressable? In response to a series of papers demonstrating that the ZX calculus was complete for Stabilizer Quantum Mechanics but not universal Quantum Mechanics, a Stabilizer ZX Calculus was proposed (http://... 2answers 271 views Deciding whether a unary context-sensitive language is regular It is a well-known result that the question Does a context-free grammar generate a regular language? is undecidable. However, it becomes decidable on a unary alphabet, simply because in this ... 0answers 46 views Path finding on graph with state dependent edge costs I'm looking for a version of path planning that is able to find paths in a graph where edge costs depend on the state of the moving entity. In such cases, it is required to also consider trade-offs, i.... 1answer 115 views Median finding with “green forests”? I have a vague memory of a series of papers working to reduce the constant factor in the number of comparisons for deterministic linear time median finding, using increasingly elaborate (but ... 0answers 117 views P/Poly vs Uniform Complexity Classes It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization. What is the smallest uniform class C for which one ... 0answers 56 views Approximating circuits with polynomial of low degree, can't understand small detail in the proof I'm looking at the proof of this lemma: Lemma For every integer$t>0$, there exists a (proper) polynomial of total degree$(2t)^d$that differs with$C$on at most$size(C) 2^{n-t}$inputs Where ... 1answer 67 views What is the recognition complexity of k-uniform k-partite hypergraphs? [duplicate] We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied. It's also ... 1answer 91 views Quicksort: compute the expected number of comparisons as a function of$M$and$t$I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at ... 1answer 190 views NP-hardness on Cayley graphs What is known about complexity of NP-hard problems on Cayley graphs? Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ... 4answers 180 views Find the maximum subset contained by a ball of radius R I am searching for the name of / literature to the algorithmic problem as follows: Given a metric space$(M,d)$, a finite Subset$X = \{ x_1, \dots, x_n \} \subset M$and a fixed Radius$R > 0$,... 0answers 48 views How much variance is captured by the RFF maps? [migrated] The RFF maps here are possibly the most used feature maps. I was wondering if there are cases where anyone has theoretically estimated the total variance captured by these maps? Is any simplification ... 1answer 99 views What's the effect of imposing the following restriction on inductive type families? Let a simple expression be either: A free variable A data constructor of an inductive type family, applied to 0 or more simple expressions What would be the effect of imposing the following ... 1answer 44 views What are the general classes of measured systems Imagine there is a class of system such that a measurement can be performed on an exemplar of this class, each measurement producing 1 bit of information. There are no limitation on how many times the ... 0answers 73 views Distribution attaining minimum discrepancy of disjointness function Is it true that for the optimal distribution$\nu$(not necessarily uniform) that attains minimum discrepancy$\mathsf{disc}(\mathsf{DISJ}_n)$for the disjointness function$\mathsf{DISJ}_n$we have ... 1answer 107 views Pathwidth of planarized drawing of$K_{3,n}$The pathwidth of the complete bipartite graph$K_{3,n}$with partite sets of size$3$and$n$is at most$3$. I am interested in planarizing this graph by the following process: Draw it in the ... 0answers 190 views Efficient algorithm for testing planarity of the union of two planar graphs Let$G_1 = (V,E_1)$and$G_2 = (V,E_2)$both be planar graphs. Is there an efficient algorithm to check whether the union$G = (V,E_1\cup E_2)$is planar? That is, an algorithm more efficient than ... 1answer 67 views Convergence and representation theorems for machine learning I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology. Let's say we have a function$...
I am interested in the complexity of the following problems: Input: an undirected graph $G = \langle V, E \rangle$ Query 1: is there a partition of $V$ into two a clique $C$ and an independent set \$...