Unraveling Complexity, Reachability, and Role of Quantum Entanglement

Quantum computing, which uses quantum effects in computational devices, has made significant strides recently, leading to questions about the quantum advantage – the theoretical and practical speed increase quantum computers can offer over classical computers. This advantage is linked to the complexity and reachability of quantum states, which should be complex enough to not be simulated by classical computers without exponential resources, but also reachable on a practical quantum computer.

The role of entanglement and the simulatability of quantum states are also crucial in understanding the quantum advantage. As technology advances, our understanding of these concepts and their applications in quantum computing will continue to grow.

What is the Quantum Advantage in Computing?

Quantum computing, a field that utilizes quantum effects in computational devices, has seen significant progress in recent years. This has led to the question of the origin of the quantum advantage, or the theoretical and practical speed increase that quantum computers can provide over classical computers. While attempts have been made to quantify and characterize this advantage, a universal approach has yet to be defined.

The concept of complexity and reachability of quantum states is one approach to understanding the quantum advantage. Quantum states of interest for quantum computing should be complex, meaning they cannot be simulated with classical computers without exponential resources. However, these quantum states should also be reachable on a practical quantum computer. This means that a unitary corresponding to the transformation of quantum states from initial to desired can be decomposed in a sequence of single and two-qubit gates with no more than polynomial in the number of qubits.

This approach to understanding the quantum advantage is paving the way towards understanding the scope of problems that can be solved by a quantum computer. It does this by formulating a sequence of statements and conjectures on various sets of quantum states.

How Have Developments in Technology Influenced Quantum Computing?

Developments in the technology of producing processors based on semiconductor platforms have consistently increased computational power over the last few decades. This has brought society to an era where computational devices are used daily. However, certain computational problems remain exceptionally high in computational complexity for such devices. Examples include integer factorization, simulating complex quantum systems, and combinatorial optimization problems.

One way to extend computational capabilities is to build a drastically different type of quantum devices that use phenomena that occur at the level of individual quantum objects, like single atoms or photons. These quantum computational devices are considered useful in solving various classes of computational problems that are known to be classically hard.

Historically, the Feynman’s approach to building quantum computers is to use such devices to simulate other quantum systems that are believed to be hard to simulate using classical resources. This is known as the entanglement frontier.

What is the Role of Entanglement in Quantum Computing?

Entanglement is a key concept in quantum computing. For example, consider a state of n-qubits where each of the qubit is described by a certain state. The description of such a state requires 2^n real numbers. However, if we apply a long enough sequence of single-qubit operations and two-qubit entangling operations, then its many-body quantum states become entangled.

This entanglement means there is no obvious way to simulate such a state with linear resources. One may conjecture that we would need resources scaling as 2^n, i.e., exponentially with the system size. For a 100 case, a straightforward simulation requires storing a 2^100-dimensional complex vector in the memory and calculating the results of rotations in 2^100-size space, which seems to be impossible with the use of any foreseen classical computing device.

However, the Gottesman-Knill theorem says that sometimes it is not the case. A many-body entangled state that is prepared by a set of gates belonging to the Clifford set applied to a computational basis state, the so-called stabilizer state, is amenable to polynomial resource strong simulation with respect to any Pauli measurement, including the computational basis measurement.

How Does Simulatability of Quantum States Play a Role in Quantum Computing?

The question of the simulatability of quantum states plays an important role in achieving quantum computational advantage. This is related not only to the amount of quantum entanglement but also to the type of readout measurement and employed gates.

Applying a layer of non-Clifford gates to an entangled stabilizer state just before the computational basis measurement can lead to a quantum computational advantage. This shows that thinking about quantum computers as devices whose computational advantage is related only to the entangled superposition nature of the underlying quantum state is naive.

In conclusion, understanding the quantum advantage in computing requires a deep understanding of the complexity and reachability of quantum states, the role of entanglement, and the simulatability of quantum states. As technology continues to advance, so too will our understanding of these complex concepts and their applications in quantum computing.