Aja viide. Aja lugu.

In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm.^[1] Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.

The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel R. Simon in 1994.^[2] Simon exhibited a quantum algorithm that solves Simon's problem exponentially faster with exponentially fewer queries than the best probabilistic (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries.

This problem yields an oracle separation between the complexity classes BPP (bounded-error classical query complexity) and BQP (bounded-error quantum query complexity).^[3] This is the same separation that the Bernstein–Vazirani algorithm achieves, and different from the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP. Unlike the Bernstein–Vazirani algorithm, Simon's algorithm's separation is exponential.

Because this problem assumes the existence of a highly-structured "black box" oracle to achieve its speedup, this problem has little practical value.^[4] However, without such an oracle, exponential speedups cannot easily be proven, since this would prove that P is different from PSPACE.

Problem description

Simon's problem considers access to a function $f:\{0,1\}^{n}\to \{0,1\}^{m},\;m\geq n$ as implemented by a black box or an oracle. This function is promised to be either a one-to-one function, or a two-to-one function; if $f$ is two-to-one, it is furthermore promised that two inputs $x$ and $x'$ evaluate to the same value if and only if $x$ and $x'$ differ in a fixed set of bits. I.e.,

If

f

is not one-to-one, it is promised that there exists a non-zero

s

such that, for all

x\neq x'

,

f(x)=f(x')

if and only if

x'=x\oplus s

where $\oplus$ denotes bitwise exclusive-or. Simon's problem asks, in its decision version, whether $f$ is one-to-one or two-to-one. In its non-decision version, Simon's problem asks whether $f$ is one-to-one or what is the value of $s$ (as defined above). The goal is to solve this task with the least number of queries (evaluations) of $f$ .

Note that if $x'=x$ , then $f(x')=f(x)$ and $x'=x\oplus s$ with $s=0$ . On the other hand (because $a\oplus b\oplus b=a$ for all $a$ and $b$ ), $x'=x\oplus s\iff x'\oplus x=s$ . Thus, Simon's problem may be restated in the following form:

Given black-box or oracle access to

f

, promised to satisfy, for some

s

and all

x,x'

,

f(x)=f(x')

if and only if

x'\oplus x\in \{0,s\}

, determine whether

s\neq 0

(decision version), or output

s

(non-decision version).

Note also that the promise on $f$ implies that if $f$ is two-to-one then it is a periodic function: $f(x)=f(y)=f(x\oplus s).$

Example

The following function is an example of a function that satisfies the required property for $n=3$ :

$x$	$f(x)$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

In this case, $s=110$ (i.e. the solution). Every output of $f$ occurs twice, and the two input strings corresponding to any one given output have bitwise XOR equal to $s=110$ .

For example, the input strings $010$ and $100$ are both mapped (by $f$ ) to the same output string $000$ . That is, ${\displaystyle f(010)=000}$ and ${\displaystyle f(100)=000}$ . Applying XOR to 010 and 100 obtains 110, that is ${\displaystyle 010\oplus 100=110=s}.$

$s=110$ can also be verified using input strings 001 and 111 that are both mapped (by f) to the same output string 010. Applying XOR to 001 and 111 obtains 110, that is $001\oplus 111=110=s$ . This gives the same solution $s=110$ as before.

In this example the function f is indeed a two-to-one function where ${\displaystyle s\neq 0^{n}}$ .

Problem hardness

Intuitively, this is a hard problem to solve in a "classical" way, even if one uses randomness and accepts a small probability of error. The intuition behind the hardness is reasonably simple: if you want to solve the problem classically, you need to find two different inputs $x$ and $y$ for which $f(x)=f(y)$ . There is not necessarily any structure in the function $f$ that would help us to find two such inputs: more specifically, we can discover something about $f$ (or what it does) only when, for two different inputs, we obtain the same output. In any case, we would need to guess ${\displaystyle \Omega ({\sqrt {2^{n}}})}$ different inputs before being likely to find a pair on which $f$ takes the same output, as per the birthday problem. Since, classically to find s with a 100% certainty it would require checking ${\displaystyle \Theta ({\sqrt {2^{n}}})}$ inputs, Simon's problem seeks to find s using fewer queries than this classical method.

Simon's algorithm

The algorithm as a whole uses a subroutine to execute the following two steps:

Run the quantum subroutine an expected $O(n)$ times to get a list of linearly independent bitstrings $y_{1},...,y_{n-1}$ .
Each $y_{k}$ satisfies $y_{k}\cdot s=0$ , so we can solve the system of equations this produces to get $s$ .

Quantum subroutine

The quantum circuit (see the picture) is the implementation of the quantum part of Simon's algorithm. The quantum subroutine of the algorithm makes use of the Hadamard transform $H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle$ where $k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}$ , where $\oplus$ denotes XOR.

First, the algorithm starts with two registers, initialized to $|0\rangle ^{\otimes n}|0\rangle ^{\otimes n}$ . Then, we apply the Hadamard transform to the first register, which gives the state

{\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.

Query the oracle $U_{f}$ to get the state

{\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |f(k)\rangle

.

Apply another Hadamard transform to the first register. This will produce the state

{\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].

Finally, we measure the first register (the algorithm also works if the second register is measured before the first, but this is unnecessary). The probability of measuring a state $|j\rangle$ is $\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}$ This is due to the fact that taking the magnitude of this vector and squaring it sums up all the probabilities of all the possible measurements of the second register that must have the first register as $|j\rangle$ . There are two cases for our measurement:

$s=0^{n}$ and $f$ is one-to-one.
$s\neq 0^{n}$ and $f$ is two-to-one.

For the first case, $\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}$ since in this case, $f$ is one-to-one, implying that the range of $f$ is $\{0,1\}^{n}$ , meaning that the summation is over every basis vector. For the second case, note that there exist two strings, $x_{1}$ and $x_{2}$ , such that $f(x_{1})=f(x_{2})=z$ , where $z\in \mathrm {range} (f)$ . Thus, $\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}$ Furthermore, since $x_{1}\oplus x_{2}=s$ , $x_{2}=x_{1}\oplus s$ , and so ${\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}$ This expression is now easy to evaluate. Recall that we are measuring $j$ . When $j\cdot s=1$ , then this expression will evaluate to $0$ , and when $j\cdot s=0$ , then this expression will be $2^{-n+1}$ .

Thus, both when $s=0^{n}$ and when $s\neq 0^{n}$ , our measured $j$ satisfies $j\cdot s=0$ .

Classical post-processing

We run the quantum part of the algorithm until we have a linearly independent list of bitstrings $y_{1},\ldots ,y_{n-1}$ , and each $y_{k}$ satisfies $y_{k}\cdot s=0$ . Thus, we can efficiently solve this system of equations classically to find $s$ .

The probability that $y_{1},y_{2},\dots ,y_{n-1}$ are linearly independent is at least $\prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots$ Once we solve the system of equations, and produce a solution $s'$ , we can test if $f(0^{n})=f(s')$ . If this is true, then we know $s'=s$ , since $f(0^{n})=f(0^{n}\oplus s)=f(s)$ . If it is the case that $f(0^{n})\neq f(s')$ , then that means that $s=0^{n}$ , and $f(0^{n})\neq f(s')$ since $f$ is one-to-one.

We can repeat Simon's algorithm a constant number of times to increase the probability of success arbitrarily, while still having the same time complexity.

Explicit examples of Simon's algorithm for few qubits

One qubit

Consider the simplest instance of the algorithm, with $n=1$ . In this case evolving the input state through an Hadamard gate and the oracle results in the state (up to renormalization):

|0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .

If $s=1$ , that is, $f(0)=f(1)$ , then measuring the second register always gives the outcome $|f(0)\rangle$ , and always results in the first register collapsing to the state (up to renormalization):

|0\rangle +|1\rangle .

Thus applying an Hadamard and measuring the first register always gives the outcome $|0\rangle$ . On the other hand, if $f$ is one-to-one, that is, $s=0$ , then measuring the first register after the second Hadamard can result in both $|0\rangle$ and $|1\rangle$ , with equal probability.

We recover $s$ from the measurement outcomes by looking at whether we measured always $|0\rangle$ , in which case $s=1$ , or we measured both $|0\rangle$ and $|1\rangle$ with equal probability, in which case we infer that $s=0$ . This scheme will fail if $s=0$ but we nonetheless always found the outcome $|0\rangle$ , but the probability of this event is $2^{-N}$ with $N$ the number of performed measurements, and can thus be made exponentially small by increasing the statistics.

Two qubits

Consider now the case with $n=2$ . The initial part of the algorithm results in the state (up to renormalization): $|00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .$ If $s=(00)$ , meaning $f$ is injective, then finding $|f(x)\rangle$ on the second register always collapses the first register to $|x\rangle$ , for all $x\in \{0,1\}^{2}$ . In other words, applying Hadamard gates and measuring the first register the four outcomes $00,01,10,11$ are thus found with equal probability.

Suppose on the other hand $s\neq (00)$ , for example, $s=(01)$ . Then measuring $|f(00)\rangle$ on the second register collapses the first register to the state $|00\rangle +|10\rangle$ . And more generally, measuring $|f(xy)\rangle$ gives $|x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )$ on the first register. Applying Hadamard gates and measuring on the first register can thus result in the outcomes $00$ and $10$ with equal probabilities.

Similar reasoning applies to the other cases: if $s=(10)$ then the possible outcomes are $00$ and $01$ , while if $s=(11)$ the possible outcomes are $00$ and $11$ , compatibly with the $j\cdot s=0$ rule discussed in the general case.

To recover $s$ we thus only need to distinguish between these four cases, collecting enough statistics to ensure that the probability of mistaking one outcome probability distribution for another is sufficiently small.

Complexity

Simon's algorithm requires $O(n)$ queries to the black box, whereas a classical algorithm would need at least $\Omega (2^{n/2})$ queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires $\Omega (n)$ queries.^[5]^[6]

Simon's algorithm Qiskit implementation

Below is an example of how one might implement Simon’s algorithm in Python using Qiskit (version 1.3), an open-source quantum computing software development framework by IBM. The code includes a simple way to construct the required oracle (the black box) given a “secret” bitstring.

import numpy as np
from qiskit import QuantumCircuit, transpile
from qiskit_aer import Aer
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import MCXGate

def build_simon_oracle(secret_string: str, num_qubits: int) -> QuantumCircuit:
    """
    Build a Qiskit circuit that represents the oracle for Simon's problem.

    The oracle encodes a function f such that f(x) = f(x ⊕ s).
    For demonstration we create random labels for half the inputs,
    ensuring that the same label is used for x and x⊕s.
    """
    # The oracle acts on a 2*n qubit register:
    #   qubits 0 .. n-1: input register
    #   qubits n .. 2*n-1: output register
    oracle = QuantumCircuit(num_qubits * 2)
    s_int = int(secret_string, 2)
    size = 2 ** num_qubits

    # Create random labels for half of the input space.
    rng = np.random.default_rng(123)  # fixed seed for reproducibility
    f_dict = {}
    used_labels = set()
    for x in range(size):
        x_partner = x ^ s_int
        # Assign a label to x and x⊕s if neither has one yet.
        if x not in f_dict and x_partner not in f_dict:
            label = int(rng.integers(0, size))
            while label in used_labels:
                label = int(rng.integers(0, size))
            used_labels.add(label)
            f_dict[x] = label
            f_dict[x_partner] = label

    # For each x, implement the mapping |x>|0...0> -> |x>|f(x)>.
    # For each output bit j for which f(x)_j == '1', add a gate that flips
    # output qubit (n+j) only when the input register equals x.
    for x in range(size):
        label = f_dict[x]
        # Create bit strings for x and f(x) in LSB–first order.
        # This way, bit position i corresponds to input qubit i.
        x_bin = format(x, f'0{num_qubits}b')[::-1]
        label_bin = format(label, f'0{num_qubits}b')[::-1]

        for j, bit in enumerate(label_bin):
            if bit == '1':
                # Create an MCX gate that fires only when the input register equals x.
                mcx_gate = MCXGate(num_qubits, ctrl_state=x_bin)
                # Append the MCX gate:
                #   Controls: input qubits [0, 1, ..., num_qubits-1]
                #   Target: output qubit (num_qubits + j)
                oracle.append(mcx_gate, list(range(num_qubits)) + [num_qubits + j])
    return oracle

def simon_circuit(num_qubits: int, secret_string: str) -> QuantumCircuit:
    """Construct the Simon circuit using the specified oracle."""
    oracle = build_simon_oracle(secret_string, num_qubits)
    qc = QuantumCircuit(num_qubits * 2, num_qubits)

    # 1. Apply Hadamard gates to the input register (qubits 0..n-1).
    for qubit in range(num_qubits):
        qc.h(qubit)

    # 2. Apply the oracle.
    qc.compose(oracle, inplace=True)

    # 3. Apply Hadamard gates to the input register again.
    for qubit in range(num_qubits):
        qc.h(qubit)

    # 4. Measure the input register (qubits 0..n-1).
    for qubit in range(num_qubits):
        qc.measure(qubit, qubit)

    return qc

def run_simon_experiment(num_qubits: int, secret_string: str, shots: int = 1024):
    """Run the Simon circuit on a Qiskit simulator and return measurement counts."""
    circuit = simon_circuit(num_qubits, secret_string)

    # For visual reference (if in a Jupyter notebook, otherwise print text).
    try:
        display(circuit.draw("mpl"))
    except Exception:
        print(circuit.draw())

    simulator = Aer.get_backend('aer_simulator')
    transpiled_circ = transpile(circuit, simulator)
    job = simulator.run(transpiled_circ, shots=shots)
    result = job.result()
    counts = result.get_counts()

    # Display a histogram of the results
    display(plot_histogram(counts))
    return counts

def solve_for_secret(counts, num_qubits):
    """
    Given measurement outcomes from the Simon circuit, solve for s using
    linear algebra in GF(2).

    Note:
      - Qiskit's get_counts() returns bitstrings with the highest-indexed bit on the left.
      - We reverse each bitstring so that index 0 corresponds to qubit 0.
      - The computed secret s is now output in the same order as the secret provided.
    """
    measurement_vectors = []
    for outcome in counts.keys():
        # Reverse the outcome string so that index 0 is qubit 0.
        vec = [int(bit) for bit in reversed(outcome)]
        measurement_vectors.append(vec)

    # Perform Gaussian elimination in GF(2).
    matrix = measurement_vectors[:]  # make a copy
    rank = 0
    for col in range(num_qubits):
        # Find a pivot row with a 1 in the current column.
        pivot = -1
        for row in range(rank, len(matrix)):
            if matrix[row][col] == 1:
                pivot = row
                break
        if pivot < 0:
            continue  # no pivot in this column
        # Swap pivot row into position.
        matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank]
        # Eliminate below the pivot.
        for r2 in range(rank + 1, len(matrix)):
            if matrix[r2][col] == 1:
                matrix[r2] = [a ^ b for a, b in zip(matrix[r2], matrix[rank])]
        rank += 1
        if rank == num_qubits:
            break

    # In Simon's algorithm, the equations j · s = 0 typically span an (n-1)-dimensional space.
    s = [0] * num_qubits
    if rank < num_qubits:
        # Identify pivot columns.
        pivot_positions = []
        for r in range(len(matrix)):
            pivot_col = None
            for c in range(num_qubits):
                if matrix[r][c] == 1:
                    pivot_col = c
                    break
            if pivot_col is not None:
                pivot_positions.append(pivot_col)
        free_cols = [c for c in range(num_qubits) if c not in pivot_positions]
        if free_cols:
            free_col = free_cols[0]
            s[free_col] = 1  # set one free variable to 1
            # Back-substitute for pivot columns.
            for r in reversed(range(len(matrix))):
                pivot_col = None
                for c in range(num_qubits):
                    if matrix[r][c] == 1:
                        pivot_col = c
                        break
                if pivot_col is not None:
                    xor_sum = 0
                    for c in range(pivot_col + 1, num_qubits):
                        xor_sum ^= (matrix[r][c] & s[c])
                    s[pivot_col] = xor_sum

    # Do not reverse the computed secret; it is now in the same order as provided.
    s_str = ''.join(str(bit) for bit in s)
    return s_str

def main():
    # Example: 3 qubits, secret s = "110" (MSB-first notation)
    num_qubits = 3
    secret_string = "110"

    print(f"Running Simon’s Algorithm with secret s = {secret_string}")
    counts = run_simon_experiment(num_qubits, secret_string, shots=2048)

    print("Measurement results (input-register bitstrings):")
    for outcome, cnt in sorted(counts.items()):
        print(f"  {outcome} : {cnt}")

    s_guess = solve_for_secret(counts, num_qubits)
    print(f"\nGuessed secret string from measurements: {s_guess}")

if __name__ == "__main__":
    main()

Output:

Running Simon’s Algorithm with secret s = 110

Measurement results (input-register bitstrings):
  000 : 523
  011 : 512
  100 : 529
  111 : 484

Guessed secret string from measurements: 110

Explanation of Simon's Algorithm Implementation

This program implements Simon’s algorithm to determine a secret bitstring $s$ hidden by a function $f$ with the property that $f(x)=f(x\oplus s)$ . Here’s a concise breakdown:

Oracle Construction (build_simon_oracle)

Creates a $2n$ -qubit circuit where the first $n$ qubits are the input register and the last $n$ are the output register.
Assigns random labels to each pair $(x,x\oplus s)$ , ensuring that $f$ is $2$ -to- $1$ .
Uses multi-controlled X gates (MCXGate) with custom control states to flip output qubits when the input register matches a particular $x$ .

Circuit Assembly (simon_circuit)

Applies Hadamard gates to the input register to create an equal superposition over all inputs.
Inserts the oracle to entangle the input and output registers.
Applies another round of Hadamard gates to the input register, which causes interference that ensures every measurement $y$ satisfies $y\cdot s=0{\pmod {2}}$ .
Measures the input register to extract these linear constraints on $s$ .

Simulation and Measurement (run_simon_experiment)

Transpiles and runs the circuit on a Qiskit simulator, collecting measurement counts (bitstrings).

Classical Post-Processing (solve_for_secret)

Interprets each measurement outcome as a linear equation in ${\text{GF}}(2)$ .
Uses Gaussian elimination to solve the system, thereby deducing the secret string $s$ .

Execution (main)

Demonstrates the algorithm with an example (e.g., 3 qubits and $s={\texttt {110}}$ ), prints measurement outcomes, and shows the recovered secret.

In summary, the quantum portion of the program prepares a superposition and uses the oracle to encode a hidden periodicity, while the classical portion solves a system of linear equations to deduce the secret $s$ .

References

^ Shor, Peter W. (1999-01-01). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Review. 41 (2): 303–332. arXiv:quant-ph/9508027. doi:10.1137/S0036144598347011. ISSN 0036-1445.
^ Simon, Daniel R. (1997-10-01). "On the Power of Quantum Computation". SIAM Journal on Computing. 26 (5): 1474–1483. doi:10.1137/S0097539796298637. ISSN 0097-5397.
^ Preskill, John (1998). Lecture Notes for Physics 229: Quantum Information and Computation. pp. 273–275.
^ Aaronson, Scott (2018). Introduction to Quantum Information Science Lecture Notes (PDF). pp. 144–151.
^ Koiran, P.; Nesme, V.; Portier, N. (2007), "The quantum query complexity of the Abelian hidden subgroup problem", Theoretical Computer Science, 380 (1–2): 115–126, doi:10.1016/j.tcs.2007.02.057, retrieved 2011-06-06
^ Koiran, P.; Nesme, V.; Portier, N. (2005), "A quantum lower bound for the query complexity of Simon's Problem", Proc. ICALP, 3580: 1287–1298, arXiv:quant-ph/0501060, Bibcode:2005quant.ph..1060K, retrieved 2011-06-06

[1] Shor, Peter W. (1999-01-01). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Review. 41 (2): 303–332. arXiv:quant-ph/9508027. doi:10.1137/S0036144598347011. ISSN 0036-1445.

[2] Simon, Daniel R. (1997-10-01). "On the Power of Quantum Computation". SIAM Journal on Computing. 26 (5): 1474–1483. doi:10.1137/S0097539796298637. ISSN 0097-5397.

[3] Preskill, John (1998). Lecture Notes for Physics 229: Quantum Information and Computation. pp. 273–275.

[4] Aaronson, Scott (2018). Introduction to Quantum Information Science Lecture Notes (PDF). pp. 144–151.

[5] Koiran, P.; Nesme, V.; Portier, N. (2007), "The quantum query complexity of the Abelian hidden subgroup problem", Theoretical Computer Science, 380 (1–2): 115–126, doi:10.1016/j.tcs.2007.02.057, retrieved 2011-06-06

[6] Koiran, P.; Nesme, V.; Portier, N. (2005), "A quantum lower bound for the query complexity of Simon's Problem", Proc. ICALP, 3580: 1287–1298, arXiv:quant-ph/0501060, Bibcode:2005quant.ph..1060K, retrieved 2011-06-06

[1]

[2]

[3]

[4]

[5]

[6]

Aja viide. Aja lugu.

Värsked postitused

Most Used Categories

HC Panter alistus tasavägises mängus lähirivaalile

Pakosta esitab justiits- ja digiministeeriumi kantsleriks Tiina Uudebergi

Trump helistas kõigepealt Putinile, siis Zelenskile – jutt Putiniga oli pikk, Zelenskiga lühike

Soome lasteaiast kadus alla 2-aastane laps, samal ajal ilmus poodi üks kuju

Kas USA kapituleerub Venemaale? Kaitseminister esitas täiesti uue vaate Ukraina sõjale

Ukraina meelitab noori sõdureid tingimustega, mis tekitavad vanades olijates pahameelt

Putin kutsus Trumpi külla: koos hakatakse arutama Ukraina teemat

VIDEO: Vene väed alustasid Ukraina varustustee põletamist Kurski oblastiga

Selgus põhjus, miks Helsingi lasteaia sügavkülmikus olid surnud varesed

Kaja Kallas