Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
14
votes
1answer
664 views

What is known about multi-prover interactive proofs with short messages?

Beigi, Shor and Watrous have a very nice paper on the power of quantum interactive proofs with short messages. They consider three variants of 'short messages', and the specific one I care about is ...
-6
votes
1answer
341 views

Quantum complexity class vs classical complexity class [closed]

What is the relation between BQP complexity class and P and NP?
7
votes
3answers
3k views

Ed. Witten's new paper and the simulation of a quantum field theory

Context: Ed. Witten recently wrote a potentially revolutionary paper where he showed that under certain conditions, a Chern-Simons path integral in three dimensions is equivalent to an N = 4 path ...
12
votes
1answer
317 views

Transitioning from quantum to classical random walks on the line

Quick version Are there models of decoherence for the quantum walk on the line such that we can tune the walk to spread as $\Theta(t^k)$ for any $1/2 \leq k \leq 1$? Motivation Classical random ...
6
votes
3answers
1k views

Physical realization of nonlinear operators for quantum computers.

I have read in a paper where nonlinear operators for quantum computers implies the solving of problems in #P time. See http://arxiv.org/pdf/quant-ph/9801041 . What would be the simplest realization of ...
18
votes
2answers
995 views

Computation beyond unitary matrices

Just out of curiosity, if the classical computation is about permutation matrices and quantum computing is about unitary matrices (of which the permutation matrices are a subgroup), then will there be ...
17
votes
1answer
457 views

Using the extra power of the negative adversary method

The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that ...
1
vote
1answer
205 views

Computational Library to compute Quantum Cluster States

I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? ...
6
votes
1answer
260 views

Proof that Entanglement Cannot Increase the Capacity of a Noiseless Classical Channel

I am aware that quantum entanglement cannot increase the asymptotic capacity of a noiseless classical channel. However, can anyone provide some type of reference in the literature that contains a ...
1
vote
1answer
257 views

Branch prediction in quantum algorithms

Are there any good examples of branching efficiency / prediction in quantum algorihms? Specifically suppose I have a set of CNOT gates one after the other that have the control line on the same line ...
6
votes
3answers
593 views

Why does the Complexity Class PostBQP makes proving PP greater than or equal to QMA easier?

PP was proved greater than QMA in by Kitaev and Watrous 2000 - Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems. Later Aaronson proved that PostBQP ...
10
votes
1answer
402 views

Why must QMA complete problems be promise problems?

I'm reading Watrous's excellent survey paper on paper on quantum complexity theory. In it he states that it would be surprising if a QMA -complete problem were found to have a vacuous promise (I.e. Be ...
11
votes
2answers
497 views

Nonlocal Games and Quantum Communication

I'm currently on the look out for some good reference material relating non-local games with beneficial aspects in quantum communication. For instance, I am aware that non-local games are good at ...
10
votes
4answers
444 views

Quantum Bell-Type Inequalities

I'm curious if someone could recommend some supplementary material for gaining a deeper understanding of the paper : "Some Results and Problems on Quantum Bell-Type Inequalities - Tsirelson". ...
4
votes
1answer
639 views

Qubits and permutation symmetry

To put it straight - are qubits fermions, bosons or else? For example, the Bell states that are frequently used in quantum computations have different symmetry (00 + 11 is symmetric, 10 - 01 is ...
2
votes
0answers
857 views

Are quantum computers turing complete? [closed]

I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial ...
7
votes
4answers
2k views

Von Neumann architectures and quantum computing

Can you do quantum computing in a von neuman architecture? If not, why? What is the constraint? If you control a qbit, can a quantum computer use the von neuman architecture? Thanks.
14
votes
1answer
629 views

Reading up on $BQP = BPP^{BQNC}$

What should I read to understand this problem? The power of small-depth quantum circuits. Is $BQP = BPP^{BQNC}$? In other words, can the "quantum" part of any quantum algorithm be compressed ...
9
votes
1answer
381 views

What is the proper role of verification in quantum sampling, simulation, and extended-Church-Turing (E-C-T) testing?

Since no answer was given, a flag has been set requesting that this question be converted to a community wiki. The comments by Aaron Sterling, Sasho Nikolov, and Vor have been synthesized into the ...
5
votes
1answer
495 views

Is there any problem which is in AWPP but conjectured to be not in BQP?

Is there any known problem which is in $\mathsf{AWPP}$ but conjectured to be not in $\mathsf{BQP}$? What about relative to an oracle? Is there any known problem in $\mathsf{MQ^2}$ which is ...
10
votes
2answers
360 views

Restricting entries of unitary operators to real numbers and universal gate sets

In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-...
5
votes
1answer
245 views

Quantum Channel Decoding

Let a quantum channel $\Phi(\cdot)$ between two Hilbert spaces $\mathcal{H}_{in}$ and $\mathcal{H}_{out}$. What is the quantum channel $\Phi_{inv}(\cdot)$ that best reverses $\Phi(\cdot)$ ? $\forall $...
19
votes
1answer
615 views

Does cryptography have an inherent thermodynamic cost?

Reversible computing is a computational model that only allows thermodynamically reversible operations. According to Landauer's principle, which states that erasing a bit of information releases $kT ...
8
votes
0answers
315 views

Approximation of Quantum Channels

Background: In quantum information theory, a wide class of processes acting on stochastic quantum states can be described using the formalism of Quantum Channels: A quantum channel is a linear, ...
15
votes
2answers
592 views

Quantum PAC learning

Background Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If ...
5
votes
1answer
336 views

How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?

In quantum computation there is a fair amount of interest in the task of simulating quantum physics. One instance of this is the problem of simulating the evolution of a system under the action of ...
7
votes
4answers
436 views

Is there a standard definition of Quantum Randomness?

I hope this question is not too vague. For classical bit generators there is the classical statistical definition which (informally) states that a source is ideally random if its output $X_1,X_2,\...
13
votes
1answer
310 views

Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

Context. I am writing on topics such as the Gottesman-Knill theorem, using Pauli stabilizer groups, but in the case of d-dimensional qudits — where d may have more than one prime factor. (I ...
32
votes
2answers
1k views

Consequences of $SAT \in BQP$

As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far: Quantum computers are not known to ...
27
votes
1answer
4k views

Shor's factoring algorithm help

I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm. Given an $N$ we want to factor, we choose a random $x$ which has order $r$. The first step involves ...
10
votes
4answers
627 views

Bounding the gap between quantum and deterministic query complexity

Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, ...
-8
votes
1answer
425 views

Duality computers

There is a lot on the internet about quantum computers and how they could factor integers. However, there is a type of computer which also uses the principles of quantum mechanics, which can be used ...
10
votes
1answer
415 views

Span programs, witness size, and certificate complexity

A span program is a linear-algebraic way of specifying a boolean function introduced here. Recently, this model was used to show that the negative adversary method provides a tight characterization (...
9
votes
3answers
541 views

Interactive Proofs via Postselection?

Define the computational model MPostBQP to be identical to PostBQP except we allow polynomially many qubit measurements before the post-selection and final measurement. Can we give any evidence ...
9
votes
2answers
240 views

Polynomial algorithms for UPB (Unextendable Product Bases)

Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n ...
1
vote
2answers
352 views

Quantum evolutions

I was reading Quantum Computation Explained to my Mother. While considering the following problem: Problem 1 Suppose we are given a mysterious boolean operator F (a black box) which takes one ...
7
votes
2answers
447 views

Quantum query complexity and certificate complexity

A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum ...
2
votes
2answers
367 views

Time-entanglement phenomenon

Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know). The general notion of algorithm is model of ...
17
votes
2answers
362 views

Is PARITY in QAC_0 (if that even makes sense)

As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in fact const-dept circuits require EXP number of gates. What about QUANTUM circuits? a) Can PARITY be done with a ...
9
votes
1answer
616 views

Lower bounds on the Threshold function

In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
19
votes
3answers
5k views

Is there any connection between the diamond norm and the distance of the associated states?

In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such ...
-3
votes
2answers
391 views

Understanding function controlled NOT gate

...
3
votes
1answer
251 views

Background Required to understand Quantum Monte Carlo techniques?

I'm trying to decide whether or not to do a project for a professor. The project involves writing a survey paper (of high enough quality to get his research group up to speed for a peripheral project)...
18
votes
3answers
725 views

Is there a Quantum equivalent of the Time hierarchy theorem ?

My favourite theorem in complexity theory is the Time hierarchy theorem. However, this was done in 1965. I wanted to know then if there was anything similar for Quantum Computing. Also, if not ...
14
votes
2answers
857 views

Quantum analogues of SPACE complexity classes

We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in ...
1
vote
0answers
255 views

Separating the QIP hierarchy

Background: I'm a CS grad student. I've taken a course on computational complexity. Question: Can you suggest an introductory book on quantum computation, especially regarding the details of ...
27
votes
2answers
2k views

NP-intermediate problems with efficient quantum solutions

Peter Shor showed that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) ...
23
votes
1answer
446 views

Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we dont know how to sample using classical computers. For example if f is a Boolean function (from $\{-1,1\}^n$ to ${-1,1}$) that can be ...
11
votes
2answers
574 views

What is the Relationship between QMA and AM?

I read in S. P. Jordan, D. Gosset, P. J. Love's "$QMA$-complete problems for stoquastic Hamiltonians and Markov matrices" that it is unlikely that $QMA \subseteq AM$. I was surprised about this ...
20
votes
2answers
750 views

Are there descriptive complexity representations of quantum complexity classes?

The title more or less says it all, but I guess I could add a bit of background and some specific examples I'm interested in. Descriptive complexity theorists, such as Immerman and Fagin, have ...