Leetcode 큐빗(Qubit)을 다룬 문제

Quantum bit (Qubit)은 양자컴퓨팅에서 사용하는 개념이라 보통 생소한 개념인데 리트코드 문제로 나와서 인상깊어서 올려본다.

458. Poor Pigs

처음에 언듯보면 바이너리서치를 쓰는 문제 같지만, 솔루션을 보고 충격받았다. Qubit 개념을 적극적으로 쓰는 문제 였다. 솔루션 설명에서도 보듯이 최근 Google, IBM, Amazon 같은 회사에서 양자컴퓨터 개념을 물어보는 문제도 종종 나오기 시작한 것 같다.

다시 본론으로 돌아오면 문제는 돼지 하나를 큐빗 하나로 가정하여 독이든 버켓 하나를 찾는 것이다. 큐빗 처럼 동작하게 하기위해서 문제에서는 몇가지 가정을 준다.

• 돼지는 동시에 여러 버켓을 먹을 수 있다.
• 독이든 버켓을 먹은 돼지는 m분후 죽는다.
• m분동안 다른 돼지에게 버켓을 먹일 수 없다.

위 조건중 특히 동시에 여러 버켓을 먹을 수 있다라는 특성이 양자역학적인 특성에 들어맞는다. 동시에 먹일 수 있기 때문에 m분후 돼지는 살아있는 상태, 죽엉있는 상태 둘중 하나가 되기 때문에 독이든 버켓을 m분에 특정할 수 있다. 한 마리를 늘리고 버켓을 4개라고 가정하면  돼지1은 1, 2번 버켓, 돼지2는 2, 3번 버켓을 동시에 먹게하면 m분후 다음 4개의 케이스가 발생할 수 있다.

• 돼지1 🐖, 돼지2 🐖
• 돼지1 🐖, 돼지2 ☠️
• 돼지1 ☠️, 돼지2 🐖
• 돼지1 ☠️, 돼지2 ☠️

2개의 돼지로 4개의 버켓을 테스트할 수 있다. 동일하게 3개의 경우에는 8개, 4개의 경우에는 16개. n개의 경우에는 2^n개를 테스트할 수 있다. 여기서 추가로 문제에서 주어진 조건인 총 테스트 가능 시간 minutesToTest을 적용하면 돼지가 죽는시간이 m일 때 하나의 돼지로 총 m / minutesToTest + 1 번 테스트에 사용할 수 있는거다. 이 조건을 추가로 이용하면 (m / minutesToTest + 1) ^ x >= buckets 를 만족하는 x를 찾으면 되는 문제이다.