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 ...
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 …
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 …
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 ...
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 ...
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 ...
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 …
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 …
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 ...
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 ...
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 ...
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 = …
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 …
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, ...
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: …
Physics results in TCS?
It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are Quantum computation ...
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 ...
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 …
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 ...
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 ...
Polynomial speedups with algorithms based on semidefinite programming
This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time. I am still puzzling over the actual running time of algorithms that compute the solution of …
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 …
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 ...
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 …
Real world applications of quantum computing (except for security)
Let's assume that we have built an universal quantum computer. Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it? I am ...
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 ...
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 …
Ternary (and beyond) computation and quantum computing?
Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved. I have always thought that having more states could improve computing …
Complexity of optimization over unitary group
What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? A typical task, arising often in quantum information theory, would be maximizing a ...
Are there any known implementations for quantum computing constructs?
Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the ...
Email Updates
Log in to receive emails of new questions in this filter. You can receive emails every 15 minutes, every 3 hours, or daily.These users asked the most up-voted questions on this page
