Quantum computation and computational issues related to quantum mechanics
1
vote
0answers
67 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
184 views
Is the D-Wave architecture a close implementation of quantum interactive proof?
A very high level architecture is, as mentioned here, shown in this picture.
The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is ...
2
votes
1answer
88 views
Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?
In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum ...
11
votes
1answer
406 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 ...
0
votes
0answers
41 views
Is SVP in Lattices equivalent with decoding random linear codes problem in terms of hardness?
Is there any equivalence (reduction) of the Decoding of random linear codes problem which the McEliece cryptosystem is based with the SVP problem where recent lattice base cryptography put its ...
11
votes
0answers
199 views
Runtime of Grover's algorithm
What is the time complexity (not query complexity) of Grover's algorithm? It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration ...
7
votes
2answers
389 views
Is adiabatic quantum computing as powerful as qubit computing?
Much of quantum computing literature focuses on qubit-based computation. Adiabatic quantum computing is not based on qubits. I am looking for insight into any of the following.
Is adiabatic quantum ...
9
votes
1answer
364 views
Is there a quantum NC algorithm for computing GCD?
From the comments on one of my questions on MathOverflow
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer ...
1
vote
1answer
143 views
1st & 2nd quantization from TCS
Last year I attended Scott Aaronson's talk Hawking Quantum Wares at the Classical Complexity Bazaar. Being intrigued by his argument that "[e]ven if quantum mechanics hadn't existed, theoretical ...
2
votes
2answers
155 views
Quantum oracle implementation overhead
I am a physicist getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle ...
0
votes
1answer
90 views
Finding all solutions by Grover search(not superposition)
When there are multiple marked elements, grover search provides only superposition of them. If I want to find all the marked elements, not superposition, I could try this:
1) Do Grover search, get ...
7
votes
0answers
138 views
Is there a candidate for a post-quantum one-way group action?
Is there a known family of group actions with a designated element
in the set that is being acted on, where it is known how to efficiently
$\:$ sample (essentially uniformly) from the groups, ...
-1
votes
2answers
292 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
0answers
191 views
How to Come Up With a Research Proposal for a One Year Master's Degree? [closed]
I have submitted an application to do an M.Phil in Advanced Computer Science at Cambridge University. I have been asked to submit a "research proposal"; I have no idea where to start.
I believe would ...
17
votes
1answer
249 views
Consequences of $BQP \subseteq P/poly$?
While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq ...
5
votes
1answer
108 views
Things that imply BQP Derandomization
I am aware that it is generally believed that P = BPP, but BQP != P (since factoring is in BQP, and factoring seems hard.)
For BPP, we have the hardness vs randomness result: which states that ...
3
votes
1answer
132 views
Quantum oracle for non-negative vector (closed)
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 ...
17
votes
2answers
492 views
Bounded depth probability distributions
Two related questions about bounded depth computing:
1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem ...
7
votes
0answers
197 views
On optimality of Grover algorithm with high success probability
It is well-known that bounded error quantum query complexity of the function $OR(x_1,x_2,\ldots, x_n)$ is $\Theta(\sqrt{n})$. Now the question is what if we want our quantum algorithm to succeed for ...
4
votes
2answers
322 views
Major advance for measurement based quantum computing?
http://arxiv.org/abs/1211.3405
The Measurement Based Quantum Computing Search Algorithm is Faster than Grover's Algorithm
If this recent paper is true, it seems like a major advance for ...
0
votes
1answer
288 views
Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?
Forgive me wise men for my simple words, for I am but a noob.
There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum ...
2
votes
1answer
307 views
Using MATLAB's CVX Package for Semidefinite Programming in Quantum Information
I'm attempting to formulate the semidefinite programs used in the paper "Hedging Bets with Correlated Quantum Strategies" (specifically those on page 7) into CVX so that I can play around with the ...
7
votes
2answers
248 views
Are provable quantum speed-ups possible for classes larger than NP?
In the oracle query model quantum computers can provably achieve a quadratic speed-up over any classical randomized computer [Grover, BBBV].
Are similar speed-ups provably possible for higher levels ...
25
votes
3answers
835 views
A Notion of Monotone Quantum Circuits
In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the ...
13
votes
3answers
304 views
One-way quantum verification
The theory of cluster-state computation is well-established by now, showing that any BQP circuit can be modified so it uses only single qubit quantum gates, possibly classically controlled, provided ...
12
votes
1answer
248 views
Can quantum algorithms with exponential speed-up be rederived using span-programs?
The general adversary lower-bound is now known to characterize quantum query complexity
due to breakthrough work by Reichardt et al. The same line of work also establishes connections
to the span ...
7
votes
0answers
156 views
What are the most recent developments in small-depth quantum circuits?
Back in 2005, Scott Aaronson posted a list of 10 "semi-grand" challenges for quantum computing theory which contained the following challenge:
The power of small-depth quantum circuits. Is $BQP = ...
7
votes
2answers
150 views
Largest set allowing one-step unstructured quantum search
What is the largest set admitting a deterministic quantum search algorithm, for a single marked element, that operates with only a single call to the oracle?
The question is interesting since ...
-2
votes
1answer
134 views
Lower bounds on $Q_{\epsilon}(IP)$
I want to show that $Q_{\epsilon}(IP) \geq (1-O(\epsilon))n$, where $IP:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ is the usual mod 2 inner product.
I have Nayak's lower bound, but I am not sure ...
5
votes
1answer
137 views
Communicating a string of zeros and ones quantumly
Alice wants to communicate an arbitrary $x \in \{0 ,1\}^n$ to Bob. Alice and Bob communicate
in rounds, in each round Alice (or Bob) applies a unitary transformation on his/her part and
transmits a ...
10
votes
1answer
252 views
Distinguishing between $N$ quantum states
Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$?
This problem can be ...
5
votes
1answer
122 views
Known properties of a specific class of quantum states
Recently, I have been studying a quantum protocol for the "Hidden Matching" problem that makes use of states that can be expressed as
$|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^n ...
5
votes
1answer
146 views
A promise problem to decide whether two given pure quantum states are close or far apart
Consider this problem in quantum cryptography:
We have two pure states $\phi_1,\phi_2$ as input and constants $0 \leq \alpha <\beta \leq 1 $, where "Yes instances" are those for which ...
-2
votes
1answer
176 views
What are the obstacles in buidling a practical quantum computer? [closed]
There are quantum algorithms like Shor's factoring algorithm that are implemented in small and experimental cases. But why we still don't have Practical quantum computers? Is there a problem with ...
-1
votes
2answers
248 views
Will we be able to use the current software in quantum computers? [closed]
I'm not sure if this should go here, so my apologies. The fact is that lately I have heard a lot about quantum computers and that they are not that far away. As it is a totally new technology, which ...
11
votes
1answer
119 views
Best method of Error Correction in Quantum Key Distribution
As far as I can tell, almost all implementations of QKD use Brassard and Salvail's CASCADE algorithm for error correction. Is this really the best known method of correcting errors in a shared ...
11
votes
0answers
225 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 ...
6
votes
1answer
253 views
Layman Interpretation: Quantum Factoring Algorithm
I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media.
So, I'm hoping that somebody will be able to help me ...
2
votes
0answers
90 views
Polynomial Quantum Algorithm for Graph Isomorphism? [duplicate]
Possible Duplicate:
NP-intermediate problems with efficient quantum solutions
Many suspect that quantum computers will not be able to efficiently solve NP-complete problems and thus focus ...
10
votes
1answer
172 views
Notation for a Conditional Hamiltonian Evolution Operator
I am reading Harrow, Hassidim, and Lloyd's paper Quantum algorithms for linear systems of equations. On the third page of that paper, they write
Next we apply the conditional Hamiltonian evolution ...
16
votes
0answers
212 views
Geometric picture behind quantum expanders
(also asked here, no replies)
A $(d,\lambda)$-quantum expander is a distribution $\nu$ over the unitary group $\mathcal{U}(d)$ with the property that: a) $|\mathrm{supp} \ \nu| =d$, b) $\Vert ...
13
votes
0answers
277 views
Is there any known nontrivial result on QIP systems having a space-bounded verifier?
Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier?
The only paper I know is An application of quantum finite automata to interactive ...
9
votes
3answers
445 views
1-way Quantum Finite Automata Example Question
I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be ...
4
votes
0answers
131 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 ...
8
votes
1answer
335 views
Uniform way of quantifying “branching” in nondeterministic, probabilistic, and quantum computation?
The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is ...
5
votes
1answer
326 views
Quantum algorithms for determining whether two sets intersect
Grover's algorithm is a quantum algorithm that is able to locate a special record in an $N$ element unsorted database in $\Theta(\sqrt{N})$ time. What quantum algorithms are known to determine whether ...
7
votes
1answer
384 views
What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?
JBV suggested I turn some comments into a question, so here goes.
Another question [1] asks about applications of QM computing. One answer [2] was "efficiently simulating quantum mechanics". ...
6
votes
1answer
90 views
Quantum capacity for ensemble of Pauli channels
In Preskill's quantum computing notes Chapter 7 approximate page 82, he shows that a Pauli channel has capacity $Q \geq 1-H(p_I,p_X,p_Y,p_Z)$ where $H$ is Shannon entropy and $p_I, p_X, p_Y, p_Z$ are ...
19
votes
0answers
158 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 ...
22
votes
2answers
140 views
Computational complexity of quantum optics
In "Requirement for quantum computation", Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table:
MY question is three-fold:
...
