Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
15
votes
6answers
3k views

Is there a formal proof that quantum computing is or will be faster than classical computing?

Rather than empirical evidence, by what formal principles have we proved that quantum computing will be faster than traditional/classical computing?
7
votes
1answer
175 views

Is any QMA-intermediate problem known?

Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been ...
23
votes
1answer
551 views

The randomized query complexity of the conjoined trees problem

An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ...
11
votes
2answers
313 views

Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem

I've difficulty in understanding the last steps of the AHSP algorithm. Let $G$ be an abelian group and $f$ be the function which hides the subgroup $H$. Let $G^*$ represent the dual group of $G$. ...
7
votes
0answers
63 views

Explicit error bounds on the abelian hidden subgroup problem

What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries? Ettinger, Hoyer, and Knill give a result that the ...
1
vote
0answers
102 views

Non-Transversal Fault Tolerant Gate

I have always heard that transversality is a sufficient, not a necessary condition for fault-tolerance in quantum computation. However, I have never seen any examples of non-transversal fault tolerant ...
2
votes
0answers
53 views

How the errors of the measured quantities of an adiabatic Hamiltonian are inversely proportional to the square root of the number of measurements?

I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says, Since ...
2
votes
1answer
1k views

A quantum algorithm for GCD

Does anyone know of a direct quantum algorithm for computing GCD, - There could be quantum gates for addition subtraction constructed explicitly, using CNOT, etc. - the construction can be done in ...
5
votes
0answers
270 views

Generating quadratic optimization problems amenable to quantum annealing

Some context: there is a current debate in adiabatic quantum computing over whether a particular machine, the D-Wave quantum annealer, can outperform a classical algorithm [*]. Earlier this year, a ...
7
votes
1answer
330 views

Hardness of quantum circuit equivalence?

Given two poly-sized quantum circuits $C_1$ and $C_2$ on $n$ qubits with a universal gate set generated by some finite set of one and two qubit gates. I'm thinking of the gates $\langle H, T, CNOT\...
7
votes
1answer
250 views

What complexity issues are there in considering quantum algorithms with infinite gate-sets?

Short Version Suppose that you want to consider a model of quantum computation in which the gates used in the circuits may depend on the input size. Are there pitfalls to avoid when defining the ...
5
votes
2answers
521 views

Are two-qubit unitaries necessary for universal quantum computation?

I was going through Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians by Daniel Nagaj. In the first sentence of the fifth paragraph on the fourth page, he said, Two-qubit ...
17
votes
1answer
351 views

Which results make quantum space interesting?

Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation? I know many interesting results for quantum computation with sublogarithmic space bounds ...
5
votes
1answer
343 views

Grover's search algorithm for 3 coloring

According to Arora & Barak (pdf), pg. 186, for a polynomial-time computable function $f: \{0,1\}^n \to \{0,1\}$ (represented as a circuit computing $f$), Grover's algorithm finds in $O(\text{poly}(...
20
votes
2answers
964 views

$\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
18
votes
2answers
1k 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 ...
1
vote
1answer
274 views

Running Simon's algorithm on D-wave machine

I was wondering whether Simon's algorithm could be run on a D-wave machine. The Simon's algorithm is a promise problem. On the other hand the D-wave machine can run only quadratic unconstrained ...
10
votes
0answers
203 views

How hard it is to approximate the ground state of the (2-D) Hubbard model

The Hubbard model (see also the wikipedea article on the Bose-Hubbard model) is a basic quantum model of solid-state physics. Question: What is the computational complexity of approximating the ...
3
votes
0answers
172 views

Are NQP and QMA comparable?

Both definitions try to create a quantum analog for NP. NQP's definition comes from non-deterministic algorithms: it contains languages for which a Quantum Algorithm accepts with non-zero probability ...
3
votes
0answers
158 views

Why is Shor's algorithm in $BPP^{BQNC}$ when needing to uncompute subprocedure call?

Why is Shor's algorithm in $BPP^{BQNC}$? It's true the quantum Fourier transform is in $BPP^{BQNC}$, but the algorithm needs to call a number theoretic function f which has period p which is a factor ...
0
votes
0answers
124 views

Determining if a function is constant or not using period finding

Consider an arbitrary boolean function $$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$ which we write as: $$f(x_1, x_2 ... x_n) $$ where each $x_i$ is a boolean variable We note ...
23
votes
1answer
466 views

Sampling satisfiable 3-SAT formulas

Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned ...
0
votes
0answers
131 views

Computing the period of a function using a quantum computer

Consider a blackbox function $$f(x): Z \rightarrow \lbrace 0,1 \rbrace $$ Which inputs an integer and outputs 0 or 1 with bit complexity n. If the period P of this function satisfies $$P \in O(2^{...
1
vote
0answers
92 views

Period of a Multivariable Function using Quantum Computing

consider a function $$f(x_1,x_2...x_n)$$ I am told it is possible to compute the period of the function as a vector $$<l_1,l_2...l_n>$$ where each l denotes the period of the function for ...
4
votes
1answer
189 views

Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm

In the quantum adiabatic algorithm, one prepares the ground state of a Hamiltonian $H_{i}$, and then evolves the Hamiltonian slowly over time to a target Hamiltonian $H_{f}$ via the interpolation $H(s)...
3
votes
1answer
2k views

Differences between Quantum Computing and Parallelism [closed]

What are the differences between Quantum Computing and Parallelism? thanks in advance
24
votes
3answers
1k views

Graph Isomorphism and hidden subgroups

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
6
votes
1answer
160 views

What is the underlying physical principle behind quantum fault tolerance in quantum computation?

What is the underlying physical principle behind quantum fault tolerance in quantum computation? I am trying to follow the mathematical steps behind quantum fault tolerance, and while I can just ...
-6
votes
1answer
207 views

Is the sub-bit model of quantum computation equivalent to other models? [closed]

In a comment to this question Peter Shor asked me for a reference about the third described in the question point of view, namely, that quantum computers can be described as computers that can ...
3
votes
0answers
203 views

Environment-assisted quantum transport computation

The paper below and the news story based on it describe a new form of computation based on what they call environment-assisted quantum transport (ENAQT). ENAQT involves a combination of quantum and ...
12
votes
1answer
349 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 ...
2
votes
0answers
158 views

Quantum algorithm of graphs: How to create superposition of paths?

Let us allow path to have same vertexes in it. (defining) So suppose we have a graph of $N$ vertexes and we want to separate it into some superposition of paths that have $N$ vertexes (so if the ...
4
votes
2answers
336 views

Simulation of every physical quantum system on quantum computer

Let me quote from the section 9.3 of Classical and Quantum Computation by Kitaev, Shen and Vyalyi. With high confidence, we may claim that every physical quantum system can be efficiently ...
2
votes
1answer
2k views

Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as ...
19
votes
1answer
282 views

Is there a geometrical picture for adiabatic quantum computation?

In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily ...
27
votes
5answers
883 views

Quantum proofs of classical theorems

I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be ...
5
votes
1answer
209 views

Is bounded-error probabilistic computation sensitive to transition types?

In the unbounded-error case, it is known that both realtime quantum and probabilistic finite automata can recognize some uncomputable languages if they are allowed to use arbitrary real numbers in ...
2
votes
0answers
1k views

From CHSH inequality to CHSH game

I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by Umesh Vazirani and Thomas Vidick. They have used entangled particles as ...
9
votes
2answers
829 views

Is adiabatic quantum computing as powerful as the circuit model?

Much of the quantum computing literature focuses on the circuit model. Adiabatic quantum computing is not based on applying a sequence of unitary operators, but on changing a time-dependent ...
7
votes
0answers
262 views

Implication of Bell test loopholes on Vazirani-Vidick random sequence generation scheme

I am trying to imagine what would be the implications of the loopholes on Bell test on the random sequence generation scheme proposed by Vazirani and Vidick (VV protocol) in the paper titled '...
3
votes
2answers
334 views

Impacts of quantum computing on Theoretical Computer Science [closed]

Using quantum computers we can do calculations very fast. However from a layman's view, I want to know the impact of quantum computers have on Theoretical computer science.
0
votes
1answer
92 views

Confusion with the proof of constraints for a particular adiabatic quantum evolution

[This might be related to one of my previous unanswered questions.] This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann ...
3
votes
1answer
96 views

Questions about Farhi's pre-Adiabatic paper

I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation. I guess I understand most of the math and physics but I am struggling ...
17
votes
1answer
1k views

The complexity of sampling (approximately) the Fourier transform of a Boolean function

One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P. Here and ...
6
votes
0answers
175 views

Local Hamiltonian and combinatorial search problems

I was going through the PhD thesis of Daniel Nagaj. At the beginning of chapter two he indicated a relation between the local Hamiltonian perspective of adiabatic quantum computation and combination ...
9
votes
2answers
726 views

Quantum PCP and hardness of simulating of Hamiltonians

I have a few questions about Quantum PCP conjecture: What is the statement of the quantum PCP conjecture? What implications would Quantum PCP theorem have for simulating of Hamiltonians? Is it ...
8
votes
2answers
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 ...
7
votes
2answers
509 views

Is there any task where classical computers outperform quantum computers?

Everybody knows that there are whole classes of problems which quantum computers are able to solve much faster (i.e. with fewer instructions) than classical computers. Is there any problem for which ...
1
vote
0answers
176 views

Relationship between size of quantum superposition and rate of decoherence

I am new here in StackExchange and this will be my first question to ask. I have a background in Computer Science and I am interested in looking into Distributed Quantum Computing (DQC). I have read ...
4
votes
1answer
201 views

Quantum oracle for non-negative vector

I was wondering if anyone knew on whether it is possible to construct a quantum oracle that was able to detect whether a given state vector was "non-negative"? Essentially I have a classical problem ...

1
4
5
6 7 8