26

The title of your question asks for techniques that are impossible to break, to which the One Time Pad (OTP) is the correct answer, as pointed out in the other answers. The OTP is information-theoretically secure, which means that an adversaries computational abilities are inapplicable when it comes to finding the message. However, despite being perfectly ...


23

The function $f$ is simply an arbitrary boolean function of a bit string: $f\colon \{0,1\}^n \to \{0,1\}$. For applications to breaking cryptography, such as [1], [2], or [3], this is not actually a ‘database lookup’, which would necessitate storing the entire database as a quantum circuit somehow, but rather a function such as \begin{equation*} x \...


23

There is a good explanation by Craig Gidney here (he also has other great content, including a circuit simulator, on his blog). Essentially, Grover's algorithm applies when you have a function which returns True for one of its possible inputs, and False for all the others. The job of the algorithm is to find the one that returns True. To do this we express ...


20

I suppose there is a type of encryption that is not crackable using quantum computers: a one-time pad such as the Vigenère cipher. This is a cipher with a keypad that has at least the length of the encoded string and will be used only once. This cipher is impossible to crack even with a quantum computer. I will explain why: Let's assume our plaintext is ...


19

On computational helpfulness in general Without perhaps realising it, you are asking a version of one of the most difficult questions you can possibly ask about theoretical computer science. You can ask the same question about classical computers, only instead of asking whether adding 'quantumness' is helpful, you can ask: Is there a concise statement ...


19

"Postselection" refers to the process of conditioning on the outcome of a measurement on some other qubit. (This is something that you can think of for classical probability distributions and statistical analysis as well: it is not a concept special to quantum computation.) Postselection has featured quite often (up to this point) in quantum mechanics ...


18

Yes, there are a lot of proposals for Post-quantum cryptographical algorithms that provide the cryptographic primitives that we are used to (including asymmetric encryption with private and public keys).


18

Giving an estimate for a generic quantum chip is impossible as there is no standard implementation for the moment. Nevertheless, it is possible to estimate this number for specific quantum chip, with the information provided online. I found information on the IBM Q chips, so here is the answer for the IBM Q 5 Tenerife chip. In the link you will find ...


16

From a pseudo-foundational standpoint, the reason why BQP is a differently powerful (to coin a phrase) class than NP, is that quantum computers can be considered as making use of destructive interference. Many different complexity classes can be described in terms of (more or less complicated properties of) the number of accepting branches of an NTM. Given ...


15

There are plenty of different variants, particularly with regards to the conditions on the Hamiltonian. It's a bit of a game, for example, to try and find the simplest possible class of Hamiltonians for which simulation is still BQP-complete. The statement will roughly be along the lines of: let $|\psi\rangle$ be a (normalised) product state, $H$ be a ...


15

Google's paper/results are kind of sideways to questions in computational complexity about the relation between $\mathrm{BPP}$ and $\mathrm{BQP}$ (and even further from questions about whether $\mathrm{P}\ne\mathrm{NP}$). It's more as if Google relies on the hypothesis that $\mathrm{BPP}\ne\mathrm{BQP}$ as evidence that their quantum computer performs a ...


13

TL;DR: No, we do not have any precise "general" statement about exactly which type of problems quantum computers can solve, in complexity theory terms. However, we do have a rough idea. According to Wikipedia's sub-article on Relation to to computational complexity theory The class of problems that can be efficiently solved by quantum computers is ...


13

This is not a very enlightening concept, because most interesting quantum algorithms, such as Shor's algorithm, involve some classical computations as well. While you can always shoehorn a classical computation into a quantum computer, it would be at unnecessarily exorbitant cost. We don't yet know, of course, exactly what problems will be hard to solve ...


12

Not sure if this is strictly what you're looking for; and I don't know that I'd qualify this as "exponential" (I'm also not a computer scientist so my ability to do algorithm analysis is more or less nonexistent...), but a recent result by Bravyi et. al presented a class of '2D Hidden Linear Function problems' that provably use fewer resources on a quantum ...


11

There is an important difference between physical operations and logical operations. Physical operations that will be slightly imperfect, performed on qubits that are also imperfect. The rate at which these can be performed depends on what physical system is being used to realize the qubits. For example, superconducting qubits can perform two qubit gates (...


11

Since $U$ is a normal matrix, the spectral theorem applies, i.e. we can write $$ U=\sum_n\lambda_n|\lambda_n\rangle\langle\lambda_n|, $$ where $\lambda_n$ are the eigenvalues, and $|\lambda_n\rangle$ are the eigenvectors. Moreover, since $UU^\dagger=I$, we know that $|\lambda_n|^2=1$, and thus we can write $\lambda_n=e^{-i\theta_n}$ for $\theta_n$ in the ...


10

BQP is defined considering circuit size, which is to say the total number of gates. This means that it incorporates: Number of qubits — because we can ignore any qubits which are not acted on by a gate. This will be polynomially bounded relative to the input size, and often a modest polynomial (e.g. Shor's algorithm only involves a number of ...


9

I don't think there are clear reasons for a 'yes' or a 'no' answer. However, I can provide a reason why PP was much more likely to admit such a characterisation than NP was, and to give some intuitions for why NP might never have a simple characterisation in terms of modification of the quantum computational model. Counting complexity The classes NP and PP ...


9

I believe there are two issues here. The first isn't anything wrong with your statement, but rather that you could make a far stronger (non-quantum) statement by the same reasoning: $\mathsf{P}\neq \mathsf{BPP}$. Why is this? For testing if an $n$ bit function is constant or balanced with certainty (as required by $\mathsf{P}$), it could be that we have to ...


8

I think John Watrous' survey is a great place to start (Professor Watrous recommended it to me a long long time ago and I have been hooked ever since!): J. Watrous. Quantum computational complexity. Encyclopedia of Complexity and System Science, Springer, 2009. arXiv:0804.3401 [quant-ph] To the best of my knowledge, it has the highest complexity classes to ...


8

Suppose a function $f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$ has the following curious property: There exists $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x + y = s$. If $s = 0$ is the only solution, this means $f$ is 1-to-1; otherwise there is a nonzero $s$ such that $f(x) = f(x + s)$ for all $x$, which, because $2 = 0$, means $f$ is 2-to-...


8

For comparison-based sorting (and search) bounds seem to fit the ones of classical computers: $\Omega(N\log N)$ for sorting and $\Omega(\log N)$ for search, as shown by Hoyer et al. A couple of quantum sorting algorithms are listed in 'Related work' section of "Quantum sort algorithm based on entanglement qubits {00, 11}".


8

DISCLAIMER: The quantum-bogosort is a joke-algorithm Let me just state the algorithm in brief: Step 1: Using a quantum randomization algorithm, randomize the list/array, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into $O(N!)$ universes; however, the division has no cost, as it happens ...


7

I find a graphical approach quite good for giving some insight without getting too technical. We need some inputs: we can produce a state $|\psi\rangle$ with non-zero overlap with the 'marked' state $|x\rangle$: $\langle x|\psi\rangle\neq 0$. we can implement an operation $U_1=-(\mathbb{I}-2|\psi\rangle\langle\psi|)$ we can implement an operation $U_2=\...


7

As the other answer conveyed (and to which I am just trying to provide some clarification), post-selection is about just looking at a subset of possible measurement outcomes. To my mind, this falls into two different cases, as below. Yes, they are different aspects of the same thing, but they are used very differently by two different communities. ...


7

There is no such general statement and it is unlikely there will be one soon. I will explain why this is the case. For a partial answer to your question, looking at the problems in the two complexity classes BQP and PostBQP might help. The complexity classes that come closest to the problems that can be solved efficiently by quantum computers of the quantum ...


7

There is always a difference between a quantum system and a classical metaphor. If a system is a qubit in a pure state, then there always exists a measurement basis (or alternatively a proper unitary gate for the standard measurement basis) such that the measurement outcome is 100% predictable, and a measurement basis with measurement outcome 50%-50%. You ...


7

To determine the classical complexity of a problem you need two things, of course: an upper bound (generally an algorithm) and a lower bound. There is an easy randomized algorithm that works with high probability given $O(2^{n/2})$ queries to the function $f$: for a suitable constant $c>0$, generate $k = c 2^{n/2}$ strings $x_1,\ldots,x_k\in\{0,1\}^n$ ...


7

The essential feature of this problem is that while both the quantum and classical algorithms can make use of the efficient classical function of calculating $a^k\text{ mod }N$, the issue is how many times does each have to evaluate the function. For the classical algorithm you're suggesting, you'd calculate $a\text{ mod }N$, and $a^2\text{ mod }N$, and $a^...


7

There is evidently a classical polynomial-time algorithm for finding a four-coloring of a given planar graph, so the answer to the question is "yes" for the trivial reason that every polynomial-time classical algorithm can be implemented as a polynomial-time quantum algorithm. (Also, polynomial time implies polynomial space, for both quantum and classical ...


Only top voted, non community-wiki answers of a minimum length are eligible