2021년 10월 26일 화요일

Hardware Security-preserving Android Remote Unlocking Service using Synthetic Password

이 글은 제가 IEEE SecDev 2021 [1] 에 투고하여 게재된 글입니다. 논문의 Footnote 와 Reference 는 하나로 통합합니다.

Abstract

Remote unlocking for Android devices may benefit both users and manufacturers. Users can continue using the device without factory-resetting when they unexpectedly forget their passphrases. Manufacturers can improve non-face-to-face customer services in the COVID-19 era. Nevertheless, not many manufacturers support remote unlocking services for Android devices. If the remote unlocking service is triggered by requests over-the-air, it may increase the attack surface of Android security. Android security is hardware-based (e.g., hardware-backed Keystore), so we seek to preserve this security level by designing a new remote unlocking service without modifying trusted execution environments. Our design supports two-factor authentication, distributed authority, trust-boundary minimization, and key management.  Since a synthetic password used for remote unlocking is not exposed to the outside of an Android device, the manufacturer still cannot unlock the device without user consent. We identify 208 security threats in the proposed remote unlocking service using the STRIDE model and ensure that our design has countermeasures for all high-level security threats. After passing quality verification and penetration tests, the proposed remote unlocking service has been officially installed on commercial devices.

Ⅰ. Introduction

An Android remote unlocking service allows its user to unlock an Android device through the Internet [2]. Once a user registers a passphrase such as a PIN, pattern, or password with an Android device, a screen lock is set. If supported, the user can also activate the remote unlocking service for her device. After this, when the user cannot unlock the device (say, forgetting her passphrase), the user can visit the remote unlocking service website and make the device unlocked via the Internet. The device receives a secure message over the Internet and can be unlocked.

Not many manufacturers support such a service due to the difficulty of designing and implementing a secure remote unlocking service. From the perspective of security, the remote unlocking service can be risky since it inevitably increases the attack surface. Because, unlike conventional offline device unlocking, this service allows device unlocking through the Internet. Thus, if the remote unlocking service is not carefully designed, the device might be unlocked by a malicious attacker and its user's personal data might leak.

However, from the perspective of usability, the remote unlocking service benefits both users and device manufacturers. If the device users accidentally forget the passphrase of the screen lock, the remote unlocking service provides users with an alternative method of unlocking their device. In this way, the device can be reused without performing factory-resetting. In contrast, an Android device that does not support the remote unlocking service needs factory-resetting to be reused if the device cannot be unlocked. [3] Due to the unwanted factory-resetting, users lose valuable data such as photos, contacts, and text messages that have not been backed up. Briefly, since the remote unlocking service allows users to unlock their devices without going through factory-resetting, the users can avoid this data loss.

Remotely unlocking devices also helps increase the manufacturer's profit. The manufacturers can improve customer services by supporting remote unlocking services. Also, since non-face-to-face services reduce customer visits to the service center, the manufacturers can save their customer service costs. Especially in the COVID-19 era, adopting non-face-to-face services is highly encouraged.

For the devices with Android 10 or higher, file-based encryption (FBE) is essential to obtain Google mobile service (GMS) certificates [4]. Once FBE is applied to an Android device, the master key that encrypts the device is derived from the user's passphrase. Thus, even its manufacturer, who has the system permission authority, cannot obtain the information about the encryption key. It means that it is hard for the manufacturer to overhaul the locked device. Assume that there is an Android device that cannot be unlocked. If the user claims that the correct passphrase cannot unlock the device, the manufacturer must struggle to determine whether the user typed an incorrect passphrase or the device is defective. In general, any software and hardware have the possibility of malfunctioning. Moreover, the Android user authentication consists of various modules such as Keyguard, Lockscreen, Gatekeeper, LocksettingService, Keymaster, and Keystore. Thoughtful manufacturers conduct comprehensive testing before launching their devices, but testing all use-cases is impossible. If the device supports the remote unlocking service and the user enabled the service, the manufacturer can help the user unlock her device. Then, under the user agreement, the manufacturer can examine the locked device to find which module went wrong.

The advantages and challenges of the remote unlocking service are evident. While this service benefits both users and manufacturers, it also increases the attack surface. Thus we seek to develop a new remote unlocking service that preserves the security level of Android. The proposed remote unlocking service utilizes a synthetic password (SP). Therefore, it preserves the hardware-backed security level, but it requires no modifications to the Android hardware security. To the best of our knowledge, the proposed remote unlocking service is the first case to leverage the SP for personal users, not for enterprises.

We adopt the STRIDE model [5] to identify the threats and add the corresponding countermeasures in security design. Finally, the proposed solution has been installed onto commercial devices after passing quality verification by a manufacturer and penetration tests by a third party.

The rest of this paper consists of the following. Section Ⅱ briefly describes the current Android security features. Section Ⅲ addresses our security design. Section Ⅳ explains our security design from an implementation perspective. Section Ⅴ analyzes security threats and describes their countermeasures. Section Ⅵ compares our research with other works. In Section Ⅶ, we share the conclusions.

Ⅱ. Background

Android provides various security features, which are leveraged to design the proposed remote unlocking service.

A. Synthetic Password

User authentication in modern Android devices is based on hardware security [5]. User passphrases are encrypted and stored in the device's hardware-backed Keystore and not exposed outside the device. For personal Android devices, a device user is the same as its owner. However, in enterprise scenarios, a device user and an owner may be different [6]. In the enterprise scenario, the device owner should be able to reset the passphrase set by the previous user so that other users can reuse the device. For this, Android introduces a security primitive, the SP, starting from its version 8 (or Oreo). The DevicePolicyManager (DPM) in the Android framework provides application programming interfaces (APIs) that only the device owner (specifically, the organization's IT administrator) can activate and use the SP to unlock the device with a reset password token (RPTkn) [7][8].

B. Android Application Sandbox

The Android platform uses Linux user-based protection to identify and isolate an app's resources [9]. The user ID (UID) that Android assigns to each app provides a kernel-level app sandbox, and each app runs in the sandbox. Thus, Android apps cannot communicate directly with each other by default. Instead, only limited access through the OS is allowed. Also, since the app sandbox is inside the kernel, this security mechanism protects all modules above the kernel. To break the sandbox, the Linux kernel must be compromised. However, as Android has been upgraded, various access controls such as SELinux and kernel protection schemes have been applied [9].

C. Android Application Integrity

All apps running on the Android platform must be signed by their developers [10]. Also, legitimately signed apps normally run with different UIDs. However, if an app wishes to share the same sandbox with other apps at runtime, these apps must be signed with the same key. The apps signed with the same key can declare a shared UID in their Android manifest files. As the Android app signing scheme has been upgraded, the performance and security have been further enhanced [10].

D. Android Permissions

Android apps declare permissions in their manifest files to interact with other apps. Specific permissions are verified at the app's install time or execution time. Thus, they can be limited depending on the app's signature. Also, new permissions can be declared to restrict access from other apps [11].

Ⅲ. Security by Design

The security level of modern Android devices is deemed hardware-backed security [12][13]. This means that a user's keys are not exposed outside of its hardware security module (HSM). Thus, even the device manufacturer cannot arbitrarily unlock the device without the consent of the user.

A. Design Goals

In this section, we cover the security goals in the design of our remote unlocking service.

1) Preserving hardware-backed security: Security parameters used in remote unlocking must have a trust anchor that has its basis in the HSM. In a nutshell, a symmetric key for an AES cipher should not be exposed outside of the Android hardware Keystore, and the private key of an RSA cipher should not be disclosed outside of the HSM. See Section Ⅳ.A for details.

Even standard security measures would have vulnerability if poorly operated or unexpectedly misimplemented. Therefore, relying on a single security measure would not provide a sufficient security level. So, we intentionally overlap multiple security measures if the security enhancement is needed. See Section Ⅳ.F for details.

2) Two-factor authentication: In general, there are three types of authentication mechanisms, what-you-know, what-you-have, and what-you-are. A password represents what-you-know authentication. A credit card is an example of what-you-have. Biometric features such as fingerprint and iris are what-you-are authentication. We secure the proposed remote unlocking service by combining two of the three authentication techniques. First, requesting the user to enter her ID and password is the what-you-know authentication. Second, a mobile device itself can be the what-you-have authentication as only the user who possesses the device can trigger the remote unlocking service (say, selects a button in the device screen). Therefore, even the service providers [14] cannot unlock the device they do not have. See Figure Ⅰ and Section Ⅲ.C.2 for details.

3) Distributed authority: The unlocking server could be implemented as a single entity. However, to avoid the single point of compromise, our design divides the unlocking server into three entities: an account server, a database server, and a web interface server. That is, the compromise of a single server will not lead to unlocking an arbitrary device (Suppose that the attacker obtains an Android device of arbitrary victims.). See Figure Ⅱ and Section Ⅲ.C.2 for details.

4) Trust-boundary minimization: Besides third-party apps signed with the private keys of corresponding developers, an Android device has many system-privileged apps of different developers signed with the same platform key [15]. As the system-privileged apps can also call the SP-related APIs even if they are not related to the remote unlocking service, we need to add a new access control mechanism beyond the Android permission system. See Ⅳ.D for details.

5) Key management and compatibility: The server administrators should be able to change the public/private key pairs in their HSMs, e.g., due to key expiration or cipher change. Also, the proposed design should support forward compatibility by allowing the administrators to add new parameters related to the ciphers or expand the service functions. Meanwhile, it must consider backward compatibility for devices whose update support is expired. See Section Ⅳ.F for details.

Figure Ⅰ. Data flow diagram of device registration phase

B. Design Components

The structure of our service is shown in Figure Ⅰ. This section describes the major data elements and functional components of our service.

1) Reset password token (RPTkn): This is a 256-bit random value generated by an Android device that may have to be unlocked later. This is neither stored in the device storage nor left in the memory. Immediately after being generated, the RPTkn is encrypted with the hardware-backed AES key and then encrypted again with the RSA public key of the database server (DBS) by the remote unlocking app (RUApp). It will then be delivered to the DBS over TLS and zeroized in the device. When the device registration phase completes, the DBS stores the AES encrypted RPTkn. Thus, even the DBS cannot see the plaintext RPTkn.

2) User service account (USAcnt): This is the user's service account value saved in the device, for example, userid@manufacturer.com. To activate the remote unlocking service, the user saves her account in the AccountManager of the Android framework and agrees to the terms of the service. The service agreement includes that a network connection is enabled by RUApp when the remote unlocking service is triggered. Since the USAcnt is authenticated by a single entity, which is the account server, the same USAcnt is used in both the device and the web interface server (WIS). This data is encrypted with the RSA public key of the WIS by RUApp and decrypted in the WIS. Thus, the DBS cannot see the plaintext USAcnt.

3) Device Identifier (DevId): This data is an inherent value by which the service provider identifies a specific device. This is an international mobile equipment identity (IMEI) value for a device that can make a phone call, or a manufacturer serial number (MSN) value for a device that supports WiFi only. This is encrypted with the RSA public key of the DBS and transmitted to the DBS and WIS over TLS.

4) Remote unlocking app (RUApp): We develop this app from scratch for the remote unlocking service. Only this app can access new DPM APIs that control the SP in personal use scenarios (See Ⅳ.D). It also performs TLS connection setup with the DBS, payload encryption using an RSA cipher, payload signature / nonce / timestamp verification, RPTkn generation, AES encryption, and decryption of an RPTkn using the Android Keystore.

5) Database server (DBS): This server handles the communication with the device over TLS and stores the encrypted RPTkn of the device. The payload received from RUApp is decrypted using the DBS's RSA private key stored in its HSM. Also, the DBS delivers a part of the payload from RUApp to the WIS or the payload received from the WIS to RUApp.

6) Web interface server (WIS): We develop this server from scratch to handles the unlocking request from the user. The user visits the WIS and logs in using her USAcnt, which was saved on her device. When the device is waiting for remote unlocking, the user can select the device on the web page using another online machine.

C. Data Flow Diagrams (DFDs)

Our remote unlocking service has two phases: device registration and device unlocking. Each phase consists of the following interactions. See Section Ⅳ.F for details.

1) Device registration: Figure Ⅰ shows the DFD of the device registration phase. After the user sets her passphrase with LockSettingsApp, she can activate the remote unlocking service. As a precondition [16], (R1) LockSettingsApp calls AccountApp to set her USAcnt. (R2) The device user logs into her USAcnt via the Account server. (R3) If succeeded, the USAcnt is saved in AccountManager. (R4) The user activates the remote unlocking service. (R5) LockSettingsApp checks whether the user accepts the service agreement and (R6) requests RUApp to create an RPTkn. (R7) RUApp creates the RPTkn using remote unlocking APIs added to the DPM and performs AES encryption using the Keystore. (R8) RUApp returns only the pass/fail result of RPTkn creation to LockSettingsApp. (R9) LockSettingsApp calls KeyGuardApp to request the user to input the passphrase again. (R10) The user inputs the current passphrase [17]. (R11) LockSettingsApp requests RUApp to register the RPTkn with the DBS. (R12) RUApp gets the USAcnt through AccountManager and encrypts it with the RSA public key of the WIS. The RPTkn and DevId are encrypted with the RSA public key of the DBS. (R13) Then RUApp transmits the payload (see Figure Ⅲ) including the device's nonce (DevNonce) to the DBS through a TLS connection. (R14) The DBS decrypts the payload by using its HSM. (R15) The DBS sends the DevId and encrypted USAcnt to the WIS. (R16) The WIS uses its HSM to decrypt and store the USAcnt. (R17) The DBS sends the result  (see Figure Ⅲ) of the device's remote unlocking service registration and its signature to RUApp. (R18) RUApp verifies the DBS's signature with the DevNonce and returns the result to LockSettingsApp. (R19) LockSettingsApp shows the result of the device registration to the user.

Figure Ⅱ. Data flow diagram of device unlocking phase

2) Device unlocking: Figure Ⅱ shows the DFD of unlocking the registered device. (U1) The user fails to unlock the device several times (say, forgets her passphrase). (U2) Keyguard checks the user consent to use the remote unlocking service through AccountApp and (U3) checks whether the remote unlocking service is activated through the DPM. If both conditions are satisfied, a throttling screen [18] displays a button to start the remote unlocking service. (U4) The user selects the button. (U5) KeyGuard calls RUApp. (U6) RUApp sends a payload (see Figure Ⅳ) including a fresh DevNonce to request (i) the RPTkn, and (ii) the WISSign (see Section Ⅳ.F.9) to the DBS through a TLS connection. (U7) The DBS requests a payload from the WIS. (U8) Using another machine, the user logs in to the WIS with her USAcnt. (U9) The WIS authenticates the user through the account server. (U10) The user selects the device currently waiting for remote unlocking. (U11) The WIS uses its HSM to sign her USAcnt with the WIS's timestamp (WISTimeStamp). (U12) The WIS sends the payload to the DBS securely. (U13) The DBS uses its HSM to complete the payload (see Figure Ⅳ). (U14) Then the DBS replies to the RUApp's request over the TLS connection. (U15) RUApp verifies the freshness of WISTimeStamp and the WIS signature with the USAcnt saved in AccountManager. Also, RUApp verifies the DevNonce and the DBS signature. (U16) If they are valid, RUApp decrypts the RPTkn and unlocks the device. If succeeded, the user can see the unlocked device. (U17) RUApp notifies the DBS of the device unlocking result over the TLS connection. (U18) The DBS notifies the WIS of the result. (U19) The user can also see the remote unlocking result from the WIS.

The device could send the data intended for the WIS directly to the WIS instead of passing through the DBS. But we design for the device to send the data through the DBS for the following benefits. First, it can simplify the channel device should have. A simplified communication channel can narrow the attack surface of the service. Second, this design can guarantee cooperation between DBS and WIS. Third, if the device connects DBS and WIS sequentially, it may increase the total round trip time. Because generally, Android device uses a wireless connection, but DBS and WIS are the servers with a high speed wired network.

Ⅳ. Implementation

This section covers the implementation of the remote unlocking service. 

A. Security Requirements

The security algorithms used by the remote unlocking service require sufficient security strengths. Thus, we follow the recommendations of the NIST [19].  Table Ⅰ shows the requirements of the cryptographic algorithms applied to the remote unlocking service. RUApp has the X.509 certificates from the DBS and the WIS as its raw assets. The certificates containing the public key can be changed through app updates. An RPTkn and a DevNonce are generated using the SecureRandom module of Java software development kit (SDK), which complies with FIPS 140-2 security requirements [20]. TLS 1.2 or higher is used for the communications between the RUApp and the DBS. The trust anchor of the server certificates must reach one of the root CA certificates stored in Android CredentialStorage.

Table Ⅰ. Security requirement details

B. Application Signing

RUApp needs the system privilege. Thus, we wrote the Android.mk build file for RUApp, which is to be signed with the Android platform key at the build time. In this way, the Android security features mentioned in Section Ⅱ.B, Section Ⅱ.C, and Section Ⅱ.D can be applied.

C. Hide Annotation

We add the hide annotation (@hide) to the DPM's remote unlocking service APIs to hide them from the SDK [21]. From Android 9 (API level 28), the APIs with the hide annotation can only be called by an app with system privileges [22]. Since RUApp is signed with the platform key, it can call the remote unlocking service APIs. In contrast, third-party apps are not allowed to call these APIs.

D. Call Stack Monitoring

This feature restricts other system privilege apps on the device from calling the remote unlocking service APIs. Thus, we can prevent unexpected internal attacks. Table Ⅱ shows the partial code that checks the call stack and blocks API calls by arbitrary system apps. If the caller is not specified in the API, a SecurityException is thrown. Therefore, the trust boundary is minimized.

Table Ⅱ. Code snippet of call stack monitoring

E. Custom Permission

We add custom permission to RUApp to regulate arbitrary accesses from third-party apps. Moreover, even system apps cannot access RUApp unless its custom permission is explicitly declared in their AndroidManifest.xml file. Thus, it can guarantee accountability. Table Ⅲ shows a partial code of the custom permission declared in AndroidManifest.xml of RUApp.

Table Ⅲ. Code snippet of custom permission in AndroidManifest.xml

F. Secure Protocol

TLS protects the communication between the RUApp and the DBS. On top of TLS, we add multi-layered security mechanisms to preserve the hardware-backed security level. Figures Ⅲ and Ⅳ show our secure protocol. The payload format is the JavaScript Object Notation (JSON) type, which consists of field-value pairs. Therefore, it can be flexibly expanded without the restriction of order and length. To represent all values as human-readable characters, we use Base64 encoding if necessary. Those human-readable characters make it easy to debug and respond to security incidents. Also, Base64 encoding is able to encode arbitrary binary data into a channel that is not "8-bit clean" (i.e., not any 8-bit character is allowed on the channel). The major fields in the payload are as follows.

Figure Ⅲ. Secure protocol in the device registration phase

1) Magic: Opening ports can be sensitive for server administrators. The DBS administrator opens only ports with security countermeasures such as network firewall and intrusion protection system (IPS). That is, the DBS may use the secure port for multiple purposes. This field value specifies that an arriving packet at the port of the DBS is for the remote unlocking service.

2) Version: This represents the remote unlocking service version known to the device. Depending on the update level of the device, the version of the remote unlocking service can vary. Also, new fields can be added as the version goes up. The DBS must be able to provide the service for the version the device knows. This field allows forward and backward compatibility to be achieved.

3) DevNonce: RUApp generates a new random value in the DevNonce field value every time it sends a request packet. The DBS signs the corresponding response, including this random value. When RUApp receives the response from the DBS, it verifies the signature DBSSign with the RSA public key of the DBS. RUApp keeps the DevNonce values generated in the current session. Thus, to prevent the replay attack, RUApp drops the response from the DBS if the DevNonce is not matched.

4) DBSAlias & WISAlias: This field serves as the index of the server's public/private key pairs. If the device has received the new certificate of the server and uses the new public key, this field value lets the server know which public key is used in the payload.

5) RsaEncrypted: This field is for an RSA ciphertext. Its plaintext may contain a CMD representing the device message (e.g., RPTkn request), DevId, AES encrypted RPTkn, and USAcnt.

6) ToWIS: This field is passed to the WIS by the DBS. It contains the WISAlias, which indicates the RSA public key of the WIS that the device uses. It also includes the RSA encrypted USAcnt in the registration phase. Since the USAcnt is encrypted with the public key of the WIS, the DBS cannot see the USAcnt of the device.

7) ToBeSigned: The response includes the device-issued DevNonce and the CMD containing the server message (e.g., RPTkn response). The AES encrypted RPTkn is also included when the user requests remote unlocking via the WIS.

8) DBSSign: This field has the signature for the values in the ToBeSigned field. This is generated using the DBS RSA private key. Since ToBeSigned includes DevNonce, every response has a different signature that defends against the replay attack.

9) FromWIS: The WIS passes this field to RUApp through the DBS. This field contains the WISTimeStamp and the signature WISSign, which proves the integrity of the USAcnt of the user whose authentication succeeds. WISSign is generated by signing the USAcnt concatenated by WISTimeStamp. Thus, the WISSign is different every time. Also, as the plaintext USAcnt is not included, the DBS cannot know the USAcnt of the device.

In the device registration phase, the secure protocol works in a single transaction as shown in Figure Ⅲ. However, in the device unlocking phase, the secure protocol requires server polling for synchronization as follows. The user calls RUApp on the throttling screen. According to the user agreement, the device enables its network connectivity. The device enters the remote unlocking standby state and requests a remote unlocking payload (the black arrows in Figure Ⅲ) at regular intervals to the DBS. Until the user makes an unlocking request via the WIS, the response using CMD from the DBS is "wait." (the grey arrow in Figure Ⅲ) [23].

Figure Ⅳ. Secure protocol in the device unlocking phase

Once the user request is valid at the WIS, it creates a FromWIS and sends it to the DBS. The DBS completes the payload (the green arrow in Figure Ⅳ) and sends it to RUApp. Then, RUApp tries unlocking the device and sends its result (the blue arrow in Figure Ⅳ) to the DBS. The DBS sends the received result to the WIS, which displays the unlocking result to the WIS user. The detailed operations are shown in Figure Ⅳ and Section Ⅲ.C.2.

Ⅳ. Evaluation


A. Threat Analysis

We adopt the STRIDE model to identify the threats the proposed unlocking service may have. The STRIDE model is a threat modeling method that is the most mature and helps identify relevant mitigating techniques [24]. The DFDs of the registration and unlocking phases are given to Microsoft's automatic tool for the STRIDE model analysis [25] (See [A.2]). As a result, 208 possible threats from our design are identified. Next, we assess the risk level of each threat based on the OWASP risk rating [26]. Table Ⅳ summarizes the result of the threat analysis and risk assessment. We publish the whole data in [A.3].

Table Ⅳ. Summary of the threat analysis and the risk assessment

B. Security Countermeasures

According to the result of our risk assessment as shown in [A.3], the high-level threats exist in the interactions R13, R17, U6, and U14 (see Figures Ⅰ and Ⅱ). These are in the communication channel between the RUApp and the DBS. The proposed secure protocol uses TLS, RSA, AES, and SHA256withRSA digital signature to defend against spoofing identities, tampering with data, repudiation, and information disclosure. For the medium-level threats, the device platform can be divided into a framework layer and an app layer. As to the potentially vulnerable interactions between apps, they are secured by using RUApp's Android custom permission. The DPM's remote unlocking service APIs restrict unauthorized access by leveraging application signing, hide annotation, and call-stack monitoring. To secure interactions R2 and U9, the account server utilizes OAuth 2.0. For the interaction U8, the WIS can lock the USAcnt in the case of multiple login failures to protect against the brute force attack [27]. As a result, our security design takes security countermeasures against all the high-level threats and most of the medium-level threats.

Ⅵ. Related work

As mentioned in section Ⅰ, this is the first paper that handles the Android SP. Utilizing the SP, we propose a new remote unlocking service over the current offline Android unlocking system. Also, we seek to preserve the current Android security level based on applying Android security features and inventing new security mechanisms. Thus, this paper doesn't open potential vulnerabilities in Android security. 

Android security has been enhanced as its version grows. Therefore, the previous security issues mentioned in related works may not works for now. Also, considering that well-known formula "likelihood x impact" in the risk assessment step of various threat modelings, the Android security issues in the related works can be assessed differently up to its cases. So, we overview the previous researches about Android security and compare them with our research briefly.

Hassan Khan et al. proposed an implicit authentication framework for Android [28]. Their study starts with the survey result that about 53% of Android users do not use the screen lock of the Android in 2013. Their research can improve the Android security for the users who do not use the screen lock. On the contrary, our study focuses on the users who set a passphrase for their Android devices.

Jie Huang et al. studied the privacy issue in the Android accessibility service [29]. The accessibility service is a valuable function that helps people with disabilities. But, some features of the Android accessibility service can be abused. Thus, they proposed a secure accessibility service. On the contrary, our study utilizes the DPM of android and focuses on the newly designed remote unlocking service.

Muhammad Shahzad et al. proposed a gesture-based Android unlocking mechanism [30]. They claim that the Android screen lock is vulnerable to shoulder surfing attacks and smudge attacks. Therefore, they invent a gesture-based Android unlocking mechanism that the attacker can see but can not quickly reproduce. Their study seems similar to our research in designing a new unlocking mechanism of the Android device, but our study doesn't focus on the shoulder surfing attacks and smudge attacks.

Sebastian Uellenbeck et al. research the vulnerability that Android pattern unlocking may have [31]. Their study statistically suggested that the existing 3 x 3 pattern unlocking doesn't provide sufficient entropy. Also, they proposed an improved pattern lock mechanism via changing pattern layout. On the contrary, our study doesn't focus on the current Android pattern unlocking.

Timothy J. Forman et al. also proposed a new Android pattern unlocking [32]. They invent Double Patterns (DPatts) to improve the entropy of the Android pattern unlocking. But, as mentioned, our study doesn't focus on the current Android pattern unlocking.

Muhammad Rehman Zafar et al. analyzed fingerprint authentication for smart devices [33]. Their research suggested more classified levels are needed in designing fingerprint authentication for security. On the contrary, our research does not focus on biometric authentication mechanisms.

Lukas Janik et al. invented a two-factor authentication that uses an additional simple game on existing Android pattern unlocking to improve the security level [34]. In the game, behavioral biometrics-based on touch screen interaction provides secondary authentication. On the contrary, our unlocking service does not rely on behavioral biometrics.

Fadi Aloul et al. proposed two-factor authentication that uses the OTP via SMS [35]. Due to the SMS that cannot be used while the device is locked, their mechanism seems unusable for unlocking devices. On the contrary, our proposed two-factor authentication scheme focuses on device unlocking.

Ammar H. Ali et al. designed an Android app to provide secure chatting [36]. Their design uses ECDH, AES, and RC4 ciphers. On the contrary, our design utilizes RSA, AES, and SHA256withRSA ciphers that meet the NIST recommendations.

Junsung Cho et al. opened a vulnerability on Android 5.1 (Lollipop) that an attacker can unlock the arbitrary Android device [37]. Their scheme uses Firebase push message to send an attack payload. Also, a Brute force attack is conducted on the victim's screen lock. But, their attacking scheme is expected to be outdated for now. Because the gatekeeper throttles the brute force attack targeting the screen lock. Also, FBE doesn't allow the Firebase push message until the device is unlocked.

Ⅶ. Conclusion

We presented a new Android remote unlocking service using the synthetic password. The proposed service can improve the user experiences while preserving the Android hardware-based security. Also, our design supports two-factor authentication, distributed authority, trust-boundary minimization, key management, and compatibility. We evaluated the security of the proposed remote unlocking service through the STRIDE model and the OWASP risk rating. We identified 208 threats and assessed each threat's risk level using public tools. We added the corresponding countermeasures to the proposed unlocking service against all the identified high-level threats. The developed remote unlocking service has been installed on commercial devices after passing quality verification and penetration tests.

Footnote & Reference

[1] IEEE Secure Development Conference (SecDev) 2021:
https://secdev.ieee.org/2021/accepted/
[2] If you are unfamiliar with what a remote unlocking service is, we recommend watching the demo video (1min 17sec long) in [A.1] first.
[3] If the factory reset protection (FRP) feature to prevent the use of stolen devices is activated, the user must also unlock the FRP to reuse the device after factory-resetting.
[4] Google, “Android file-based encryption.”:
https://source.android.google.cn/security/encryption/file-based
[5] Google, “Android authentication.”:
https://source.android.com/security/authentication
[6] A typical example is a device that a company distributes to an employee. The owner of the device is the company (or administrator), but the user is the employee.
[7] Qualcomm, “File based encryption.”:
https://www.qualcomm.com/media/documents/files/file-based-encryption.pdf
[8] RPTkn is also called the escrow token in the Android framework's LockSettingService sourcecode of the AOSP and other documents.
[9] Google, “Android application sandbox.”:
https://source.android.com/security/app-sandbox
[10] Google, “Application signing.”:
https://source.android.com/security/apksigning
[11] Google, “Permissions on android.” :
https://developer.android.com/guide/topics/permissions
[12] Google, “Android keystore system.”:
https://developer.android.com/training/articles/keystore
[13] Google, “Hardware-backed keystore.”:
https://source.android.com/security/keystore
[14] In this paper, we use the expressions of manufacturer, service provider, and server administrator interchangeably in context.
[15] The platform key is a term of a private key of the manufacturer in Android.
[16] If the user already saved her USAcnt in the device, R1 ~ R3 can be skipped. In addition, the USAcnt can be saved via the Settings app.
[17] If the user fails to input the correct passphrase at this time, the device registration is canceled. By this, a malicious attacker cannot arbitrarily activate the remote unlocking service.
[18] This is a screen that KeyGuard temporarily restricts the passphrase input to prevent the brute force attack.
[19] NIST, “Sp 800-57 part 1 rev. 5 recommendation for key management: Part 1 – general.”:
https://doi.org/10.6028/NIST.SP.800-57pt1r5
[20] Google, “Secure random.”:
https://developer.android.com/reference/java/security/SecureRandom
[21] Google, “Hide annotation.”:
https://source.android.com/devices/architecture/aidl/aidl-annotations#hide
[22] Google, “Restrictions on non-sdk interfaces.”:
https://developer.android.com/guide/app-compatibility/restrictions-non-sdk-interfaces
[23] If the device's polling continues forever, the user's network resource could be maliciously exhausted. Thus, we define the maximum standby duration as 5 minutes. After the maximum time has elapsed, the device standby state is canceled. The user can restart the remote unlocking manually. The interval and the threshold also help the DBS to be protected against the DoS attack.
[24] N. Shevchenko, “Threat modeling: 12 available methods.” Carnegie Mellon University’s Software Engineering Institute Blog, Dec. 3, 2018:
[26] OWASP, “Owasp risk rating methodology.”:
https://owasp-risk-rating.com
[27] The user can unlock her USAcnt via email authentication.
[28] H. Khan, A. Atwater, and U. Hengartner, “Itus: an implicit authentication framework for android,” in Proceedings of the 20th annual international conference on Mobile computing and networking, pp. 507–518, 2014
[29] J. Huang, M. Backes, and S. Bugiel, “A11y and privacy don’t have to be mutually exclusive: Constraining accessibility service misuse on android,” in 30th USENIX Security Symposium (USENIX Security 21), pp. 3631–3648, USENIX Association, Aug. 2021
[30] M. Shahzad, A. X. Liu, and A. Samuel, “Secure unlocking of mobile touch screen devices by simple gestures: You can see it but you can not do it,” in Proceedings of the 19th annual international conference on Mobile computing & networking, pp. 39–50, 2013
[31] S. Uellenbeck, M. Dürmuth, C. Wolf, and T. Holz, “Quantifying the security of graphical passwords: The case of android unlock patterns,” in Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pp. 161–172, 2013
[32] T. Forman and A. Aviv, “Double patterns: A usable solution to increase the security of android unlock patterns,” in Annual Computer Security Applications Conference, pp. 219–233, 2020
[33] M. R. Zafar and M. A. Shah, “Fingerprint authentication and security risks in smart devices,” in 2016 22nd International Conference on Automation and Computing (ICAC), pp. 548–553, IEEE, 2016.
[34] L. Janik, D. Chuda, and K. Burda, “Sgfa: A two-factor smartphone authentication mechanism using touch behavioral biometrics,” in Proceedings of the 21st International Conference on Computer Systems and Technologies’ 20, pp. 35–42, 2020
[35] F. Aloul, S. Zahidi, and W. El-Hajj, “Two factor authentication using mobile phones,” in 2009 IEEE/ACS International Conference on Computer Systems and Applications, pp. 641–644, IEEE, 2009
[36] A. H. Ali and A. M. Sagheer, “Design of an android application for secure chatting.,” International Journal of Computer Network & Information Security, vol. 9, no. 2, 2017
[37] J. Cho, G. Cho, S. Hyun, and H. Kim, “Open sesame! design and implementation of backdoor to secretly unlock android devices.,” J. Internet Serv. Inf. Secur., vol. 7, no. 4, pp. 35–44, 2017

Appendices

2021년 7월 14일 수요일

Qiskit tutorial - 5. Operators

작성중입니다.

이 글은 Qiskit 공식 홈페이지에서 제공하는 튜토리얼을 직접 해보고 요약하거나 덧붙이거나 교정한 글입니다. 원문은 [1]이며, Anaconda 의 Jupyter notebook 을 사용하는 원문과 달리 순수 Python 으로 실행가능하도록 소스코드를 수정하고, 중간마다 양자 상태를 시각화하는 코드 등이 추가되어 코드도 원문과 차이가 있습니다. 제가 작성한 코드는 [2]에 공개합니다.

기본 import 들은 다음과 같다.

코드5.1. 기본 import 문

5.1. Operator 클래스

Qiskit의 Operator 클래스는 양자 시스템에 작용하는 행렬 연산자를 나타내는 데 사용된다. 이 클래스는 텐서곱을 이용한 다중 결합 연산자를 만들거나 연산자를 작성하는데 필요한 다양한 매서드를 포함한다.

5.1.1. Operator 생성

Operator 객체를 만드는 가장 쉬운 방법은 리스트나 Numpy 배열로 주어진 행렬로 연산자를 초기화하는 것이다. 예를 들면 두 큐비트 Pauli-XX 연산자는 다음과 같이 만들 수 있다.

코드5.2. XX-게이트 연산자 구현

코드 15번의 출력은 다음과 같다.

Operator([[0.+0.j, 0.+0.j, 0.+0.j, 1.+0.j],
          [0.+0.j, 0.+0.j, 1.+0.j, 0.+0.j],
          [0.+0.j, 1.+0.j, 0.+0.j, 0.+0.j],
          [1.+0.j, 0.+0.j, 0.+0.j, 0.+0.j]],
         input_dims=(2, 2), output_dims=(2, 2))

5.1.2. Operator의 속성

Operator 객체는 행렬과 서브시스템들의 입력 및 출력 차원을 포함한다.

  • data: 기반이 되는 Numpy 배열에 접근할 때 사용한다. 
  • dims: 연산자의 전체 입력과 출력의 차원을 반환할 때 사용한다. 이 출력은 (input_dim, output_dim)의 튜플을 반환한다.(주의. 기반 행렬의 모양과 순서가 반대다.)

코드는 다음과 같다.

코드5.3. 행렬과 차원의 출력

코드 18번 라인의 출력은 다음과 같다. 

[[0.+0.j 0.+0.j 0.+0.j 1.+0.j]
 [0.+0.j 0.+0.j 1.+0.j 0.+0.j]
 [0.+0.j 1.+0.j 0.+0.j 0.+0.j]
 [1.+0.j 0.+0.j 0.+0.j 0.+0.j]]

코드 21번 라인의 출력은 다음과 같다.

4 4

5.1.3. 입력과 출력의 차원

Operator 클래스는 서브시스템의 차원을 추적하기 때문에 다중결합 연산자를 작성하는 데 사용할 수 있다. 이 값은 input_dims 와 output_dims 함수를 이용하여 접근할 수 있다.

연산자의 행이 2N개이고, 열이 2M개이면 입력과 출력 차원이 자동으로 M-큐비트와 N-큐비트로 가정된다.

코드5.4. 차원 출력

코드 25~26번 라인의 출력은 다음과 같다.

Input dimensions :  (2, 2)
Output dimensions :  (2,)

입력된 행렬을 서브시스템으로 나눌 수 없는 경우 단일 연산자로 지정된다. 예를 들어 입력된 행렬이 6 x 6 행렬이면 다음과 같이 입력과 출력 행렬은 모두 6행이다.

코드5.5. 6 x 6 행렬 연산자의 입력 출력 차원

코드 29~30번 라인의 출력은 다음과 같다.

Input dimensions:  (6,)
Output dimensions:  (6,)

입력과 출력의 차원은 새 연산자를 초기화할 때 수동으로 명시할 수 있다.

코드5.6. 연산자의 입력 출력 차원 명시

코드 34, 35번 라인과 39, 40번 라인의 출력은 다음과 같다.

Input dimensions:  (4,)
Output dimensions:  (2,)
Input dimensions:  (2, 3)
Output dimensions:  (2, 3)

또한 input_dims() 와 output_dims() 를 사용하여 일부 서브시스템의 입력 혹은 출력의 차원만 추출할 수 있다.

코드5.7. 서브시스템의 차원 출력

코드 42, 43번 라인의 출력은 다음과 같다.

Dimension of input system 0: (2,)
Dimension of input system 1: (3,)

5.2. 클래스를 연산자로 변환

키스킷에서 사용하는 다음 클래스들은 연산자 초기화 메소드를 이용하여 Operator 객체로 바로 변환 가능하다. 

  • Pauli 객체
  • Gate 와 Instruction 객체
  • QuantumCircuits 객체

마지막 객체는 시뮬레이터 백엔드를 호출하지 않고 양자 회로에 대한 최종 유니타리 행렬을 계산하기 위해 Operator 클래스를 유니타리 시뮬레이터로 사용할 수 있다는 것을 의미한다. 회로에 지원되지 않는 연산이 포함되어 있으면 예외가 발생한다. 지원되지 않는 연산들은 측정, 재설정, 조건부 연산, 또는 '게이트를 행렬로 정의할 때 행렬 정의나 분해가 존재하지 않는 게이트'들이다. 구현은 다음과 같다.

코드5.8. 클래스를 Operator 객체로 변환 구현

코드 49번 라인의 출력은 다음과 같다.

Operator([[0.+0.j, 0.+0.j, 0.+0.j, 1.+0.j],
          [0.+0.j, 0.+0.j, 1.+0.j, 0.+0.j],
          [0.+0.j, 1.+0.j, 0.+0.j, 0.+0.j],
          [1.+0.j, 0.+0.j, 0.+0.j, 0.+0.j]],
         input_dims=(2, 2), output_dims=(2, 2))

코드 52번 라인의 출력은 다음과 같다.

Operator([[1.+0.j, 0.+0.j, 0.+0.j, 0.+0.j],
          [0.+0.j, 0.+0.j, 0.+0.j, 1.+0.j],
          [0.+0.j, 0.+0.j, 1.+0.j, 0.+0.j],
          [0.+0.j, 1.+0.j, 0.+0.j, 0.+0.j]],
         input_dims=(2, 2), output_dims=(2, 2))

코드 64번 라인의 출력은 다음과 같다.

Operator([[ 0.70710678+0.j,  0.70710678+0.j,  0.        +0.j, ...,
            0.        +0.j,  0.        +0.j,  0.        +0.j],
          [ 0.        +0.j,  0.        +0.j,  0.70710678+0.j, ...,
            0.        +0.j,  0.        +0.j,  0.        +0.j],
          [ 0.        +0.j,  0.        +0.j,  0.        +0.j, ...,
            0.        +0.j,  0.        +0.j,  0.        +0.j],
          ...,
          [ 0.        +0.j,  0.        +0.j,  0.        +0.j, ...,
            0.        +0.j,  0.        +0.j,  0.        +0.j],
          [ 0.        +0.j,  0.        +0.j,  0.70710678+0.j, ...,
            0.        +0.j,  0.        +0.j,  0.        +0.j],
          [ 0.70710678+0.j, -0.70710678+0.j,  0.        +0.j, ...,
            0.        +0.j,  0.        +0.j,  0.        +0.j]],
         input_dims=(2, 2, 2, 2, 2, 2, 2, 2, 2, 2), output_dims=(2, 2, 2, 2, 2, 2, 2, 2, 2, 2))

5.3. 회로에서 연산자 사용

유니타리인 Operator 객체는 QuantumCircuit.append() 를 이용하여 QuantumCircuit 객체에 바로 넣을 수 있다. 이는 Operator 객체를 회로에 추가할 수 있는 UnitaryGate 객체로 바꿔준다. 만약 연산자가 유니타리가 아니면 예외처리된다. 객체의 유니타리 여부는 Operator.is_unitary() 를 사용하여 확인할 수 있다. 만약 연산자가 유니타리이면 True, 아니면 False 를 반환한다. 구현은 다음과 같다.

코드5.9. 회로에서 연산자 사용 구현

코드 76번 라인의 출력은 다음과 같다.

그림5.1. Operator 객체를 이용한 회로 도식

5.4. 연산자 결합

연산자들은 다양한 방법으로 결합될 수 있다.

5.4.1. 텐서곱




2021년 7월 13일 화요일

Qiskit tutorial - 4. Advanced Circuits

이 글은 Qiskit 공식 홈페이지에서 제공하는 튜토리얼을 직접 해보고 요약하거나 덧붙이거나 교정한 글입니다. 원문은 [1]이며, Anaconda 의 Jupyter notebook 을 사용하는 원문과 달리 순수 Python 으로 실행가능하도록 소스코드를 수정하고, 중간마다 양자 상태를 시각화하는 코드 등이 추가되어 코드도 원문과 차이가 있습니다. 제가 작성한 코드는 [2]에 공개합니다.

우선 기본 import 와 gate 선언은 다음과 같다.

코드4.1. 기본 import

4.1. 불투명한 게이트

임의의 게이트를 선언하고 큐비트에 적용할 수 있다. 코드는 다음과 같다.

코드4.2. 불투명 게이트 구현

코드 9번에서 게이트를 선언한다. 코드 10번에서 3-큐비트 레지스터를 선언하고 회로를 생성한다. 코드 12번과 13번 라인에서 두 큐비트 게이트를 적용하고 14번 라인에서 도식한다. 15번 라인의 출력은 다음과 같다. 

그림4.1. 불투명 게이트 도식

4.2. 합성 게이트

하위 회로를 합성하여 게이트 연산을 합성할 수 있다. 구현 코드는 다음과 같다.

코드4.3 합성 게이트 구현

코드 20번에서 2-큐비트 레지스터를 선언하고, 코드 21번 라인에서 이 양자 레지스터를 가진 회로 sub_circ을 생성한다. 코드 29번 라인에서 sub_circ 회로는 하위 로직으로 변경된다. 코드 31번에서는 다른 회로를 선언하고, 36번에서 이 회로에 sub_inst 를 붙인다. 코드 38번의 출력은 다음과 같다.

그림4.2. 하위 회로를 붙인 회로의 도식

코드 29번에서 회로가 to_instruction() 에 의해 바로 분해되지는 않으며, 이는 회로 설계를 더 고차원의 추상화 단계에서 가능하게 한다. 임의로 지정된 순간 또는 컴파일 전에 하위 회로들은 decompose() 에 의해 분해된다. 코드 42번의 출력은 다음과 같다.

그림4.3. 하위 회로를 분해한 회로의 도식

4.3. 매개변수화된 회로

매개변수화된 회로의 구현은 다음과 같다.

코드4.4. 매개변수를 가진 회로 구현

코드 47번에서 매개변수 theta 를 선언한다. 코드 49번 라인에서 5개의 큐비트와 1개의 전통적인 비트를 갖는 회로를 생성한다. 코드 50번 라인에서 0번 큐비트에 하다마드 게이트를 적용한다. 코드 51번의 반복문은 5개의 큐비트를 CX 게이트로 순차적으로 얽힘 상태로 만든다. 코드 54번부터, 두 개의 배리어 사이에서 매개변수 theta를 이용하여 Z축 표준회전 게이트인 RZ 게이트를 큐비트들에 적용한다. 코드 58~59번 라인에서 CX 게이트를 역순으로 추가하고, 코드 60번 라인에서 큐비트 0 에 다시 하다마드 게이트를 적용한다. 코드 61번에서 큐비트 0의 값을 측정하여 전통적인 비트에 기록한다. 코드 63번 라인에서 회로를 도식하고 64번 라인에서 출력한다. 결과는 다음과 같다.

그림4.4. 매개변수를 가진 회로 도식

코드 66번에서 회로의 매개변수를 출력한다. 결과는 다음과 같다.

ParameterView([Parameter(θ)])

4.3.1 매개변수를 실제 값에 연결하기

모든 회로의 매개변수는 회로를 백엔드로 보내기 전에 값을 연결해야 한다. 이 작업은 다음의 두 가지 방법 중 하나로 수행 가능하다. bind_parameters() 는 Parameter 에 값을 할당하는 딕셔너리를 받아 각각의 해당하는 매개변수가 그에 알맞는 값으로 바뀐 새로운 회로를 되돌려준다. 부분적인 값 지정도 지원되는 데, 이 경우 반환된 회로는 특정 값에 연결되지 않은 Parameter 들로 매개변수가 지정된다. 예제 코드의 구현은 다음과 같다.

코드4.5. 매개변수의 연결 구현

코드 70번 라인에서 theta_range는 0 ~ 2π 까지의 선형값을 128단계로 나누어 갖는다. 이 값들을 매개변수 theta 에 연결한다. 반복문이 종료된 마지막 회로를 코드 73번 라인에서 도식하고, 74번 라인에서 출력하면 다음과 같다.

그림4.5. 매개변수 Θ에 2π가 연결된 회로의 도식 

코드 76번 라인에서 execute()는 parameter_binds 에 할당되는 인자들을 받아들이며, Parameter 들을 해당 value 에 할당하는 딕셔너리들로 구성된 리스트가 지정된 경우, 그 리스트에 들어 있는 모든 딕셔너리들을 각각 회로에 적용하고 벡엔드에서 실행한다. 

예제 회로에서 RZ(θ) 회전을 5 큐비트 얽힘 상태에 적용하였으므로, 큐비트 0에서 5θ의 진동을 관찰할 수 있다. 코드 92번 라인의 출력은 다음과 같다.

그림4.6. 큐비트0의 측정 결과 도식

4.3.2 컴파일 비용 줄이기

특정 경우, 값의 연결 전에 매개변수화된 회로를 컴파일하면, 연결된 회로의 집합을 컴파일하는 것보다 컴파일 시간을 상당히 줄일 수 있다. 구현 코드는 다음과 같다.

코드4.6. 회로 컴파일 시간 비교 구현

코드 102 ~ 116번 라인에서, θ 를 0 ~ 2π 까지 32등분한 값들인 theta_range를 이용하여 양자 회로들을 생성하고 qcs 에 할당한다. 이후 qcs 리스트의 회로들을 컴파일하고 소요된 시간을 122번 라인에서 출력한다. 반대로, 코드 125 ~ 137번 라인은 매개변수화된 양자 회로를 135번 라인에서 컴파일하고, 136번 라인에서 매개변수들을 theta_range 에 할당한다. 이후 소요 시간을 139번 라인에서 출력한다. 두 출력 결과는 다음과 같다.

Time compiling over set of bound circuits :  4.91303277015686
Time compiling over parameterized circuit, then binding :  0.6330001354217529

4.3.3 합성(Composition)

매개변수화된 회로는 일반적인 QuantumCircuit 처럼 구성될 수 있다. 보통 두 매개변수화된 회로를 구성할 때, 출력 회로는 입력 회로의 매개변수들의 결합에 의해 매개변수화된다. 그러나 매개변수의 이름은 회로에서 고유해야한다. 회로에 이미 존재하는 이름을 가진 매개변수를 추가하려고 시도할 때, 만약 출처(source)와 대상(target)이 같은 Parameter 인스턴스를 공유하면, 매개변수들은 동일한 것으로 간주되어 결합된다. 만약 출처와 대상이 다른 Parameter 인스턴스를 가지면 에러가 발생한다. 예제 코드는 다음과 같다.

코드4.7. 회로 합성 구현

코드 142번 라인에서 phi 라는 이름의 Parameter 인스턴스를 생성한다. 144~150번 라인에서 두개의 2-큐비트 회로를 생성하고 각각 sc_1 과 sc_2로 명명한다. 152번 라인에서 4-큐비트 회로를 생성하고, 153번 라인에서 회로의 큐비트에 접근할 수 있는 변수 qr 을 만든다. 155~158번 라인에서 기생성한 2-큐비트 회로들을 하위회로로 이용하여 4-큐비트 회로를 구성한다. 코드 160번 라인에서 양자회로를 도식하고, 161번 라인에서 출력한다. 출력 결과는 다음과 같다.

그림4.7. 매개변수화된 회로 합성 결과

하위 회로에 다른 매개변수를 추가하기 위해 to_instruction() 은 추가 전달인자로  parameter_map 을 가질 수 있다. 이 것이 설정된 경우 출처의 매개변수들이 새로운 매개변수들로 치환된 명령어들을 생성한다. 구현은 다음과 같다.

코드4.8. 합성된 회로의 매개변수 변경 구현

코드 166번 라인에서 생성한 회로는 매개변수 p 를 포함하고 있다. 코드 173~175번 라인에서 새로운 매개변수들을 선언한다. 코드 177~178번 라인에서 9-큐비트 회로를 선언하고, 코드 179~181 라인에서 3-큐비트 회로를 합성하여 9-큐비트 회로를 구성한다. 이 때, to_instruction() 에 인자로 매개변수 p 를 각각 theta, phi, gamma 로 교체한다. 코드 184번에서 이 회로의 도식을 출력하면 다음과 같다. 

그림4.8. 합성 회로의 매개변수 변경

[1] 원문: 
https://qiskit.org/documentation/tutorials/circuits_advanced/01_advanced_circuits.html
[2] 내 코드:
https://github.com/sungmin-net/python-qiskit-tutorials/blob/main/tutorial04_AdvancedCircuits.py

2021년 6월 23일 수요일

Qiskit tutorial - 3. Summary of Quantum Operators

이 글은 Qiskit 공식 홈페이지에서 제공하는 튜토리얼을 직접 해보고 요약하거나 덧붙이거나 교정한 글입니다. 원문은 [1]이며, Anaconda 의 Jupyter notebook 을 사용하는 원문과 달리 순수 Python 으로 실행가능하도록 소스코드를 수정하고, 중간마다 양자 상태를 시각화하는 코드 등이 추가되어 코드도 원문과 차이가 있습니다. 제가 작성한 코드는 [2]에 공개합니다.

이 단원에서는 Qiskit Terra 에서 이용 가능한 여러가지 연산들에 대하여 다룬다. 목록은 다음과 같다.

  • 단일 큐비트 양자 게이트
  • 다중 큐비트 양자 게이트
  • 측정
  • 초기화 (Reset)
  • 조건
  • 상태 초기화

또한 세 가지 종류의 시뮬레이터를 사용하는 방법도 설명한다.

  • unitary_simulator
  • qsam_simulator
  • statevector_simulator

우선 다음의 기본 import 와 백엔드 선언으로 코드를 시작한다.


코드3.1. 기본 import 와 백엔드 선언

3.1. 단일 큐비트 양자 상태

단일 큐비트 양자 상태는 다음과 같이 기술할 수 있다.

|ψ〉 = α |0〉 + β |1〉

여기서 α 와 β 는 복소수이다. 측정에서 큐비트가 |0〉에 있을 확률은 |α|² 이고, |1〉일 확률은 |β|² 이다. 백터를 행렬로 표현하면 아래와 같다.

확률의 보존으로 인해 |α|² + |β|² = 1 이며, 전역 위상이 감지되지 않는 |ψ〉 := e |ψ〉이므로, 단일 큐비트 양자 상태를 설명하기 위해 두 개의 실수만 필요하다. 전역 위상이 Φ 와 θ 일 때 다음과 같이 나타낼 수 있다.

|ψ〉 = cos(θ/2) |0〉 + sin(θ/2) e |1〉

여기에서 0 ≤ Φ ≤ 2π 이고, 0 ≤ θ ≤ π 이다. 물론 큐비프 상태(C²) 와 단위 구 표면의 점(R³)은 일대일로 대응된다. 이를 큐비트 상태의 블로흐 구체 표현이라고 한다.

양자 게이트 / 연산은 일반적으로 행렬로 표현한다. 특히 큐비트에 작용하는 게이트는 2 x 2 유니타리 행렬 U 로 표현된다. 그리고 양자 게이트의 작용은 양자 상태를 나타내는 벡터에 게이트를 나타내는 행렬을 곱함으로써 알 수 있다.

|ψ‘〉 = U |ψ〉

일반적으로 유니타리 상태에서는 |0〉을 위의 상태로만들 수 있어야 한다. 따라서 U는 다음과 같다.

여기에서 a와 b는 임의로 주어진 0 ≤ θ ≤ π 와 0 ≤ Φ ≤ 2π 에 대해 UU = I 를 만족하는 복소수이다. (여기에서 † 는 영어로 '대거(dagger)' 라고 읽는다. 우리말로는 '칼표' 라고 부른다. U 는 행렬 U 의 i 행 j 열 위치의 원소를 j 행 i 열로 이동(전치)시키고, 복소수 i 들의 ± 부호를 뒤집어서(켤레) 만든 행렬이다. 자세한 내용은 위키[3] 참고) 또, 0 ≤ λ ≤ 2π 일 때, a → -e sin(θ/2) 와 b → eiλ+iΦ cos(θ/2) 인 세 가지 제약조건을 준다. 따라서 다음과 같다.

이는 단일 큐비트에 작용되는 유니타리의 가장 일반적인 형태이다.

3.2. 단일 큐비트 게이트들

사용할 수 있는 단일 큐비트 게이트는 U게이트들, 항등(Identity) 게이트, 파울리(Pauli) 게이트, 클리포드(Clifford) 게이트, C3 게이트, 표준 회전(Standard rotation) 게이트이다. 키스킷은 유니타리 행렬들을 계산할 수 있는 unitary_simulator 백엔드를 제공한다.

다음의 코드로 단일 큐비트 회로를 생성하고, 초기 상태를 살펴본다.

코드3.1. 단일 큐비트 회로 생성 및 큐비트 상태 출력

그림3.1. 단일 큐비트 회로 상태 출력 결과(코드 21번 라인)

3.2.1. U 게이트들

3.2.1.1. U3 게이트

Qiskit 에서는 일반적인 유니타리 연산을 사용할 수 있도록 u3 게이트를 제공한다.

u3(θ, Φ, λ) = U(θ, Φ, λ)

코드3.2. u3 게이트 적용

그림3.2. u3 게이트 적용 회로 도식(코드 29번 라인)

그림3.3. u3 게이트 적용 큐비트 도식(코드 32번 라인)

코드 35번 라인에서 유니타리 행렬을 출력한 결과는 다음과 같다.

[[ 0.707+0.j    -0.-0.707j]
[ 0.+0.707j    -0.707+0.j]]

위 출력 결과에서 j는 python의 복소수 i 표기이며, 0.707은 1/√2의 근사값이다. 즉, 다음의 행렬이다.

3.2.1.2. U2 게이트

u2 게이트는 u3 게이트로 u2(Φ, λ) =u3(π/2, Φ, λ)이며, 다음의 행렬로도 표현된다.

이것은 우리가 중첩을 만들 수 있게 해주는 유용한 게이트이다.

코드3.3. u2 게이트 적용 회로

그림3.4 u2 게이트 적용 회로 도식(코드 42번 라인)

그림3.5. u2 게이트 적용 큐비트 상태 도식

코드 48번에서 유니타리 행렬을 출력한 결과는 다음과 같다.

[[ 0.707+0.j    -0.-0.707j]
 [ 0.+0.707j    -0.707+0.j]]

3.2.1.3. U1 게이트

u1 게이트는 u3 게이트로 표현하면 u1(λ) = u3(0, 0, λ)이며, 행렬로는 다음과 같다.

이 게이트는 양자 위상을 만들어주므로 유용하다.

코드3.4.  u1 게이트 적용 회로 생성

그림3.6. u1게이트 적용 회로 도식(코드 52번 라인)

그림3.7. u1게이트 적용 큐비트 상태 도식(코드 56번 라인)

u1게이트는 파동의 위상만 변경하여, 단일 큐비트의 상태벡터에는 영향을 미치지 않는다. 코드 59번 라인의 실행 결과는 다음과 같다.

[[1.+0.j 0.+0.j]
 [0.+0.j 0.+1.j]]

3.2.2. 항등(Identity) 게이트

항등 게이트는 Id는 u0(1) 과 같다. 즉, Id = u(0).

코드3.5. 항등 게이트 생성 코드

그림3.9. 항등 게이트 회로 도식(코드 66번 라인)

그림3.10. 항등 게이트 적용 큐비트 상태 도식(코드 69번 라인)

항등 게이트는 큐비트의 상태 벡터에 영향을 주지 않는다. 코드 71번 라인의 출력 결과는 다음과 같다.

[[1.+0.j 0.+0.j]
 [0.+0.j 1.+0.j]]

3.2.3. 파울리(Pauli) 게이트들

3.2.3.1. X 게이트

비트 플립 게이트이며, 다음의 수식과 같이 정의된다.

Qiskit 구현은 다음과 같다.

코드3.6. X 게이트 구현

코드 80번 라인을 통해 회로를 출력하면 다음과 같다.

그림3.11. X 게이트 회로 도식

코드 83번 라인으로 큐비트의 상태벡터를 도식하면 다음과 같이 비트가 플립된다.

그림3.12. 파울리-X 게이트 적용 결과 도식

코드 86번 라인의 결과는 앞의 수식과 동일하다. 

[[0.+0.j 1.+0.j]
 [1.+0.j 0.+0.j]]

3.2.3.2. Y 게이트

비트와 위상을 플립하는 게이트이며, 다음의 수식으로 정의된다.

회로의 구현은 다음과 같다.

코드3.7. Y게이트 회로 구현

코드 92번 라인의 결과로 아래와 같이 출력된다.

그림3.13. Y게이트 도식

코드 95번 라인의 결과로 아래와 같이 블로흐 구에서 비트가 플립된 것을 볼 수 있다.

그림3.14. Y게이트 적용 결과 도식

코드 98번 라인의 결과는 상기 수식과 동일하다.

[[ 0.+0.j -0.-1.j]
 [ 0.+1.j  0.+0.j]]

3.2.3.3. Z 게이트

위상 플립 게이트 Z는 다음의 수식으로 정의된다.

Z 게이트의 회로는 다음과 같이 구현할 수 있다.

코드3.8. Z 게이트 회로 구현

코드 105번 라인의 결과는 다음과 같다.

그림3.16. Z 게이트 회로 도식

코드 108번 라인은 다음의 블로흐 구를 도식한다. 위상만 변경되어 비트는 유지된다.

그림3.17. Z 게이트 적용 후 큐비트 상태벡터 도식

코드 111번 라인의 결과는 앞의 수식과 같다.

[[ 1.+0.j  0.+0.j]
 [ 0.+0.j -1.+0.j]]

3.2.4. 클리포드(Clifford) 게이트들

3.2.4.1. 하마다드(Hadamard) 게이트

이 게이트는 단일 큐비트를 0과 1의 중첩 상태로 만든다. 수식은 다음과 같다.

회로의 구현은 다음과 같다.

코드3.9. 하다마드 게이트 회로 구현

코드 118번 라인의 출력 결과는 다음과 같다.

그림3.18. 하다마드 게이트 도식

코드 121번 라인의 출력 결과는 다음과 같다.

그림3.19. 하다마드 게이트 적용 후 상태벡터 도식

코드 124번의 출력 결과는 다음과 같다. 수식과 동일함을 알 수 있다.

[[ 0.707+0.j  0.707-0.j]
 [ 0.707+0.j -0.707+0.j]]

3.2.4.2. S (또는 √Z 위상) 게이트

이 게이트는 양자 위상을 π/2 만큼 수정한다. 수식은 다음과 같다.

회로의 구현은 다음과 같다.

코드3.10. S 게이트 회로 구현

코드 130 라인의 출력은 다음과 같다.

그림3.19. S 게이트 회로 도식

코드 133번 라인의 출력은 다음과 같다.

그림3.20. S 게이트 상태 벡터 도식

코드136번 라인의 출력은 다음과 같다.

[[1.+0.j 0.+0.j]
 [0.+0.j 0.+1.j]]

3.2.4.2. S (또는 √Z 위상의 켤레) 게이트

수식은 다음과 같다.

회로의 구현은 다음과 같다.

코드3.11 S† 게이트 회로 구현

코드 143번 라인의 출력은 다음과 같다.

그림3.21. S† 게이트 회로 도식

코드 146번 라인의 출력은 다음과 같다.

그림3.22. S† 게이트 상태 벡터 도식

코드 149번 라인의 출력은 다음과 같다.

[[1.+0.j 0.+0.j]
 [0.+0.j 0.-1.j]]

3.2.5. C3 게이트들

3.2.5.1. T (또는 √S 위상) 게이트

수식은 다음과 같다.

구현은 다음과 같다.

코드3.12. T 게이트 회로 구현

코드 157번 라인의 출력은 다음과 같다.

그림3.23. T 게이트 회로 도식

코드 160번 라인의 출력은 다음과 같다.

그림3.24. T 게이트 회로의 상태벡터 도식

코드 163번 라인의 출력은 다음과 같다.

[[1.   +0.j    0.   +0.j   ]
 [0.   +0.j    0.707+0.707j]]

32.5.2. T (또는 √S 위상의 켤레) 게이트

수식은 다음과 같다.

양자 회로의 구현은 다음과 같다.

코드3.13. T dagger 게이트 구현

코드 169번 라인의 출력은 다음과 같다.

그림3.25. T† 게이트 회로 도식

코드 172번 라인의 출력은 다음과 같다.

그림3.26.  T† 게이트의 상태 벡터 도식

코드 176번 라인의 출력은 다음과 같다.

[[1.   +0.j    0.   +0.j   ]
 [0.   +0.j    0.707-0.707j]]

3.2.6. 표준 회전들

표준 회전 게이트들은 파울리 P = {X, Y, Z}에 대응하는 블로흐 벡터 축을 기준으로 하는 회전을 정의하는 게이트이다. 수식으로 다음과 같이 정의된다.

3.2.6.1. X축에 대한 회전 게이트

수식은 다음과 같다.

회로의 구현은 다음과 같다.

코드3.14. Rx 게이트 회로 구현

코드 184번 라인의 출력은 다음과 같다.

그림3.27. Rx 게이트 회로 도식

코드 187번 라인의 출력은 다음과 같다.

그림3.28. Rx 게이트 상태 벡터 도식

3.2.6.2. Y축에 대한 회전 게이트

수식은 다음과 같다.

회로의 구현은 다음과 같다.


코드3.15. Ry 게이트 회로 구현

코드 197번 라인의 출력은 다음과 같다.


그림3.29. Ry 게이트 회로 도식

코드 200번 라인의 출력은 다음과 같다.

그림3.30. Ry 게이트의 상태 벡터 도식

코드 203번 라인의 출력은 다음과 같다.

[[ 0.707+0.j -0.707+0.j]
 [ 0.707+0.j  0.707+0.j]]

3.2.6.3. Z축에 대한 회전 게이트

수식은 다음과 같다.

여기에서 전역 위상만 e-iΦ/2 만큼 차이난다는 의미에서 동치를 사용하였다. 구현은 다음과 같다.

코드3.16. Rz 게이트 회로 구현

코드 210번 라인의 출력은 다음과 같다.

그림3.31. Rz 게이트 회로 도식

코드 213번 라인의 출력은 다음과 같다.

그림3.32. Rz 게이트의 상태 벡터 도식

코드 216번 라인의 출력은 다음과 같다. 오직 전역 위상만 다르다.

[[0.707-0.707j 0.   +0.j   ]
 [0.   +0.j    0.707+0.707j]]

3.3. 다중 큐비트 게이트

3.3.1. 수학적 예비

양자 컴퓨터를 기술하는 공간의 차원은 큐비트의 개수가 증가함에 따라 지수적으로 증가한다. n 큐비트를 기술하는 복소 벡터 공간은 2ⁿ 차원을 가지기 때문이다. 다중 큐비트 시스템의 상태를 표현할 때는 텐서곱을 사용하여 연산자들이나 기저 벡터 사이를 붙여줄 수 있다.

우선 두 개의 큐비트들로 구성된 시스템을 생각해보자. 각 큐비트에서 작용하는 두 개의 연산자 A 와 B 가 주어졌을 때 두 개의 큐비트에 동시에 작용하는 연합 연산자 A⊗B 는 다음과 같다.

여기서 Ajk 와 Blm 은 각각 A 행렬과 B 행렬의 성분이다. 이와 유사하게, 두 큐비트 시스템의 기저 벡터들은 단일 큐비트의 기저 벡터들을 텐서곱하여 형성된다.

기저 벡터의 텐서곱 |0〉⊗|0〉는 |00〉로 간략하게 쓸 수 있다. n 큐비트 시스템의 상태는 단일 큐비트 기저 벡터들을 n 번 텐서곱하여 표현할 수 있다. 2큐비트 시스템의 기저 벡터의 차원은 4차원이며, n 큐비트 시스템의 기저 벡터의 차원은 2ⁿ임을 기억하자.

3.3.1.1. 키스킷에 사용되는 기저 벡터의 순서

물리학에서 다중 큐비트 시스템의 큐비트들을 나열할 때 대부분 첫 번째 큐비트를 텐서곱의 가장 왼쪽에 놓고, 마지막 큐비트를 가장 오른쪽에 놓는 순서를 따른다. 예를 들어, 첫 번째 큐비트의 상태가 |0〉이고, 두 번째 큐비트의 상태가 |1〉이면, 전체 상태는 |01〉이 된다. 키스킷은 조금 다른 순서로큐비트를 나열하는데 가장 중요한 비트(MSB)가 좌측에 있고, 가장 덜 중요한 비트(LSB)가 우측에 놓이는 big-endian 방식을 따른다. 이는 전통적인 컴퓨터에서 사용되는 비트열 표현과 비슷하며, 측정을 한 후에 문자열을 정수로 변환하는 과정을 쉽게 만든다. 앞선 예의 경우 전체 상태는 |10〉로 표현된다. 중요한 점은 이러한 다중 큐비트 상태의 표기법의 차이가 Qiskit 에서 표현되는 다중 큐비트 게이트를 나타내느 방법에 변화를 준다는 것이다. 다음을 살펴보자.

키스킷에서 사용하는 표현은 기저 벡터를 표현하는 숫자가 증가하는 순으로 번호를 매긴다. 예를 들어 두 큐비트 시스템의 기저 벡터들은 |00〉, |01〉, |10〉, |11〉 순으로 배열된다. 이때 기저 벡터에 대응하는 비트열을 살펴보면 각각 0, 1, 2, 3이 인코딩되어 있다.

3.3.1.2. 큐비트에 적용되는 제어 연산들

일반적인 다중 큐비트 게이트는 한 큐비트에 가하는 게이트나 다른 큐비트에 조건부로 작용하는 게이트와 그 응용을 모두 포함한다. 예를 들어 첫 번째 큐빗이 |0〉일 떄 두 번째 큐비트가 플립되는 게이트를 고려하자. 이러한 게이트는 제어 게이트들(controlled gates)로 알려져 있다. 표준 다중 큐비트 게이트는 두 큐비트 게이트와 세 큐비트 게이트로 구성되어 있는데 두 큐비트 게이트에는 제어 파울리 게이트들(controlled pauli gates), 제어 하다마드 게이트(controlled hadamard gate), 제어 회전 게이트들(controlled rotation gates), 제어 위상 게이트(controlled phase gate), 제어 u3 게이트(controlled u3 gate), 교환 게이트(swap gate)가 있으며, 세 큐비트 게이트에는 토폴리 게이트(Toffoli gate)와 프레드킨 게이트(또는 제어 교환 게이트, Fredkin gate or Controlled swap gate)가 있다. 

3.3.2. 두 큐비트 게이트들(Two-qubit gates)

Swap 게이트를 제외하면, 대부분의 두 큐비트 게이트들은 다른 큐비트에 의헤 제어되는 유형이다. 일반적으로 다른 큐비트에 의해 제어되는 두 큐비트 게이트 CU 는 첫 번째 큐비트의 상태가 |1〉일 때 단일 큐비트 유니타리 U를 두 번째 큐비트에 가하는 식이다. 유니타리 U 가 다음의 행렬이라고 가정하자.

이제 CU 가 어떻게 작용하는 지 다음과 같이 살펴볼 수 있다. 먼저 두 큐비트 시스템의 기저 벡터는 |00〉, |01〉, |10〉, |11〉 순으로 쓸 수 있다. 제어 큐비트는 큐비트 0 이라 가정하자. 키스킷 표기에 따르면 텐서곱 연산의 오른쪽에 해당한다. 만약 제어 큐비트가 |1〉 이면, U가 작용할 때 기저 벡터들은 다음과 같이 변환된다.

C를 행렬로 나타내면 다음과 같다. 

이러한 행렬 성분을 알아내려면,  CU의 작용을 먼저 계산하고 내적을 계산한다.

다음 예제에서 볼 수 있듯이, 이 연산은 키스킷에서 cu(q[0], q[1])로 구현되어 있다. 만약 큐비트1 이 제어 큐비트이고 큐비트0이 표적(target) 큐비트라면, 기저 벡터는 다음과 같이 변환된다.

이는 CU의 행렬 형태가 다음과 같음을 의미한다.

3.3.2.1. 제어 파울리 게이트들

3.3.2.1.1. 제어 반전 게이트(또는 제어 X 게이트 또는 제어 NOT 게이트)

제어 반전 게이트는 제어 큐비트의 상태가 |1〉일 때 표적 큐비트를 반전시킨다. 만약 cx(q[1], q[0])와 같이 제어 큐비트가 MSB 라면 그 행렬은 다음과 같다

반대로, cx(q[0], q[1])과 같이 제어 큐비트가 LSB이면 이 게이트는 다음 행렬과 동일하다.

회로의 구현은 다음과 같다.

코드3.17. CX게이트 회로 구현 

코드 229번 라인의 출력은 다음과 같다. (컴포저에서 CX게이트는 ⊗가 아니라 ⊕임에 유의하자.)

그림3.33. CX게이트 회로 도식

코드 232번 라인의 출력은 다음과 같다. 제어 큐비트가 |0〉이므로, 표적 큐비트에 영향이 없다.

그림3.34. CX 게이트 상태 벡터 도식

코드 234번 라인의 출력은 다음과 같다.

Controlled-X
 [[1.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 1.+0.j]
 [0.+0.j 0.+0.j 1.+0.j 0.+0.j]
 [0.+0.j 1.+0.j 0.+0.j 0.+0.j]]

코드 226번 라인의 주석을 풀어서, 제어 게이트를 |1〉 로 반전시키면, 코드 232번 라인의 상태 벡터는 다음과 같이 블로흐 구에 도식된다.

그림3.35. CX 게이트 상태 벡터 도식2

3.3.2.1.2. 제어 Y 게이트

제어 큐비트가 MSB이면, Y 게이트를 목표 큐비트에 적용한다. 이 때의 행렬식은 다음과 같다.

반대로, 제어 큐비트가 LSB이면 다음의 행렬식이 적용된다.

회로의 구현은 다음과 같다.

코드3.18. CY게이트 회로 구현

코드 242번 라인의 출력은 다음과 같다.

그림3.36. CY게이트 회로 도식

코드 245번 라인의 출력은 다음과 같다.

그림3.37. CY 게이트의 상태 벡터 도식

코드 248번 라인의 출력은 다음과 같다.

Controlled-Y
 [[1.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.-1.j]
 [0.+0.j 0.+0.j 1.+0.j 0.+0.j]
 [0.+0.j 0.+1.j 0.+0.j 0.+0.j]]

코드 239번 라인의 주석을 제거하면 코드 245번의 출력이 다음과 같이 바뀐다.

그림3.38. CY 게이트의 상태벡터 도식2

3.3.2.1.3. 위상 제어 게이트(또는 제어 Z 게이트 또는 위상 반전 게이트)

위상 반전 게이트는 제어 큐비트의 상태가 |1〉 일 때 표적 큐비트의 위상을 뒤집는다. 제어 큐비트가 MSB인 경우나 LSB인 경우에 상관없이 행렬은 같은 모양이다.

회로의 구현은 다음과 같다.

코드3.19. CZ 게이트 구현

코드 255번 라인의 출력은 다음과 같다.

그림3.39. CZ 게이트 회로 도식

코드 258번 라인의 출력은 다음과 같다.

그림3.40. CZ 게이트 상태 벡터 도식

코드 261번 라인의 출력은 다음과 같다.

Controlled-Z
 [[ 1.-0.j  0.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  1.-0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  1.-0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  0.+0.j -1.+0.j]]

코드 252번 라인에서 주석을 제거하면 코드 258번의 출력은 다음과 같다.

그림3.41. CZ 게이트 상태 벡터 도식2

3.3.2.2. 제어 하다마드 게이트(Controlled hadamard gate)

제어 큐비트가 |1〉이면 하다마드 게이트를 표적 큐비트에 적용한다. 다음 행렬은 제어 큐비트가 LSB인 경우이다.

이 회로의 구현은 다음과 같다.

코드3.20. CH게이트 구현 

코드 267번 라인의 출력은 다음과 같다.

그림3.42. CH 게이트 도식

코드 270번 라인의 출력은 다음과 같다. 

그림3.43. CH 게이트의 상태 벡터 도식

코드 273번 라인의 출력은 다음과 같다.

Controlled-Hadamard
 [[ 1.   +0.j  0.   +0.j  0.   +0.j  0.   +0.j]
 [ 0.   +0.j  0.707+0.j  0.   +0.j  0.707-0.j]
 [ 0.   +0.j  0.   +0.j  1.   -0.j  0.   +0.j]
 [ 0.   +0.j  0.707+0.j  0.   +0.j -0.707+0.j]]

제어 큐비트인 q[0]가 0이므로, 표적 큐비트[1]의 상태가 바뀌지 않는다. 코드 264번의 주석을 해제하여 제어 큐비트를 X게이트로 반전시키면, 다음의 상태 벡터를 볼 수 있다.

그림3.44. CH 게이트가 동작한 후 상태 벡터의 도식

3.3.2.3. 제어 회전 게이트들(Controlled rotation gates)

3.3.2.3.1. Z 축을 기준으로 한 회전 제어 게이트(Controlled rotation around z-axis)

LSB의 제어 큐비트가 |1〉이면, 표적 큐비트를 Z축을 중심으로 회전시킨다. 행렬식은 다음과 같다.

양자 회로의 구현은 다음과 같다.

코드3.21. CRZ 게이트 구현

코드 283번 라인의 출력은 다음과 같다.

그림3.45. CRZ 게이트 회로 도식

코드 286번 라인의 출력은 다음과 같다.

그림3.46. CRZ 게이트 상태 벡터 도식

코드 289번 라인의 출력은 다음과 같다.

Controlled-Rotation of Z axis
 [[1.   +0.j    0.   +0.j    0.   +0.j    0.   +0.j   ]
 [0.   +0.j    0.707-0.707j 0.   +0.j    0.   +0.j   ]
 [0.   +0.j    0.   +0.j    1.   +0.j    0.   +0.j   ]
 [0.   +0.j    0.   +0.j    0.   +0.j    0.707+0.707j]]

코드 280번 라인의 주석을 제거하면 코드 286번 라인의 블로흐 구가 다음과 같이 출력된다.

그림3.47. CRZ 게이트 상태 벡터 도식2

3.3.2.3.2. 제어 위상 회전 게이트(Controlled phase rotation)

두 큐비트가 모두 |11〉 상태에 있으면 위상 회전을 수행한다. 이 경우 제어 큐비트가 MSB나 LSB에 상관없이 다음의 행렬이 적용된다.

키스킷을 이용한 양자 회로의 구현은 다음과 같다.

코드3.22. CU1 게이트 회로 구현

코드 289번 라인의 출력은 다음과 같다.

그림3.48. CU1 게이트 회로 도식

코드 301번 라인의 출력은 다음과 같다.

그림3.49. CU1 게이트의 상태 벡터 도식

코드 304번 라인의 출력은 다음과 같다.

Controlled phase rotation
 [[1.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 1.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 1.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+1.j]]

코드 294번 라인의 주석을 해제하면, 코드 301번 라인의 출력은 다음과 같다.

그림3.50. CU1 게이트의 상태 벡터 도식2

3.3.2.3.3. 제어 u3 회전 게이트

제어 큐비트(코드에서는 LSB)의 상태가 1〉이면 표적 큐비트에 u3 회전을 수행한다. 행렬식은 다음과 같다.

양자 회로의 구현은 다음과 같다.

코드3.23. CU3 게이트 회로 구현

코드 312번 라인의 출력은 다음과 같다.

그림3.51. CU3 게이트 회로 도식

코드 315번 라인의 출력은 다음과 같다.

그림3.52. CU3 게이트 상태 벡터 도식

코드 318번 라인의 출력은 다음과 같다.

Controlled u3 rotation
 [[ 1.   +0.j     0.   +0.j     0.   +0.j     0.   +0.j   ]
 [ 0.   +0.j     0.707+0.j     0.   +0.j    -0.   -0.707j]
 [ 0.   +0.j     0.   +0.j     1.   +0.j     0.   +0.j   ]
 [ 0.   +0.j     0.   +0.707j  0.   +0.j    -0.707+0.j   ]]

코드 309번 라인의 주석을 제거하면 코드 315번 라인의 출력은 다음과 같다.

그림3.53. CU 게이트 상태벡터 도식2

3.3.2.4. 교환 게이트(Swap gate)

교환 게이트는 두 큐비트의 상태를 서로 바꾼다. 이는 기저 벡터를 다음과 같이 변환한다.

|00〉 → |00〉, |01〉 → |10〉, |10〉 → |01〉, |11〉 → |11〉

행렬식은 다음과 같다.

구현은 다음과 같다.

코드3.24. SWAP 게이트 회로 구현

코드 326번 라인의 출력은 다음과 같다.

그림3.54. SWAP 게이트 도식

코드 329번 라인의 출력은 다음과 같다.

그림3.55. SWAP 게이트 후 상태 벡터 도식

코드 332번 라인의 출력은 다음과 같다.

Swap
 [[1.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 1.+0.j 0.+0.j]
 [0.+0.j 1.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 1.+0.j]]

코드 323번 라인의 주석처리를 제거하면 코드 329번 라인의 출력은 다음과 같다.

그림3.56. SWAP 게이트 후 상태 벡터 도식2


3.3.3. 삼중 큐비트 게이트

널리 사용되는 두 가지 삼중 큐비트 게이트가 있다. 세 큐비트의 경우 기저 벡터는 다음과 같이 정렬된다.

|000〉, |001〉, |010〉, |011〉, |100〉, |101〉, |110〉, |111〉

비트열처럼 정수 0, 1, 2, ..., 7 을 나타낸다. 키스킷은 첫번째 큐비트를 가장 오른쪽에, 세번째 큐비트를 가장 왼쪽에 위치하는 표현을 사용함을 재차 강조한다.

3.3.3.1. 토폴리 게이트

토폴리 게이트는 LSB로 첫번째와 두번째 큐비트가 모두 |1〉일 때 세번째 큐비트를 플립한다.  즉, 두 개의 제어 큐비트가 모두 |1〉인 경우 표적 큐비트를 플립한다.

행렬식으로 표현하면 다음과 같다.

회로의 구현은 다음과 같다.

코드3.25. CCX 게이트 구현

코드 345번 라인의 출력은 다음과 같다.

그림3.57. CCX 게이트 도식

코드 348번 라인의 출력은 다음과 같다.

그림3.58. CCX 게이트 후 큐비트들의 상태 벡터 출력

코드 351번 라인의 출력은 다음과 같다.

Toffoli(CCX)
 [[1.-0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 1.-0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 1.-0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 1.-0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+0.j 1.-0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 1.-0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 1.-0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 1.-0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j]]

코드 341 ~ 342번 라인의 주석 처리를 해제하면, 코드 348번 라인의 출력은 다음과 같다.

그림3.59. CCX 게이트 후 큐비트들의 상태 벡터 출력2

3.3.3.2. 제어 교환 게이트(또는 프레드킨 게이트)(Controlled swap gate, or Fredkin gate)

첫번째(LSB) 큐비트가 |1〉일 때 두번째와 세번째 큐비트를 교환한다. 즉, 제어 큐비트가 |1〉이면, 두 표적 큐비트를 교환한다. 수식은 다음과 같다.

프레드킨 게이트를 행렬로 표현하면 다음과 같다.

키스킷을 이용한 양자회로 구현은 다음과 같다.

코드3.26. CSWAP 게이트 회로 구현

코드 361번 라인의 출력은 다음과 같다.

그림3.60. CSWAP 게이트 회로 도식

코드 364번 라인의 출력은 다음과 같다.

그림3.61. CSWAP 게이트 상태 벡터 도식

코드 367번 라인의 출력은 다음과 같다.

Fredkin(CSWAP)
 [[1.-0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 1.-0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 1.-0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 1.-0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+0.j 1.-0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 1.-0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 1.-0.j 0.+0.j]
 [0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 0.+0.j 1.-0.j]]

코드 357~358번 라인의 주석처리를 제거하면 코드 364번 라인의 출력은 다음과 같다.

그림3.62. CSWAP 게이트 상태 벡터 도식2

3.4. 비 유니타리 연산들(Non-unitary operations)

양자 회로에서 사용 가능한 모든 유니타리 연산들을 살펴보았으니, 이제 유니타리가 아닌 연산들을 살펴보자. 유니타리가 아닌 연산에는 측정, 큐비트의 초기화(reset), 전통적인 조건 연산이 있다.

3.4.1. 측정

양자 컴퓨터에서 측정을 수행해도 모든 정보를 얻을 수는 없다. 양자 상태는 표준 기저에 사영된다. 아래 두 예는 각각 양자 상태들이 기저 상태 중 하나로 준비되거나 중첩 상태로 준비되는 회로를 보여준다.

코드3.27. 회로 측정 구현

코드 378번 라인의 출력은 다음과 같다.

그림3.63. 측정 회로 도식1

코드 381번 라인의 출력은 다음과 같다. 1024회 shot 모두 '0'으로 측정되었다.

{'0': 1024}

코드 387번 라인의 출력은 다음과 같다.

그림3.64. 측정 회로 도식2

코드 390번 라인의 출력은 다음과 유사하게 약 50%는 0, 나머지 약 50%는 1로 측정되었다.

{'0': 513, '1': 511}

3.4.2. 재설정(reset)

계산 중에 큐비트들을 |0〉 상태로 재설정하는 것도 가능하다. 재설정은 가역 연산이 아니므로 게이트 연산이 아님을 주목하자. 키스킷 구현은 다음과 같다.

코드3.28. 초기화 구현

코드 398번 라인의 출력은 다음과 같다.

그림3.65. 초기화 회로 도식1

코드 401번 라인의 출력은 다음과 같다.

{'0': 1024}

코드 408번 라인의 출력은 다음과 같다.

그림3.66. 초기화 회로 도식2

코드 411번 라인의 출력은 다음과 같다. 두 회로 모두 100% 로 결과값이 0 상태임을 알 수 있다.

{'0': 1024}

3.4.3. 조건 연산자

전통적인 레지스터의 상태를 조건으로 연산하는 것도 가능하다. 구현은 다음과 같다.

코드3.29. 조건 연산자 구현

코드 420번 라인의 출력은 다음과 같다. 

그림3.67. 조건 연산자 회로 도식1

코드 423번 라인의 출력은 다음과 같다. 

{'1': 1024}

코드 417번 라인에서, 전통적인 레지스터의 초기값은 0이므로, 양자 레지스터 q[0]에 플립이 발생한다. 양자 레지스터의 초기값도 0이므로, X 게이트 플립이 100% 발생하여 1로 측정된다.

코드 431번 라인의 출력은 다음과 같다.

그림3.68. 조건 연산자 회로 도식2

코드 434번 라인의 출력은 하다마드 게이트에 의해 큐비트 q3는 0과 1이 각각 약 50%의 확률을 갖는다. 코드 437번 측정에서 q3가 1인 경우, 전통적인 레지스터 c0는 측정에 따라 1이고 428번 라인의 조건(0일 때 적용)에 따라 X게이트를 적용하지 않아서 코드 434번의 결과는 q3가 1이다. 반대로, 코드 437번 측정에서 q3가 0인 경우, 전통적인 레지스터 c0도 0이고 428번 라인의 조건(0일 때 반전)이 적용되어 X 게이트로 q3가 반전된다. 따라서 q3 측정 결과는  역시 1이다. 따라서 코드 434번의 결과는 다음과 같다.

{'1': 1024}

전통적인 레지스터 c의 값은 초기에 0이므로, 417번 라인에서 x 게이트 플립이 양자 레지스터 q[0]에 적용된다. 따라서 

3.5. 임의 초기화

큐비트 레지스터를 임의의 상태로 초기화할 수 있다. n큐비트의 임의의 상태는 각 진폭의 절대값의 제곱을 모두 더했을 때 1이 되는 2ⁿ 개의 진폭을 나타내는 숫자로 구성된 벡터로 표현할 수 있다. 예를 들어, 다음의 세 큐비트 상태를 준비하자.

위 상태를 구현하면 다음과 같다.

코드3.30. 임의 초기화 구현

코드 455번 라인의 출력은 다음과 같다.

코드 460번 라인의 출력은 다음과 같다.

[2.50000000e-01-3.74255023e-17j 1.24900090e-16-3.53553391e-01j
 2.50000000e-01-2.50000000e-01j 0.00000000e+00+0.00000000e+00j
 0.00000000e+00+0.00000000e+00j 7.07106781e-01-3.53553391e-01j
 6.59194921e-17-2.50000000e-01j 0.00000000e+00+0.00000000e+00j]

충실도(Fidelity)는 두 상태가 같은지 확인하는데 유용하다. 두 순수한 양자 상태의 충실도는 다음과 같이 구한다.

F(|ψ₁〉, |ψ₂〉) = |〈ψ₁ | ψ₂〉|²

충실도는 오직 두 큐비트가 동일한 경우에만 1이다. 코트 463번 라인의 출력은 다음과 같다.

1.0000000000000004

3.5.1. 세부 내용

원하는 상태를 준비하는 다양한 방법들이 있지만, 키스킷에서는 Shende 등이 제안한 방법[4]을 사용한다. 이 논문의 아이디어는 양자 레지스터가 애초에 원하는 상태로 시작했다고 가정한 다음 |00...0〉 상태로 변환하는 회로를 구성하는 것이다. 그리고 이 회로의 역변환을 구하여 초기화 회로를 얻는다.

임의의 양자 상태를 계산 가능한 기저(computational basis)의 영 상태(zero state)로 만들고자 큐비트의 얽힘을 푸는 과정을 반복한다. 임의의 단일 큐비트 상태 |ρ〉 는 Z축을 중심으로 회전하는 Φ-회전과 Y축을 중심으로 회전하는 θ-회전을 연이어 수행하여 상태 |0〉로 변환할 수 있다. 

Ry(-θ)Rz(-Φ)|ρ〉 = reit|0>

지금 다루는 큐비트는 한 개가 아닌 n 개 이므로, 상태 벡터에서 가장 덜 중요한 비트(LSB)를 분리해 내고자 다음과 같이 성분 별로 묶어 분해한다.

이제 각 단일 큐비트 상태 |ρ0〉, ..., |ρ2n-1-1〉 은 적절한 각도 Φ와 θ를 찾아 |0〉으로 변환할 수 있다. LSB의 얽힘을 풀어나가는 이 과정을 모든 상태에 동시에 수행하는 유니타리는 다음과 같다.

따라서,

U는 블록 대각 행렬이므로, 양자 멀티플렉서(quantum multiplexor) 게이트로 구현할 수 있다. 양자 멀티플렉서에서 크기가 2ⁿ x 2ⁿ 이고, 2s 개의 블록 행렬로 구성된 블록 대각 행렬은 선택 큐비트(select qubit)가 s 개, 데이터 큐비트가 n - s개로 구성된 멀티플렉서와 동일하다. 이 때 선택 큐비트의 상태에 따라 데이터 큐비트에 적용되는 블록이 선택된다. 이러한 종류의 멀티플렉서는 기본 게이트 cr, rz 그리고 ry를 이용하여 재귀적으로 분해한 형태로 구현할 수 있다.

[1] 원문: 
https://qiskit.org/documentation/tutorials/circuits/3_summary_of_quantum_operations.html
[2] 내 코드: 
https://github.com/sungmin-net/python-qiskit-tutorials/blob/main/tutorial03_QuantumOperations.py
[3] 위키백과, '켤례전치': https://ko.wikipedia.org/wiki/켤레전치
[4] Vivek V. Shende 등, "Synthesis of Quantum Logic Circuits", https://arxiv.org/abs/quant-ph/0406176