Как мне добавить 1 + 1, используя квантовый компьютер?

29

Это можно рассматривать как программное дополнение к тому, как квантовый компьютер выполняет базовую математику на аппаратном уровне?

Этот вопрос был задан членом аудитории 4-й сети Испанской сети по квантовой информации и квантовым технологиям . Человек дал следующее объяснение: « Я материаловед. Вы вводите сложные сложные теоретические концепции, но мне трудно представить практическую работу квантового компьютера для выполнения простой задачи. Если бы я использовал диоды, транзисторы и т. Д., Я мог бы Я легко могу понять, какие классические операции мне нужно выполнить, чтобы добавить 1 + 1. Как бы вы это подробно описали на квантовом компьютере? ».

agaitaarino
источник

Ответы:

21

Согласно связанному вопросу, самое простое решение - просто заставить классический процессор выполнять такие операции, если это возможно . Конечно, это может быть невозможно, поэтому мы хотим создать сумматор .

Существует два типа однобитных сумматоров - полусуммер и полный сумматор . Полусумматор принимает входные сигналы и B и выводит сумму «» (операция XOR) S = A B и «перенос» (операция) C = B . Полный сумматор также имеет «нести в» C я н вход и «выполнить» Выход С о у т , заменяя C . Это возвращает S = A B C i nAВSзнак равноAВСзнак равноAВСяNСоUTСSзнак равноAВСяN и .Cout=Cin(A+B)+AB


Квантовая версия полумесяца

Рассматривая шлюз CNOT в регистре кубитов управляющий регистр B : CNOT A B | 0 | 0 БAB который сразу же дает выходBрегистра какAB=S. Однако нам еще предстоит вычислить перенос, и состояниерегистраBизменилось, поэтому нам также необходимо выполнить операцию AND. Это можно сделать с помощью 3-кубитного логического элемента Toffoli (Control-CNOT / CCNOT). Это можно сделать с помощью регистровAиB вкачестве управляющих регистров и инициализации третьего регистра(C)в состоянии| 0

CNOTAB|0A|0B=|0A|0BCNOTAB|0A|1B=|0A|1BCNOTAB|1A|0B=|1A|1BCNOTAB|1A|1B=|1A|0B,
BAB=SBAB(C)|0, Давая выход третьего регистра в качестве . Реализация Toffoli на регистрах A и B, управляющих регистром C, за которыми следует CNOT с A, управляющим B, выдает выходные данные регистра B в качестве суммы, а выходные данные регистра C - в качестве переноса. Квантовая принципиальная схема полусуммера показана на рисунке 1.AB=CABCABBC

Circuit diagram of a half-adder

Рисунок 1: Принципиальная схема полудуммера, состоящего из Toffoli, за которым следует CNOT. Входные биты и В , что дает сумму S с переносом из C .ABSC


Квантовая версия полного сумматора

4ABCin11|0|A|B|Cin|0:

  1. AB1|A|B|Cin|AB
  2. AB|A|AB|Cin|AB
  3. Toffoli with B and Cin controlling 1: |A|AB|Cin|AB(AB)Cin=Cout
  4. CNOT with B controlling Cin: |A|AB|ABCin=S|Cout

A final step to get back the inputs A and B is to apply a CNOT with register A controlling register B, giving the final output state as

|ψout=|A|B|S|Cout

This gives the output of register Cin as the sum and the output of register 2 as carry out.

Quantum version of the full adder

Figure 2: Circuit diagram of a full adder. Input bits are A and B along with a carry in Cin, giving the sum S with carry out Cout.


Quantum version of the ripple carry adder

A simple extension of the full adder is a ripple carry adder, named as it 'ripples' the carry out to become the carry in of the next adder in a series of adders, allowing for arbitrarily-sized (if slow) sums. A quantum version of such an adder can be found e.g. here


Actual implementation of a half-adder

For many systems, implementing a Toffoli gate is far from as simple as implementing a single qubit (or even two qubit) gate. This answer gives a way of decomposing Toffoli into multiple smaller gates. However, in real systems, such as IBMQX, there can also be issues on which qubits can be used as targets. As such, a real life implementation on IBMQX2 looks like this: Single qubit half-adder on IBMQX2

Figure 3: Implementation of a half-adder on IBMQX2. In addition to decomposing the Toffoli gate into multiple smaller gates, additional gates are required as not all qubit registers can be used as targets. Registers q[0] and q[1] are added to get the sum in q[1] and the carry in q[2]. In this case, the result q[2]q[1] should be 10. Running this on the processor gave the correct result with a probability of 42.8% (although it was still the most likely outcome).

Mithrandir24601
источник
Are there any quantum-computer adders?
John Duffield
@JohnDuffield I'm not sure whether you mean approximate quantum (state) adders (exact state adders are apparently forbidden) or implementations of 'classical' adders on a quantum computer - I haven't tried this particular code out though - or something different?
Mithrandir24601
How are the numbers represented? Is it in Binary?
user3483902
@user3483902 In this case, single bits 0 and 1 using the states |0 and |1 - that is, the 'number' A can be either 0 or 1, as can the 'number' B etc.
Mithrandir24601
@Mithrandir24601 : does it matter? Isn't the answer no in either case? I've actually built a parallel adder myself. I have a Cmputer Science degree.
John Duffield
6

``If I was using diodes, transistors etc I could easily figure out myself the classical operations I need to run to add 1+1. How would you do that, in detail, on a quantum computer?''

Impressive! I suspect that most people cannot easily figure out themselves how to combine diodes and transistors to implement a classical two-bit adde (though I do not doubt this material scientist can probably do it). ;)

Theoretically, the way you implement a classical adder is pretty similar in a classical and quantum computer: you can do that in both cases by implementing a Toffoli gate! (See @Mithrandir24601's answer.)

But the material scientist probably wants to understand how to implement such an gate (or an equivalence sequence of other quantum gates) on a physical device. There are probably an infinite ways to do that using different quantum technologies, but here are two direct realizations of this gate using trapped ions and superconducting qubits:

  1. Realization of the Quantum Toffoli Gate with Trapped Ions, T. Monz, K. Kim, W. Hänsel, M. Riebe, A. S. Villar, P. Schindler, M. Chwalla, M. Hennrich, and R. Blatt, Phys. Rev. Lett. 102, 040501, arXiv:0804.0082.
  2. Implementation of a Toffoli gate with superconducting circuits A. Fedorov, L. Steffen, M. Baur, M. P. da Silva & A. Wallraff Nature 481, 170–172, arXiv:1108.3966.

You can also decompose the Toffoli gate as a sequence of single-qubit and CNOT gates. https://media.nature.com/lw926/nature-assets/srep/2016/160802/srep30600/images/srep30600-f5.jpgenter image description here You can read about how to implement these with photonics, cavity-QED and trapped ions in Nielsen and Chuang.

Juan Bermejo Vega
источник
For disclosure, I was not that materials scientist, but rather, since the neverending discussion was still unsatisfactory and in abstract terms, I was the person that understood what he was asking for, googled for it and showed him a minimal but satisfactory answer (a half-adder on quantiki) in of quantum gates terms.
agaitaarino
5

A new method for computing sums on a quantum computer is introduced. This technique uses the quantum Fourier transform and reduces the number of qubits necessary for addition by removing the need for temporary carry bits.

PDF link for 'addition on a quantum computer', written by Thomas G. Draper, written September 1, 1998, revised: June 15, 2000.

To summarize the above link, addition is performed according to the following circuit diagram (taken from page 6):

enter image description here

To quote the paper (again, page 6):

The quantum addition is performed using a sequence of conditional rotations which are mutually commutative. The structure is very similar to the quantum Fourier transform, but the rotations are conditioned on n external bits.

Arshdeep Singh
источник
1

Parallel computation of the sum of two qubits

I wanted to experience parallel computation of the sum of two qubits, a superposition of 0 and "1 with phase -1" added to 1; and I was inspired by Mithrandir24601's answer. The results are below. I hope my answer is within the context of what was asked. It shows how 1 is added 1, and to 0, at the same time, but whilst both answers are calculated, we can read out the answer to only one of the calculations each time the computation is run. You can see that out of 1000 runs, 417 times we read out the answer "1" (1=0+1), and 380 times and we read out the answer "2" (2=1+1).

(34 times we got nought when the 1 bit was flipped to nought, 54 times we got 0=0+1, 29 times we got 1=1+1, 28 times we got 2=0+1, 42 times we got 3=0+1, and 16 times we got 3=1+1; each of these errors arising no doubt from bit flips, phase flips, or both). enter image description here

I thought an initial π phase (created in the 1st of 3 Hadamard gates) represented a negative digit, but it just represents a positive digit with a -1 phase factor.

A superposition of 0 and "1 with phase -1" in a one qubit register is added to 1 in a two-qubit register. With three qubits, the first two qubits left to right is the sum (or the 3rd and 4th of 5) and the right-most qubit shows whether the ground state (treated as 0) was added or the excited state (1 with an initial phase of -1) was added.

Brendan M
источник