Quantum computation and computational issues related to quantum mechanics

learn more… | top users | synonyms (1)

2
votes
1answer
57 views

Complexity class for quantum computer with commutative gates

BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In quantum computer allowed operations can be ...
40
votes
2answers
4k views

Was the reduction in Shor's algorithm originally discovered by Shor?

This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was ...
4
votes
3answers
667 views

Factoring as a decision problem

I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision ...
0
votes
0answers
85 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
7
votes
3answers
883 views

Are there any cases where quantum has given insight for classical algorithms?

To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum ...
5
votes
1answer
68 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 ...
0
votes
0answers
49 views

Known time complexity advantage of quantum algorithms over classical algorithms [duplicate]

I know that this question may depend on how one formulates each complexity class, but in general, what time complexity advantage does quantum algorithms have over classical algorithms?
3
votes
1answer
153 views

Applications of Harrow's algorithm for solving linear equations

In Harrow's algorithm for solving a system of linear equations the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a ...
23
votes
1answer
343 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. ...
6
votes
0answers
42 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 ...
9
votes
2answers
360 views

Quantum algorithms based on transforms other than Fourier transforms

In Quantum Computation and Quantum Information by Nielsen and Chuang they say that many of the algorithms based on quantum Fourier transforms rely on the Coset Invariance property of Fourier ...
13
votes
1answer
240 views

Oracular separations between poly- and log-depth quantum circuits

The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory. Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of ...
1
vote
0answers
35 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 ...
13
votes
6answers
2k 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?
0
votes
1answer
117 views

Quantum Fourier Transform question regarding measurement

When we use the quantum fourier transform, for a function, the output is entangled, so if a measurement is made on the output, the result may not be that of the function that one wanted in the first ...
8
votes
0answers
95 views

Why is BQPSPACE in PSPACE if it can have doubly exponentially long running times?

The standard proof that BQPSPACE is in PSPACE relies on a Savitch game type analysis on path integrals. However, it assumes the time running length for BQPSPACE is at most exponentially long. This is ...
2
votes
0answers
45 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 ...
3
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 ...
4
votes
1answer
112 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, ...
6
votes
1answer
188 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 ...
3
votes
2answers
260 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 ...
3
votes
0answers
105 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 ...
8
votes
0answers
226 views

How powerful is exact “quantum” computing if you suspend unitarity?

Short Question. What is the computational power of "quantum" circuits, if we allow non-unitary (but still invertible) gates, and require the output to give the correct answer with certainty? This ...
4
votes
1answer
210 views

Applications of Quantum Walks?

Can someone explain to me what real world applications could potentially benefit from the study of quantum random walks? I have researched a fair amount on how quantum walks operate and their ...
5
votes
1answer
174 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 ...
1
vote
1answer
215 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
117 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 ...
2
votes
0answers
85 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 ...
1
vote
1answer
90 views

Why is finding the ground state of a Hamiltonian in QMA?

Why is finding the ground stte of a Hamiltonian in QMA? It's in QMA to figure out if a hamiltonian has any energy eigenvalue within a certain window range which is at least inverse polynomial in ...
2
votes
0answers
90 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
97 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 ...
0
votes
0answers
77 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 ...
1
vote
0answers
59 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 ...
-1
votes
1answer
172 views

Differences between Quantum Computing and Parallelism [closed]

What are the differences between Quantum Computing and Parallelism? thanks in advance
5
votes
1answer
118 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 ...
1
vote
0answers
125 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 ...
-6
votes
1answer
129 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
1answer
96 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 ...
2
votes
1answer
135 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
253 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 ...
1
vote
0answers
335 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 ...
4
votes
1answer
163 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 ...
3
votes
2answers
243 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.
18
votes
1answer
203 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 ...
0
votes
1answer
76 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
72 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 ...
5
votes
0answers
151 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 ...
6
votes
0answers
196 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 ...
10
votes
2answers
246 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$. ...
6
votes
2answers
439 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 ...