Niel de Beaudrap
  • Member for 11 years, 5 months
  • Last seen this week
  • Oxford, United Kingdom
The complexity of decomposing a bi-stochastic matrix
Accepted answer
6 votes

Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using $O(\max\{n^{d+2},n^4\})$ operations over the reals for ...

View answer
How powerful is exact "quantum" computing if you suspend unitarity?
Accepted answer
6 votes

Short answer. It turns out that suspending the requirement of unitary transformations, and requiring each operation to be invertible, gives rise to exact gap-definable classes. The specific classes in ...

View answer
When does randomization stops helping within PSPACE
Accepted answer
9 votes

There is a difficulty with the premise of your question — "when does randomization stops helping within $\mathrm{PSPACE}$ — because it suggests that the computational classes $\mathrm{X}$ ...

View answer
Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?
11 votes

Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin 1974] (PS manuscript) show that the nondeterministic time ...

View answer
Is there any problem which is in AWPP but conjectured to be not in BQP?
4 votes

The relationship of $\mathsf{AWPP}$ to $\mathsf{BQP}$ $\mathsf{AWPP}$ is the class of languages $L$ for which, for each $\varepsilon \in 2^{-O(\mathop{\mathrm{poly}} n)}$, there is $g \in \mathsf{...

View answer
What is the Quantum Cheshire Cat experiments' import to Quantum Computing?
Accepted answer
2 votes

The quantum Cheshire Cat experiments appear to require postselection even to exhibit. Of course, postselection is itself a computational resource (and an extremely powerful one!) for "bounded" error ...

View answer
How does one extend local checkability to quantum complexity classes?
1 votes

A preliminary guess at what it is you're looking for I will give a preliminary answer, in the hopes that it might prompt you to elaborate on what promises to be quite a good question. I will assume ...

View answer
Is there notation for converting a multi-set to a set?
Accepted answer
14 votes

Seeing how this question doesn't appear to be set to be moved to Math.SE (where it would properly belong), I'll answer it here. Multisets are an awkward case of a perfectly natural mathematical ...

View answer
Is there a finite unitary gate set which can exactly realise all QFTs of order $2^n$?
Accepted answer
7 votes

No, there is no decomposition of the entire family $\{F_{2^n}\}_{n\geqslant1}$ into a single finite gate-set. Here's why. The QFTs involve only coefficients over $\overline{\mathbb Q}$, the complex ...

View answer
Why is shifting bits different from shifting qubits?
Accepted answer
11 votes

It's complicated, and depends on whether you approach quantum computing as a technology or a model of computation; and whether you are interested in universal quantum computation, or a special ...

View answer
Is any QMA-intermediate problem known?
8 votes

An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [Cubitt+Montenaro-2013]. From the abstract: In this work we ...

View answer
What complexity issues are there in considering quantum algorithms with infinite gate-sets?
6 votes

To answer my own question: for the purposes of exact computation, there's no need to worry about having too much computational power from linear combinations of algebraic numbers. Details On ...

View answer
What structures allow a notion of 'strictness', 'weakness' and 'mildness'?
3 votes

Complexity theory implicitly makes use of "mild" orders all the time between complexity classes — where there is a relation which is known in one direction, and unknown in another. We might define a ...

View answer
Turing-complete computation models on graphs
2 votes

You can perform universal computation using zero forcing: a simple, repeated transformation of (improper) 2-colourings of vertices. Starting from an initial configuration in which most vertices are ...

View answer
P with integer factorization oracle
10 votes

Elaborating on Joe's earlier answer: note that $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$. The latter is the second lowest class in the "low" hierarchy: which is to say that $\mathsf{NP^{NP \cap ...

View answer
A good reference for complexity class operators?
17 votes

As an introductory reference to the notion of a complexity operator (and demonstrating some applications of the idea), the best I have found so far is D. Kozen, Theory of Computation (Springer ...

View answer
Consequences of NP=PSPACE
Accepted answer
28 votes

If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply: $\mathsf{P^{\#P}} = \mathsf{NP}$That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single ...

View answer
Difference between infinite state machines and turing machines
18 votes

Let me provide you with an algorithm for recursively constructing an infinite state machine to decide any language $L \subseteq \{0,1\}^\ast$ that you like. Make the initial state accept if the empty ...

View answer
Why does randomness have stronger effect on reductions than on algorithms?
12 votes

One reason why it might seem strange to you, that we seem to think there is more apparent (or conjectured) power in the randomized reductions from $\mathsf{NP}$ to $\mathsf{UP}$ than the comparable ...

View answer
Differences between Quantum Computing and Parallelism
11 votes

The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number ...

View answer
What is the underlying physical principle behind quantum fault tolerance in quantum computation?
5 votes

I would encourage you to think of error correction not as entanglement-swapping, per se, but the stimulated dissipation of excitations from a carefully engineered Hamiltonian — not the ...

View answer
Is the sub-bit model of quantum computation equivalent to other models?
6 votes

I'm not sure who would suggest that qubits can meaningfully be described this way, or why anyone would do so. There are simply too many missing details, and it falls afoul of no-go theorems for local ...

View answer
How efficiently can circuits over sets of naturals be transformed to boolean circuits?
2 votes

A simple conversion process for $\boldsymbol\cup\,$, $\boldsymbol\cap\,$, constants, and complements Note that any integer-set circuit representing a set $S \subseteq \{0,1,\ldots,N-1\}$ can be ...

View answer
Efficient representation of set of partial order
Accepted answer
7 votes

Restrictions on pre-orders You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a < b$ rather than merely $a \leqslant b$, so that it ...

View answer
What is the fastest known simulation of BPP using Las Vegas algorithms?
4 votes

Barring any advances in derandomization, it seems to me as though the requirement that the Las Vegas Machine makes no mistakes is crucial, so that there is little to no benefit to having randomness at ...

View answer
Reference request: number-theory-free proof that maximal stabilizer groups determine unique states
Accepted answer
4 votes

For the sake of completeness, I'll note that my version of the proof appears in NdB. A linearized stabilizer formalism for systems of finite dimension. Quantum Information & Computation 13 (pp.&...

View answer
Major advance for measurement based quantum computing?
6 votes

I think that this is an example of a preprint on a crank-friendly topic (specifically it asks: "Is the new claimed [revolutionary result] correct?"). But there are specific remarks that can be made ...

View answer
Bounded depth probability distributions
12 votes

Short answer. For quantum circuits, there is at least one non-limitation result: arbitrary bounded-depth quantum circuits are unlikely to be simulatable with small multiplicative error in the ...

View answer
Factoring Cartesian bitwise join of bit vectors
Accepted answer
5 votes

Passing to the dual hypergraphs to look for products. As you mention in the comments, we may interpret the bitstrings contained in $A$, $B$, and $C$ as edges in hypergraphs. Vertices are the ...

View answer
Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem?
Accepted answer
9 votes

Note that Gödel's Incompleteness Theorems are the following statements: Any formal system which can be used to express arithmetic is either incomplete (there are statements which are neither ...

View answer