Niel de Beaudrap
  • Member for 11 years, 5 months
  • Last seen this week
  • Oxford, United Kingdom
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
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
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
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
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
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
1-way Quantum Finite Automata Example Question
5 votes

Juan Bermejo Vega has given an accurate summary of what is said in the original paper. I will give you a higher-level description. I will recommend, in your case, to avoid thinking of the amplitudes ...

View answer
What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?
5 votes

I think that a complexity class for decision problems, taking quantum states as input is likely to have a fragile definition. For promise problems, either the definition will be sensitive to numerical ...

View answer
Finding all cycles
5 votes

If you have very few cycles, here's an algorithm which will use less space, but take substantially longer to terminate. [Edit.] My previous run-time analysis missed the crucial cost of determining ...

View answer
Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices
5 votes

Here's a trivial example class [and now, also generalized slightly in view of Esha's comment]: graphs G(h,k,n) constructed from a path of length n, by adjoining a cycle of length h and a cycle of ...

View answer
Finding small sets of integers in which every element is a sum of two others
Accepted answer
5 votes

For N ≥ 10, one can build a strongly self-supporting set of size at most eleven, as follows: {−N, −N+2, −N+4, −2, 1, 3, 4, 5,&...

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 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
What is the best-known inapproximability result for MIN-3CNF-DELETION?
4 votes

The problem MIN-3CNF-DELETION you refer to is better known as MAX-3CNF-SAT (or simply MAX-3SAT for short). Presented as a decision problem, it's the problem of determining (for any input value m) ...

View answer
Is the problem of finding operators to satisfy a list of boolean variables NP complete?
4 votes

Short answer. The operator version of SAT is efficiently solvable — at least, if we assume arbitrary circuits of two-input gates with no fan-out, over any desired choice of gate-set. Long ...

View answer
Is there a standard definition of Quantum Randomness?
4 votes

"Quantum randomness" is just the concept that measurement outcomes in quantum mechanics (and quantum computation) may not be deterministic for a given choice of measurement which you perform on the ...

View answer
Interactive Proofs via Postselection?
4 votes

[Revised.] I have revised my response based on your revisions to your question, I've retained the content of my original response, but made it shorter. The more elaborate description of the "...

View answer
Dinner-table description of theoretical computer science?
4 votes

If you want to give a whimsical look into the past, remind your audience that "computer" used to refer to a person whose profession was to compute things. (And if you want to violate some gender ...

View answer
Quantum Computation - Postulates of QM
4 votes

Addendum. After re-considering the form of your question (e.g. the M†M in the denominator --- as opposed for instance to a single operator M, which suffices for projectors) and reconsulting my ...

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
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
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
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
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
1
2