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 ...


21

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 ...


20

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 \...


20

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 ...


17

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).


17

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

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 ...


15

"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 ...


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 ...


14

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 ...


14

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 ...


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

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 ...


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 (...


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

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-...


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 ...


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 ...


8

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 ...


7

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 ...


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

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 ...


6

There is a newer result from Robert Beals, Stephen Brierley, Oliver Gray, Aram Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather. They present on Table 2 of Efficient Distributed Quantum Computing the results for bubble sort and insertion sort, it is mainly for "network sorting" but they gave more references about sorting. A quick and very ...


6

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 ...


6

Summary There is a theory of complexity of search problems (also known as relation problems). This theory includes classes called FP, FNP, and FBQP which are effectively about solving search problems with different sorts of resources. From search problems, you can also define decision problems, which allows you to relate search problems to the usual classes ...


6

Sometimes, you might know the eigenvector, and the computational question that you want to answer is what the eigenvalue is. For example, any function evaluation $f(x)$ defined by the action of a $U$ $$ U:|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle $$for $x\in\{0,1\}^n$, $y\in\{0,1\}$ has well defined eigenvectors, $$ |x\rangle(|0\rangle\pm|1\...


6

If you don't supply a $|u\rangle$ as an input, there are two possible things you might want to get out: The $\varphi$ for a randomly chosen (but unknown) eigenstate $|u\rangle$; Both $\varphi$ and $|u\rangle$ for one or more eigenstates. Let's first look at 1. Since eigenstates form a complete basis, any input state you use can be interpreted as a ...


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