Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
0
votes
0answers
100 views

What is the relationship between quantum tomography and quantum error correction?

To realize correct quantum computing it seems that both quantum error correction and quantum tomography would be necessary. Is this true? What is the relationship between these two fields?
3
votes
0answers
104 views

Quantum annealing or adiabatic quantum optimization with continuous optimization problems

How do quantum annealing or adiabatic quantum optimization deal with continuous optimization problems such as SDP?
7
votes
1answer
266 views

Evidence that there is some problem in BQP distinct from BPP?

Are there any evidences (1 physics, 2 mathematics AND 3 computer science) that particular problems such as integer factorization, discrete logarithm are in BQP but not in BPP? There do not seem to be ...
1
vote
0answers
107 views

Is Logic Done on Superpositional Bit Values Useful?

Let's say I have a way to represent $N$ bits such that those bits are in a superposition of the $2^N$ possible states those bits can have and that I can do XOR and AND on those superpositional bits to ...
15
votes
1answer
655 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 ...
27
votes
0answers
453 views

Adiabatic quantum computing with level crossings

Question. In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is ...
5
votes
1answer
297 views

How Much Computing Power would be Required to Fully Simulate a Cubic Meter?

Imagine you want to simulate a cubic meter down to the particle. By following the Standard Model and other basic physical equations, how much computing power would be required to do this, in say, a ...
35
votes
1answer
1k views

$BQP$ vs $QMA$?

The central problem of complexity theory is arguably $P$ vs $NP$. However, since Nature is quantum, it would seem more natural to consider the classes $BQP$ (ie decision problems solvable by a ...
3
votes
0answers
68 views

Does simulating chiral gauge theories lie within BQP?

In theoretical physics, there is a branch of quantum field theory dealing with chiral gauge theories. It has been conjectured by Feynman [1] and others that all quantum field theories can be simulated ...
7
votes
3answers
2k 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 ...
19
votes
2answers
594 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 ...
7
votes
1answer
4k views

Quantum annealing vs adiabatic quantum computation

I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...
3
votes
1answer
321 views

How does one determine if a mixed bipartite quantum state is entangled or not?

My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf Mathematically one can think of being given a positive ...
2
votes
0answers
99 views

Claw finding using quantum walk: superposition for Szegedy's framework

Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper: Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
19
votes
1answer
920 views

Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$

In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his ...
4
votes
0answers
180 views

Two questions on Shor's algorithm

Does Shor's algorithm produce factors of a $n$-bit number and discrete log modulo $n$-bit prime in $O((\log n)^{2+\epsilon})$ bit operations using fast multiplication? I am trying to read from ...
2
votes
1answer
274 views

Verifying Shor's quantum error correction code

I know that Shor's 9 bit code can correct phase or bit flip, but I'd like to show that it can correct any type of error on a single qubit. I know that an arbitrary error can be expressed with the ...
4
votes
1answer
787 views

If BQP contains NP, does this mean that P=NP?

There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that ...
3
votes
1answer
186 views

Understanding efficient classical simulation of quantum computing

I want to understand the Gottesman-Knill theorem, which basically says that using some subclass of unitary transformations (from the Clifford group) there is no quantum speed-up ie. we can simulate ...
83
votes
2answers
10k 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 ...
8
votes
1answer
369 views

Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?

The Standard Model of physics (the mathematical model which predicts the Higg's boson) is, as far as I understand, our most complete model of the universe. That is to say, it is the best description ...
8
votes
2answers
488 views

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

DISCLAIMERI do apologize in advance if this question turns out to be silly, for some trivial reason that I may be overlooking in this moment. Suppose for a moment that $\mathbf{P} = \mathbf{BQP}$ ...
9
votes
1answer
409 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 ...
4
votes
1answer
247 views

Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm?

Is it possible to design an efficient approximation algorithm for an $\sf{NP\text{-}complete}$ problem based on reductions from Shor's algorithm? Are known any (classical) approximation algorithms ...
4
votes
1answer
161 views

Probabilistic and quantum analog of $FP$ and $FNP$?

Is there any analog of the computational classes $FP$ and $FNP$ with probabilistic or quantum Turing machines? If so, what are the relation with other computational classes?
1
vote
0answers
36 views

Coset state of $3$-node graph isomorphism problem

The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ...
0
votes
2answers
308 views

Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

Presburger arithmetic is well-known to be decidable but intractable, requiring doubly exponential time even with nondeterminism (Fischer and Rabin, 1974). I am wondering if it is also known whether ...
6
votes
1answer
548 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 ...
-7
votes
1answer
4k views

Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
6
votes
1answer
1k views

Applications of HHL's algorithm for solving linear equations

In HHL's algorithm for solving a system of linear equations (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge ...
29
votes
4answers
6k views

If P = NP were true, would quantum computers be useful?

Suppose that P = NP is true. Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on ...
2
votes
0answers
94 views

Proofs to verify quantum states without revealing their description

Consider the following function $$f_s: k \rightarrow \lvert \psi_k \rangle$$ where $s,k$ are bit strings, and $\lvert \psi_k \rangle$ is a $n$-qubit state. Assume the function is a one-to-one mapping....
0
votes
0answers
30 views

Hardness of finding similar (quantum) states

Consider a quantum state $\lvert \psi \rangle$, we know from the no cloning theorem, that it cannot be perfectly cloned. Also, loosely speaking, that it can be imperfectly cloned s.t. one can produce ...
3
votes
1answer
160 views

How well can an arbitrary (unknown) quantum state be imperfectly cloned?

How well can an arbitrary unknown (quantum) state $\rvert \psi \rangle = \alpha\rvert 0 \rangle + \beta \rvert 1 \rangle$, be imperfectly/approximately cloned? Given an unknown state ${\rvert \psi \...
3
votes
1answer
89 views

Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements

Let $N=2^n$. In Aaronson's Quantum Computing and Hidden Variables (1) and the recent follow up by Aaronson, Bouland, Fitzsimons, and Lee The space "just above" BQP (2), we consider models of ...
1
vote
1answer
194 views

What is the Quantum Cheshire Cat experiments' import to Quantum Computing?

What is the significance of the Quantum Cheshire Cat to Quantum Computing? To recap, the Quantum Cheshire Cat experiment proved it was possible to separate a neutrons' spin from the neutron. Or, in ...
4
votes
3answers
3k views

Will quantum computing pave the way for native, true RNGs?

Obviously, regular computers can't generate random numbers on their own, since they're inherently systematic machines. Would quantum computing be able to run a true RNG without a seed based off user ...
0
votes
1answer
140 views

How does one extend local checkability to quantum complexity classes?

How does one extend local checkability to quantum complexity classes like BQP? Or are quantum algortihms inherently holistic?
3
votes
1answer
177 views

Efficient generation of permutational invariant quantum states

Starting from $|00\cdots 0\rangle$, can permutational invariant quantum states, i.e. the following one: $$ |\psi_n\rangle = \frac1{n!} \sum \prod_{\pi\in S_n} |\pi(0)\rangle|\pi(1)\rangle\cdots|\pi(n-...
3
votes
1answer
322 views

The relationship between QCMA and QMA in the Turing and Communication model

First my background about computational complexity is still beginner. Recent paper published by Klauck and Podder [KP14] show that for the first time an exponential gap between computing partial ...
11
votes
1answer
161 views

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

I am considering ideas about exact quantum algorithms. In particular, I am considering likely limitations of $\mathsf{EQP}$, which consists of languages exactly decideable by polytime-uniform quantum ...
5
votes
4answers
2k 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 ...
2
votes
1answer
243 views

Why are sub-normalized states studied in quantum computation?

By basic postulates of QM, any state of a system is described by a normalised density operator. Now i fail to see why people study sub-normalized states ( e.g.: In generalised fidelity etc). I'd be ...
4
votes
1answer
225 views

Why is shifting bits different from shifting qubits?

In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a ...
3
votes
1answer
141 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 ...
0
votes
1answer
309 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 ...
7
votes
3answers
1k 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 ...
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
171 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
550 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. ...

1 2 3
4
5
8